This book constitutes the refereed proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, CPM 2003, held in Morelia, Michoac?n, Mexico in June 2003.
The 28 revised full papers presented were carefully reviewed and selected from 57 submissions. The papers are devoted to current theoretical and computational aspects of searching and matching strings and more complicate patterns, such as trees, regular expressions, graphs, point sets, and arrays. Among the application fields addressed are computational biology, bioinformatics, genomics, the Web, data compression, coding, multimedia, information retrieval, pattern recognition, and computer vision.
Author(s): Mohamed Ibrahim Abouelhoda, Enno Ohlebusch (auth.), Ricardo Baeza-Yates, Edgar Chávez, Maxime Crochemore (eds.)
Series: Lecture Notes in Computer Science 2676
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2003
Language: English
Pages: 401
Tags: Algorithm Analysis and Problem Complexity; Coding and Information Theory; Discrete Mathematics in Computer Science; Information Storage and Retrieval; Document Preparation and Text Processing; Pattern Recognition
Multiple Genome Alignment: Chaining Algorithms Revisited....Pages 1-16
Two-Dimensional Pattern Matching with Rotations....Pages 17-31
An Improved Algorithm for Generalized Comparison of Minisatellites....Pages 32-41
Optimal Spaced Seeds for Hidden Markov Models, with Application to Homologous Coding Regions....Pages 42-54
Fast Lightweight Suffix Array Construction and Checking....Pages 55-69
Distributed and Paged Suffix Trees for Large Genetic Databases....Pages 70-82
Analysis of Tree Edit Distance Algorithms....Pages 83-95
An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees....Pages 96-108
Average-Optimal Multiple Approximate String Matching....Pages 109-128
Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms....Pages 129-143
Haplotype Inference by Pure Parsimony....Pages 144-155
A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions....Pages 156-169
Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals....Pages 170-185
Linear-Time Construction of Suffix Arrays....Pages 186-199
Space Efficient Linear Time Construction of Suffix Arrays....Pages 200-210
Tuning String Matching for Huge Pattern Sets....Pages 211-224
Sparse LCS Common Substring Alignment....Pages 225-236
On Minimizing Pattern Splitting in Multi-track String Matching....Pages 237-253
Alignment between Two Multiple Alignments....Pages 254-265
An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum....Pages 266-277
Pattern Discovery in RNA Secondary Structure Using Affix Trees....Pages 278-294
More Efficient Left-to-Right Pattern Matching in Non-sequential Equational Programs....Pages 295-314
Complexities of the Centre and Median String Problems....Pages 315-327
Extracting Approximate Patterns....Pages 328-347
A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression....Pages 348-360
Constrained Tree Inclusion....Pages 361-371
Working on the Problem of Sorting by Transpositions on Genome Rearrangements....Pages 372-383
Efficient Selection of Unique and Popular Oligos for Large EST Databases....Pages 384-401
