This book constitutes the refereed proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006, held in Barcelona, Spain in July 2006.
The 33 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 88 submissions. The papers are organized in topical sections on data structures, indexing data structures, probabilistic and algebraic techniques, applications in molecular biology, string matching, data compression, and dynamic programming.
Author(s): Amihood Amir (auth.), Moshe Lewenstein, Gabriel Valiente (eds.)
Series: Lecture Notes in Computer Science 4009 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 420
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Information Storage and Retrieval; Bioinformatics; Data Structures
Front Matter....Pages -
Asynchronous Pattern Matching....Pages 1-10
SNP and Haplotype Analysis – Algorithms and Applications....Pages 11-11
Identifying Co-referential Names Across Large Corpora....Pages 12-23
Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents....Pages 24-35
Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE....Pages 36-48
A Linear Size Index for Approximate Pattern Matching....Pages 49-59
On-Line Linear-Time Construction of Word Suffix Trees....Pages 60-71
Obtaining Provably Good Performance from Suffix Trees in Secondary Storage....Pages 72-83
Geometric Suffix Tree: A New Index Structure for Protein 3-D Structures....Pages 84-93
New Bounds for Motif Finding in Strong Instances....Pages 94-105
Fingerprint Clustering with Bounded Number of Missing Values....Pages 106-116
Tiling an Interval of the Discrete Line....Pages 117-128
Common Substrings in Random Strings....Pages 129-140
On the Repeat-Annotated Phylogenetic Tree Reconstruction Problem....Pages 141-152
Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms....Pages 153-164
Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees....Pages 165-176
An Improved Algorithm for the Macro-evolutionary Phylogeny Problem....Pages 177-187
Property Matching and Weighted Matching....Pages 188-199
Faster Two Dimensional Scaled Matching....Pages 200-210
Approximation of RNA Multiple Structural Alignment....Pages 211-222
Finding Common RNA Pseudoknot Structures in Polynomial Time....Pages 223-232
A Compact Mathematical Programming Formulation for DNA Motif Finding....Pages 233-245
Local Alignment of RNA Sequences with Arbitrary Scoring Schemes....Pages 246-257
An $O(n^{3/2}\sqrt{\log (n)})$ Algorithm for Sorting by Reciprocal Translocations....Pages 258-269
Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs....Pages 270-281
A Simpler Analysis of Burrows-Wheeler Based Compression....Pages 282-293
Statistical Encoding of Succinct Data Structures....Pages 294-305
Dynamic Entropy-Compressed Sequences and Full-Text Indexes....Pages 306-317
Reducing the Space Requirement of LZ-Index....Pages 318-329
Faster Algorithms for Computing Longest Common Increasing Subsequences....Pages 330-341
New Algorithms for Text Fingerprinting....Pages 342-353
Sublinear Algorithms for Parameterized Matching....Pages 354-364
Approximate Matching in Weighted Sequences....Pages 365-376
Algorithms for Finding a Most Similar Subforest....Pages 377-388
Efficient Algorithms for Regular Expression Constrained Sequence Alignment....Pages 389-400
Large Scale Matching for Position Weight Matrices....Pages 401-412
Back Matter....Pages -
