Combinatorial Pattern Matching

by Baeza-Yates, Ricardo; Baeza-Yates, Ricardo; Chavez, Edgar; Crochemore, Maxime

• ISBN13: 9783540403111
• ISBN10: 3540403116
• Format: Paperback
• Copyright: 2003-08-01
• Publisher: Springer-Verlag New York Inc

Summary

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.

Table of Contents

Multiple Genome Alignment: Chaining Algorithms Revisited	p. 1
Two-Dimensional Pattern Matching with Rotations	p. 17
An Improved Algorithm for Generalized Comparison of Minisatellites	p. 32
Optimal Spaced Seeds for Hidden Markov Models, with Application to Homologous Coding Regions	p. 42
Fast Lightweight Suffix Array Construction and Checking	p. 55
Distributed and Paged Suffix Trees for Large Genetic Databases	p. 70
Analysis of Tree Edit Distance Algorithms	p. 83
An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees	p. 96
Average-Optimal Multiple Approximate String Matching	p. 109
Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms	p. 129
Haplotype Inference by Pure Parsimony	p. 144
A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions	p. 156
Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals	p. 170
Linear-Time Construction of Suffix Arrays	p. 186
Space Efficient Linear Time Construction of Suffix Arrays	p. 200
Tuning String Matching for Huge Pattern Sets	p. 211
Sparse LCS Common Substring Alignment	p. 225
On Minimizing Pattern Splitting in Multi-track String Matching	p. 237
Alignment between Two Multiple Alignments	p. 254
An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum	p. 266
Pattern Discovery in RNA Secondary Structure Using Affix Trees	p. 278
More Efficient Left-to-Right Pattern Matching in Non-sequential Equational Programs	p. 295
Complexities of the Centre and Median String Problems	p. 315
Extracting Approximate Patterns	p. 328
A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression	p. 348
Constrained Tree Inclusion	p. 361
Working on the Problem of Sorting by Transpositions on Genome Rearrangements	p. 372
Efficient Selection of Unique and Popular Oligos for Large EST Databases	p. 384
Author Index	p. 403
Table of Contents provided by Blackwell. All Rights Reserved.