Combinatorial Pattern Matching, 2007 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings Theoretical Computer Science and General Issues Series

Invited Talks (Abstracts).- A Combinatorial Approach to Genome-Wide Ortholog Assignment: Beyond Sequence Similarity Search.- Stringology: Some Classic and Some Modern Problems.- Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors.- Session 1: Alogirthmic Techniques I.- Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.- On Demand String Sorting over Unbounded Alphabets.- Session 2: Approximate Pattern Matching.- Finding Witnesses by Peeling.- Cache-Oblivious Index for Approximate String Matching.- Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.- Self-normalised Distance with Don’t Cares.- Session 3: Data Compression I.- Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.- A Lempel-Ziv Text Index on Secondary Storage.- Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts.- Most Burrows-Wheeler Based Compressors Are Not Optimal.- Session 4: Computational Biology I.- Non-breaking Similarity of Genomes with Gene Repetitions.- A New and Faster Method of Sorting by Transpositions.- Finding Compact Structural Motifs.- Session 5: Computational Biology II.- Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants.- Computing Exact p-Value for Structured Motif.- Session 6: Algorithmic Techniques II.- Improved Sketching of Hamming Distance with Error Correcting.- Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications.- Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge.- Space-Efficient Algorithms for Document Retrieval.- Session 7: Data Compression II.- Compressed Text Indexes with Fast Locate.- Processing Compressed Texts: A Tractability Border.- Session 8: Computational Biology III.- Common Structured Patterns in Linear Graphs: Approximation and Combinatorics.- Identification of Distinguishing Motifs.- Algorithms for Computing the Longest Parameterized Common Subsequence.- Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem.- Session 9: Pattern Analysis.- Two-Dimensional Range Minimum Queries.- Tiling Periodicity.- Fast and Practical Algorithms for Computing All the Runs in a String.- Longest Common Separable Pattern Among Permutations.- Session 10: Suffix Arrays and Trees.- Suffix Arrays on Words.- Efficient Computation of Substring Equivalence Classes with Suffix Arrays.- A Simple Construction of Two-Dimensional Suffix Trees in Linear Time.