Combinatorial Pattern Matching: 20th Annual Symposium, CPM 2009 Lille, France, June 22-24, 2009 Proceedings

Front Cover
Gregory Kucherov, Esko Ukkonen
Springer Science & Business Media, Jun 8, 2009 - Computers - 370 pages
It is our great pleasure to introduce the proceedings of the 20th anniversary edition of the Annual Symposium on Combinatorial Pattern Matching (CPM). The meeting was held in Lille, France, hosted by the Laboratoired'Informatique Fondamentale de Lille (LIFL) a?liated with the Universit e de Lille 1 and the French Centre National de Recherche Scienti?que (CNRS), as well as by INRIA Lille - Nord Europe. Started in 1990as a summer school with about 30 invited participants, CPM quicklyevolvedintoarepresentativeannualinternationalconference.Principally motivated by combinatorial algorithms for search problems in strings (texts, sequences), the scope of CPM extended to more complex data structures such astrees, graphs, two-dimensionalarrays, or setsof points.Thosestudiesresulted inarichcollectionofalgorithmictechniquesanddatastructures, makingbridges to other parts of the theory of discrete algorithms and algorithm engineering. Today, the area of combinatorial pattern matching is a well-identi?ed active sub?eld of algorithmic research. Importantly, this development has been fertilized by a number of major - plication areas providing direct motivations and fruitful feedback to the CPM problematics. Those applications include data compression, computational bi- ogy, Internetsearch, datamining, informationretrieval, coding, naturallanguage processing, pattern recognition, music analysis, and others. On the one hand, all these areas make use of combinatorial pattern matching techniques and, on the otherhand, raisenewpatternmatchingproblems.Forexample, the fastprogress in computational molecular biology, triggered in the 1990s by the availability of mass genomic data, considerably in?uenced the combinatorial pattern matching ?eld: as an illustration, about one-third of the papers presented in this volume deal with problems related to bioinformatics applications.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

A Statistical Retrospective
1
Quasidistinct Parsing and Optimal Compression Methods
12
Generalized Substring Compression
26
Common Problems and Techniques
39
A Simple and Dynamic Text Indexing Data Structure
41
Linear Time Suffix Array Construction Using DCritical Substrings
54
On the Value of Multiple ReadWrite Streams for Data Compression
68
Reoptimization of the Shortest Common Superstring Problem Extended Abstract
78
Periodic String Comparison
193
A Case Study for Interval Constrained Coloring
207
Maximum Motif Problem in VertexColored Graphs
221
Fast RNA Structure Alignment for Crossing Input Structures
236
Time and Space Efficient Algorithms
249
A Flexible Approach
263
Patterns Generators and Tools
274
Levelk Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time
275

LCS Approximation via Embedding into Local Nonrepetitive Strings
92
An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings
106
Fast Searching in Packed Strings
116
New Complexity Bounds for Image Matching under Rotation and Scaling
127
Online Approximate Matching with Nonlocal Distances
142
Faster and SpaceOptimal Edit Distance 1 Dictionary
154
Approximate Matching for RunLength Encoded Strings Is 3sumHard
168
Modeling and Algorithmic Challenges in Online Social Networks
180
Permuted LongestCommonPrefix Array
181
The Structure of Levelk Phylogenetic Networks
289
Finding All Sorting Tandem Duplication Random Loss Operations
301
AverageCase Analysis of Perfect Sorting by Reversals
314
Statistical Properties of Factor Oracles
326
Haplotype Inference Constrained by Plausible Haplotype Data
339
Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles Extented Abstract
353
Author Index
368
Copyright

Other editions - View all

Common terms and phrases