## Combinatorial Pattern Matching: 20th Annual Symposium, CPM 2009 Lille, France, June 22-24, 2009 ProceedingsGregory Kucherov, Esko Ukkonen 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 LongestCommonPreﬁx 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 |

368 | |

### Other editions - View all

Combinatorial Pattern Matching: 20th Annual Symposium, CPM 2009 Lille ... Gregory Kucherov,Esko Ukkonen No preview available - 2009 |

### Common terms and phrases

3sum algorithm alleles alphabet applied approximation binary bits bound bucket sort character color combinatorial common complexity compression Computer Science connected component constraints construction corresponding Crochemore cut-arc D-Critical data structure deﬁned Deﬁnition denote dictionary diﬀerent dynamic programming edit distance eﬃcient elements encoded equations ﬁnd ﬁnding ﬁrst ﬁxed function gene genome genotype given graph haplotype hash Heidelberg input instance integer Kucherov labeled Landau LCP array Lemma length level-k network linear LNCS matrix multisets mutations network alignment node NP-hard occurrences optimal p-variables pair parameter parsing path pattern matching pedigree perfect hash functions permutation permutation matrix phylogenetic networks PLCP polynomial position preﬁx preprocessing Proof query recursion sequence Si,j SN-set solution sorting TDRLs space speciﬁc split Springer strong interval tree substring subtree suﬃx suﬃx array suﬃx tree Theorem transition triplet Ukkonen Eds values vertex vertices