The papers contained in this volume were presented at the 18th Annual S- posium on Combinatorial Pattern Matching (CPM 2007) held at the University of Western Ontario, in London, Ontario, Canada from July 9 to 11, 2007. All the papers presented at the conference are original research contri- tions on computational pattern matching and analysis, data compression and compressed text processing, su?x arrays and trees, and computational biology. They were selected from 64 submissions. Each submission was reviewed by at least three reviewers. The committee decided to accept 32 papers. The p- gramme also included three invited talks by Tao Jiang from the University of California, Riverside, USA, S. Muthukrishnan from Rutgers University, USA, and Frances Yao from City University of Hong Kong, Hong Kong. Combinatorial Pattern Matching addresses issues of searching and matching stringsandmorecomplicatedpatternssuchastrees,regularexpressions,graphs, point sets, and arrays.The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed e?ciently.
Author(s): Tao Jiang (auth.), Bin Ma, Kaizhong Zhang (eds.)
Series: Lecture Notes in Computer Science 4580
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 368
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Data Mining and Knowledge Discovery; Computational Biology/Bioinformatics; Data Structures
Front Matter....Pages -
A Combinatorial Approach to Genome-Wide Ortholog Assignment: Beyond Sequence Similarity Search....Pages 1-1
Stringology: Some Classic and Some Modern Problems....Pages 2-2
Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors....Pages 3-3
Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions....Pages 4-15
On Demand String Sorting over Unbounded Alphabets....Pages 16-27
Finding Witnesses by Peeling....Pages 28-39
Cache-Oblivious Index for Approximate String Matching....Pages 40-51
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts....Pages 52-62
Self-normalised Distance with Don’t Cares....Pages 63-70
Move-to-Front, Distance Coding, and Inversion Frequencies Revisited....Pages 71-82
A Lempel-Ziv Text Index on Secondary Storage....Pages 83-94
Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts....Pages 95-106
Most Burrows-Wheeler Based Compressors Are Not Optimal....Pages 107-118
Non-breaking Similarity of Genomes with Gene Repetitions....Pages 119-130
A New and Faster Method of Sorting by Transpositions....Pages 131-141
Finding Compact Structural Motifs....Pages 142-149
Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants....Pages 150-161
Computing Exact p-Value for Structured Motif....Pages 162-172
Improved Sketching of Hamming Distance with Error Correcting....Pages 173-182
Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications....Pages 183-194
Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge....Pages 195-204
Space-Efficient Algorithms for Document Retrieval....Pages 205-215
Compressed Text Indexes with Fast Locate....Pages 216-227
Processing Compressed Texts: A Tractability Border....Pages 228-240
Common Structured Patterns in Linear Graphs: Approximation and Combinatorics....Pages 241-252
Identification of Distinguishing Motifs....Pages 253-264
Algorithms for Computing the Longest Parameterized Common Subsequence....Pages 265-273
Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem....Pages 274-285
Two-Dimensional Range Minimum Queries....Pages 286-294
Tiling Periodicity....Pages 295-306
Fast and Practical Algorithms for Computing All the Runs in a String....Pages 307-315
Longest Common Separable Pattern Among Permutations....Pages 316-327
Suffix Arrays on Words....Pages 328-339
Efficient Computation of Substring Equivalence Classes with Suffix Arrays....Pages 340-351
A Simple Construction of Two-Dimensional Suffix Trees in Linear Time....Pages 352-364
Back Matter....Pages -
