Combinatorial Pattern Matching: 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006, Proceedings: Lecture Notes in Computer Science, cartea 4009

Asynchronous Pattern Matching.- Asynchronous Pattern Matching.- SNP and Haplotype Analysis – Algorithms and Applications.- Identifying Co-referential Names Across Large Corpora.- Session 1. Data Structures.- Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents.- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE.- Session 2. Indexing Data Structures.- A Linear Size Index for Approximate Pattern Matching.- On-Line Linear-Time Construction of Word Suffix Trees.- Obtaining Provably Good Performance from Suffix Trees in Secondary Storage.- Geometric Suffix Tree: A New Index Structure for Protein 3-D Structures.- Session 3. Probabilistic and Algebraic Techniques.- New Bounds for Motif Finding in Strong Instances.- Fingerprint Clustering with Bounded Number of Missing Values.- Tiling an Interval of the Discrete Line.- Common Substrings in Random Strings.- Session 4. Applications in Molecular Biology I.- On the Repeat-Annotated Phylogenetic Tree Reconstruction Problem.- Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms.- Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees.- An Improved Algorithm for the Macro-evolutionary Phylogeny Problem.- Session 5. String Matching I.- Property Matching and Weighted Matching.- Faster Two Dimensional Scaled Matching.- Session 6. Applications in Molecular Biology II.- Approximation of RNA Multiple Structural Alignment.- Finding Common RNA Pseudoknot Structures in Polynomial Time.- A Compact Mathematical Programming Formulation for DNA Motif Finding.- Local Alignment of RNA Sequences with Arbitrary Scoring Schemes.- Session 7. Applications in MolecularBiology III.- An Algorithm for Sorting by Reciprocal Translocations.- Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs.- Session 8. Data Compression.- A Simpler Analysis of Burrows-Wheeler Based Compression.- Statistical Encoding of Succinct Data Structures.- Dynamic Entropy-Compressed Sequences and Full-Text Indexes.- Reducing the Space Requirement of LZ-Index.- Session 9. String Matching II.- Faster Algorithms for Computing Longest Common Increasing Subsequences.- New Algorithms for Text Fingerprinting.- Sublinear Algorithms for Parameterized Matching.- Approximate Matching in Weighted Sequences.- Session 10. Dynamic Programming.- Algorithms for Finding a Most Similar Subforest.- Efficient Algorithms for Regular Expression Constrained Sequence Alignment.- Large Scale Matching for Position Weight Matrices.