After June 5
Standard fee FIM 1100
Student fee FIM 500
Accommodation fees:
Single room FIM 300/night
Double room FIM 190/night/person
Triple room FIM 140/night/person
Double room (downtown) FIM 110/night/person
Registration fees are payable in Finnish marks (FIM) at the symposium. (In April 1995, the exchange rate was FIM 1 = USD 0.24.) No advance payment is required. However, the registration should be sent to the organizers as soon as possible. To avoid the late fee, the registration must be received by June 5. The acceptance of late registrations cannot be quaranteed because of space limitations.
The standard fee includes the Wednesday night reception, Thursday excursion and banquet, lunches, coffee breaks, and one copy of the proceedings.
The student fee includes all of the above except excursion and banquet. Students must present a note from their department or supervisor verifying student status.
The summer school fee includes lunches and coffee breaks.
Accompanying persons are invited to Wednesday's reception given by the University of Helsinki. Additional tickets for the excursion and the conference banquet are sold at the symposium.
A block of rooms has been reserved at the Hotel Hanasaari for participants. Room reservations should be made through the organizers using the registration form. The accommodation fees are collected by the hotel.
There is an interactive registration form in WWW. Alternatively, the form (or equivalent information) can be sent by email, fax, or mail to:
CPM '95 Registration
Department of Computer Science
P.O. Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland
Email: cpm95@cs.helsinki.fi
Fax: +358-0-70844441
TUESDAY, JULY 4, 1995
7:00-9:30 pm Registration at Hotel Hanasaari
WEDNESDAY, JULY 5, 1995
SESSION 1. Chair: E. Ukkonen
9:00 New results and open problems related to non-standard stringology, S. Muthukrishnan
9:25 Constant-space string matching with smaller number of comparisons: sequential sampling, L. Gasieniec, W. Plandowski, W. Rytter
9:50 Smaller representations for finite-state transducers and finite-state automata, E. Roche
10:15 Matching patterns of an automaton, M. Mohri
10:40 Coffee Break
11:10 Invited Lecture: On a technique for parsing a string, U. Vishkin
12:00 Lunch Break
SESSION 2. Chair: M. Paterson
1:30 Matching a set of strings with variable length don't cares, G. Kucherov, M. Rusinowitch
1:55 Dictionary look-up with small errors, A. Yao, F. Yao
2:20 Pattern-matching for strings with short descriptions, M. Karpinski, W. Rytter, A. Shinohara
2:45 Coffee Break
SESSION 3. Chair: J. Storer
3:15 Common subsequences and supersequences and their expected length, V. Dancik
3:40 A new flexible algorithm for the longest common subsequence problem, C. Rick
4:05 Multi-dimensional pattern matching with dimensional wildcards, R. Giancarlo, R. Grossi
4:30 Efficient string matching on coded texts, D. Breslauer, L. Gasieniec
4:55 End of Session
5:30-6:30 Open Problems Session
7:00-8:30 Reception University Main Building, Entrance: Aleksanterinkatu 5
THURSDAY, JULY 6, 1995
SESSION 4. Chair: D. Gusfield
9:00 An efficient algorithm for developing topologically valid matchings, L. Hanks, R. Cytron, W. Gillett
9:25 Three-dimensional pattern matching in protein structure analysis, A. Lesk
9:50 Multiple sequence comparison - A peptide matching approach, M.-F. Sagot, A. Viari, H. Soldano
10:15 Polynomial-time algorithm for computing translocation distance between genomes, S. Hannenhalli
10:40 Coffee Break
11:10 Invited Lecture: Genome analysis: Pattern search in biological sequences, H. W. Mewes
12:00 Lunch Break
SESSION 5. Chair: P. Pevzner
1:30 Computing similarity between RNA strings, V. Bafna, S. Muthukrishnan, R. Ravi
1:55 Making the shortest-paths approach to sum-of-pairs multiple sequence alignment more space efficient in practice, S. Gupta, J. Kececioglu, A. Schaffer
2:20 Pairwise alignment with scoring on tuples, L. Knecht
2:45 Coffee Break
SESSION 6. Chair: J. Tarhio
3:15 Fast approximate matching using suffix trees, A. Cobbs
3:40 Suffix cactus: A cross between suffix tree and suffix array, J. Karkkainen
4:05 End of Session
5:00 Excursion and Banquet
FRIDAY, JULY 7, 1995
SESSION 7. Chair: A. Ehrenfeucht
9:00 Minimizing phylogenetic number to find good evolutionary trees, L. A. Goldberg, P. Goldberg, C. Phillips, E. Sweedyk, T. Warnow
9:25 On the complexity of comparing evolutionary trees, J. Hein, T. Jiang, L. Wang, K. Zhang
9:50 Of chicken teeth and mouse eyes, or generalized character compatibility, C. Benham, S. Kannan, T. Warnow
10:15 Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree, R. Ravi, J. Kececioglu
10:40 Coffee Break
SESSION 8. Chair: M. Wegman
11:10 On the editing distance between undirected acyclic graphs and related problems, K. Zhang, J. Wang, D. Shasha
11:35 Pattern matching in directed graphs, J. Fu
12:00 String matching in hypertext, K. Park, D. Kim
12:25 Lunch
JULY 3-4, 1995
Before the symposium a short summer school will be held at the same location. The program consists of four tutorials. The registration for the school is on Sunday, July 2, at 6-8 pm. The program starts on Monday morning, July 3. The first half of each tutorial is given on Monday and the second half on Tuesday. More information about the school is available in our WWW server.
TUTORIAL 1:
String algorithms and sequence comparisons
D. Gusfield (University of California at Davis)
We will begin with a quick review of some basic string algorithms for exact matching. Then we will discuss suffix trees and non-trivial applications of them. Next we move to inexact matching and alignment with emphasis on applications that come from computational molecular biology. We will look at various definitions of inexact matching and associated algorithms that have proven effective for biological problems. We will consider in detail choices for gap models, and parameter settings, and the biological and algorithmic effects of those choices. Multiple alignment will then be particularly emphasized. Finally, we will discuss the interplay between string algorithms and algorithms for reconstructing evolutionary history, both in the form of evolutionary trees and in non-tree representations. Rather than being a "how to" course, the talks will emphasize precise statements of problems, algorithms and analyses.
TUTORIAL 2:
Combinatorial algorithms for DNA sequencing and mapping
J. Kececioglu (University of Georgia)
DNA sequencing and mapping, the tasks of determining the location of landmarks along a DNA molecule, as well as the DNA sequence itself, are basic tasks in molecular biology, and the design of algorithms to support these tasks is an area of active research. While the field is still relatively new, a few fundamental approaches are emerging, many based on combinatorial optimization. This tutorial will survey what's known about combinatorial algorithms for DNA sequence assembly and physical mapping, and point to some of the directions of current research. Specific topics include approximation of shortest superstrings, generalization to error and reverse complementarity, local search for mapping by unique and non-unique probes, and guarantees in the presence of chimerism.
TUTORIAL 3:
Foundations of data mining
H. Mannila (University of Helsinki)
Data mining, or knowledge discovery in databases, aims at formation of interesting knowledge from large masses of data. Data mining combines methods from machine learning, statistics, and databases. Data mining has recently attracted a lot of attention from the research community and from the industrial sector. In these lectures we discuss briefly the motivation and the application areas of the research in data mining. We concentrate on the basic algorithmic problems of data mining and study how the problems and methods of data mining differ from those used in machine learning and in statistics.
TUTORIAL 4:
Reconstructing evolutionary trees from molecular sequences
M. Vingron (GMD, Bonn)
DNA and protein sequences have become a major source of information for the reconstruction of the course of evolution. This tutorial will survey methods to derive phylogenetic trees from molecular sequences. Over time many fields have contributed to this problem. Therefore some of the methods are mainly algorithmic while others are statistical or mathematical. However, no special background will be required for the lectures.
LOCATION: All sessions of the symposium and the summer school will be held at the Swedish-Finnish Cultural Centre Hanasaari in Espoo, about 5 km west of the downtown of Helsinki. The participants are supposed to stay in the hotel of the Hanasaari Centre (see Section REGISTRATION for reservations). The address of the hotel is
Hotel Hanasaari
Hanasaari
FIN-02100 Espoo, Finland
Tel.: +358-0-461566
Fax: +358-0-467291
The hotel can be reached by taxi from the Helsinki-Vantaa Airport. The trip takes 20-35 minutes and costs about FIM 130. A cheaper alternative is to use the van services available at the airport.
There are nonstop flights to Helsinki from New York (Finnair and Delta) and from San Francisco, Toronto, and major European cities (Finnair). Participants planning other stops in Europe should know that building a trip from APEX round-trip tickets is likely to be much less expensive than using a Hamiltonian path.
There are daily ferry services between Helsinki and Stockholm on high-standard ships sailing through a scenic archipelago. Helsinki can also be reached by ferry from Travemunde (Germany), Gdansk (Poland), and Tallinn (Estonia).
PROCEEDINGS: Springer-Verlag will publish the proceedings. One copy is included in the registration fee; additional copies may be purchased at the symposium.
RECEPTION: A reception will be given by the Rector of the University of Helsinki in the University Main Building, entrance Aleksanterinkatu 5, at 7:00 pm on Wednesday, July 5.
CLIMATE: The weather in Helsinki is warm in July. Daytime temperatures should be 17-23 C, with cooler evenings. Be prepared to occasional showers.
TOURISM: Combined with your trip to CPM '95 it is easy to spend a few more days in Finland, for example, to visit Lapland or the lake district of the country. Travel agencies also organize different package tours from Helsinki to Tallinn and to St. Petersburg. For more information and bookings, contact, as early as possible:
Congress Team
AREA Travel Agency Ltd.
P.O. Box 6 (Paivarinnankatu 1)
FIN-00251 Helsinki, Finland
Tel: +358-0-8183385
Fax: +358-0-4775811
CPM INFORMATION: The first symposium on Combinatorial Pattern Matching was held in Paris in 1990, followed by meetings in London, Tucson, Padova, and Pacific Grove. The sixth symposium in Helsinki continues this tradition.
PROGRAM COMMITTEE: A. Ehrenfeucht, Z. Galil (co-chair), D. Gusfield, U. Manber, M. Paterson, P. Pevzner, I. Simon, J. Storer, E. Ukkonen (co-chair), M. Wegman.
STEERING COMMITTEE: A. Apostolico, M. Crochemore, Z. Galil, U. Manber.
LOCAL ORGANIZERS: J. Karkkainen, P. Kilpelainen, E. Sutinen, J. Tarhio.
FURTHER INFORMATION:
CPM '95/Esko Ukkonen
Department of Computer Science
P.O. Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland
Email: cpm95@cs.helsinki.fi
Tel.: +358-0-70844172
Fax: +358-0-70844441
http://www.cs.helsinki.fi/events/cpm95