This book constitutes the refereed proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching, CPM 2005, held in Jeju island, Korea on June 19-22, 2005.
The 37 revised full papers presented were carefully reviewed and selected from 129 submissions. They constitute original research contributions in combinatorial pattern matching and its applications. Among the application fields addressed are computational biology, bioinformatics, genomics, proteinomics, data compression, Sequence Analysis and Graphs, information retrieval, data analysis, and pattern recognition.
Author(s): Broňa Brejová, Daniel G. Brown, Ian M. Harrower (auth.), Alberto Apostolico, Maxime Crochemore, Kunsoo Park (eds.)
Series: Lecture Notes in Computer Science 3537 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 452
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Information Storage and Retrieval; Document Preparation and Text Processing; Pattern Recognition; Bioinformatics
Front Matter....Pages -
Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern ....Pages 1-10
On the Longest Common Rigid Subsequence Problem....Pages 11-20
Text Indexing with Errors....Pages 21-32
A New Compressed Suffix Tree Supporting Fast Search and Its Construction Algorithm Using Optimal Working Space....Pages 33-44
Succinct Suffix Arrays Based on Run-Length Encoding....Pages 45-56
Linear-Time Construction of Compressed Suffix Arrays Using o ( n log n )-Bit Working Space for Large Alphabets....Pages 57-67
Faster Algorithms for δ , γ -Matching and Related Problems....Pages 68-78
A Fast Algorithm for Approximate String Matching on Gene Sequences....Pages 79-90
Approximate Matching in the L 1 Metric....Pages 91-103
An Efficient Algorithm for Generating Super Condensed Neighborhoods....Pages 104-115
The Median Problem for the Reversal Distance in Circular Bacterial Genomes....Pages 116-127
Using PQ Trees for Comparative Genomics....Pages 128-143
Hardness of Optimal Spaced Seed Design....Pages 144-155
Weighted Directed Word Graph....Pages 156-167
Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets....Pages 168-177
An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression....Pages 178-189
DNA Compression Challenge Revisited: A Dynamic Programming Approach....Pages 190-200
On the Complexity of Sparse Exon Assembly....Pages 201-218
An Upper Bound on the Hardness of Exact Matrix Based Motif Discovery....Pages 219-228
Incremental Inference of Relational Motifs with a Degenerate Alphabet....Pages 229-240
Speeding up Parsing of Biological Context-Free Grammars....Pages 241-256
A New Periodicity Lemma....Pages 257-265
Two Dimensional Parameterized Matching....Pages 266-279
An Optimal Algorithm for Online Square Detection....Pages 280-287
A Simple Fast Hybrid Pattern-Matching Algorithm....Pages 288-297
Prefix-Free Regular-Expression Matching....Pages 298-309
Reducing the Size of NFAs by Using Equivalences and Preorders....Pages 310-321
Regular Expression Constrained Sequence Alignment....Pages 322-333
A Linear Tree Edit Distance Algorithm for Similar Ordered Trees....Pages 334-345
A Polynomial Time Matching Algorithm of Ordered Tree Patterns Having Height-Constrained Variables....Pages 346-357
Assessing the Significance of Sets of Words....Pages 358-370
Inferring a Graph from Path Frequency....Pages 371-382
Exact and Approximation Algorithms for DNA Tag Set Design....Pages 383-393
Parametric Analysis for Ungapped Markov Models of Evolution....Pages 394-405
Linear Programming for Phylogenetic Reconstruction Based on Gene Rearrangements....Pages 406-416
Identifying Similar Surface Patches on Proteins Using a Spin-Image Surface Representation....Pages 417-428
Mass Spectra Alignments and Their Significance....Pages 429-441
Back Matter....Pages -
