This book constitutes the refereed proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching, CPM 2009, held in Lille, France in June 2009.
The 27 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 63 submissions. The papers address all areas related to combinatorial pattern matching and its applications, such as coding and data compression, computational biology, data mining, information retrieval, natural language processing, pattern recognition, string algorithms, string processing in databases, symbolic computing and text searching.
Author(s): Elena Yavorska Harris, Thierry Lecroq, Gregory Kucherov (auth.), Gregory Kucherov, Esko Ukkonen (eds.)
Series: Lecture Notes in Computer Science 5577 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 370
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Information Storage and Retrieval; Pattern Recognition; Computational Biology/Bioinformatics; Bioinformatics
Front Matter....Pages -
CPM’s 20th Anniversary: A Statistical Retrospective....Pages 1-11
Quasi-distinct Parsing and Optimal Compression Methods....Pages 12-25
Generalized Substring Compression....Pages 26-38
Text Indexing, Suffix Sorting, and Data Compression: Common Problems and Techniques....Pages 39-40
Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure....Pages 41-53
Linear Time Suffix Array Construction Using D-Critical Substrings....Pages 54-67
On the Value of Multiple Read/Write Streams for Data Compression....Pages 68-77
Reoptimization of the Shortest Common Superstring Problem....Pages 78-91
LCS Approximation via Embedding into Local Non-repetitive Strings....Pages 92-105
An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings....Pages 106-115
Fast Searching in Packed Strings....Pages 116-126
New Complexity Bounds for Image Matching under Rotation and Scaling....Pages 127-141
Online Approximate Matching with Non-local Distances....Pages 142-153
Faster and Space-Optimal Edit Distance “1” Dictionary....Pages 154-167
Approximate Matching for Run-Length Encoded Strings Is 3sum -Hard....Pages 168-179
Modeling and Algorithmic Challenges in Online Social Networks....Pages 180-180
Permuted Longest-Common-Prefix Array....Pages 181-192
Periodic String Comparison....Pages 193-206
Deconstructing Intractability: A Case Study for Interval Constrained Coloring....Pages 207-220
Maximum Motif Problem in Vertex-Colored Graphs....Pages 221-235
Fast RNA Structure Alignment for Crossing Input Structures....Pages 236-248
Sparse RNA Folding: Time and Space Efficient Algorithms....Pages 249-262
Multiple Alignment of Biological Networks: A Flexible Approach....Pages 263-273
Graph Mining: Patterns, Generators and Tools....Pages 274-274
Level- k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time....Pages 275-288
The Structure of Level- k Phylogenetic Networks....Pages 289-300
Finding All Sorting Tandem Duplication Random Loss Operations....Pages 301-313
Average-Case Analysis of Perfect Sorting by Reversals....Pages 314-325
Statistical Properties of Factor Oracles....Pages 326-338
Haplotype Inference Constrained by Plausible Haplotype Data....Pages 339-352
Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles (Extented Abstract)....Pages 353-367
Back Matter....Pages -
