Combinatorial Pattern Matching: 8th Annual Symposium, CPM 97 Aarhus, Denmark, June 30–July 2, 1997 Proceedings

Masamichi Miyazaki, Ayumi Shinohara, Masayuki Takeda (auth.), Alberto Apostolico, Jotun Hein (eds.)3540632204, 9783540632207

This book constitutes the refereed proceedings of the Eighth Annual Symposium on Combinatorial Pattern Matching, CPM 97, held in Aarhus, Denmark, in June/July 1997.
The volume presents 20 revised full papers carefully selected from 32 submissions received; also included are abstracts of two invited contributions. The volume is devoted to the issue of searching and matching strings and more complicated patterns, such as trees, regular expressions, graphs, point sets and arrays. The results presented are particularly relevant to molecular biology, but also to information retrieval, pattern recognition, compiling, data compression and program analysis.

---

Table of contents :
An improved pattern matching algorithm for strings in terms of straight-line programs….Pages 1-11
Episode matching….Pages 12-27
Efficient algorithms for approximate string matching with swaps….Pages 28-39
On the complexity of pattern matching for highly compressed two-dimensional texts….Pages 40-51
Estimating the probability of approximate matches….Pages 52-64
Space- and time-efficient decoding with canonical huffman trees….Pages 65-75
On weak circular squares in binary words….Pages 76-82
An easy case of sorting by reversals….Pages 83-89
External inverse pattern matching….Pages 90-101
Distributed generation of suffix arrays….Pages 102-115
Direct construction of compact directed acyclic word graphs….Pages 116-129
Approximation algorithms for the fixed-topology phylogenetic number problem….Pages 130-149
A new algorithm for the ordered tree inclusion problem….Pages 150-166
On incremental computation of transitive closure and greedy alignment….Pages 167-179
Aligning coding DNA in the presence of frame-shift errors….Pages 180-190
A filter method for the weighted local similarity search problem….Pages 191-205
Trie-based data structures for sequence assembly….Pages 206-223
Flexible identification of structural objects in nucleic acid sequences: Palindromes, mirror repeats, pseudoknots and triple helices….Pages 224-246
Banishing bias from consensus sequences….Pages 247-261
On the Nadeau-Taylor theory of conserved chromosome segments….Pages 262-274
Iterative versus simultaneous multiple sequence alignment….Pages 275-275
Modern comparative lexicostatistics….Pages 276-276