Combinatorial Pattern Matching: 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings

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 -