Combinatorial Pattern Matching: 5th Annual Symposium, CPM 94 Asilomar, CA, USA, June 5–8, 1994 Proceedings

Gary Benson (auth.), Maxime Crochemore, Dan Gusfield (eds.)3540580948, 9783540580942

This volume presents the proceedings of the Fifth Annual Symposium on Combinatorial Pattern Matching, held at Asilomar, California, in June 1994. The 26 selected papers in this volume are organized in chapters on Alignments, Various Matchings, Combinatorial Aspects, and Bio-Informatics. Combinatorial Pattern Matching addresses issues of searching and matching of strings and more complicated patterns, as for example trees. The goal is to derive non-trivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. In recent years, combinatorial pattern matching has developed into a full-fledged area of algorithmics and is expected to grow even further during the next years.

---

Table of contents :
A space efficient algorithm for finding the best non-overlapping alignment score….Pages 1-14
The parameterized complexity of sequence alignment and consensus….Pages 15-30
Computing all suboptimal alignments in linear space….Pages 31-42
Approximation algorithms for multiple sequence alignment….Pages 43-53
A context dependent method for comparing sequences….Pages 54-63
Fast identification of approximately matching substrings….Pages 64-74
Alignment of trees — An alternative to tree edit….Pages 75-86
Parametric recomputing in alignment graphs….Pages 87-101
A lossy data compression based on string matching: Preliminary analysis and suboptimal algorithms….Pages 102-112
A text compression scheme that allows fast searching directly in the compressed file….Pages 113-124
An alphabet-independent optimal parallel search for three dimensional pattern….Pages 125-135
Unit route upper bound for string-matching on hypercube….Pages 136-145
Computation of squares in a string….Pages 146-150
Minimization of sequential transducers….Pages 151-163
Shortest common superstrings for strings of random letters….Pages 164-172
Maximal common subsequences and minimal common supersequences….Pages 173-183
Dictionary-matching on unbounded alphabets: Uniform length dictionaries….Pages 184-197
Proximity matching using fixed-queries trees….Pages 198-212
Query primitives for tree-structured data….Pages 213-225
Multiple matching of parameterized patterns….Pages 226-239
Approximate string matching with don’t care characters….Pages 240-249
Matching with matrix norm minimization….Pages 250-258
Approximate string matching and local similarity….Pages 259-273
Polynomial-time algorithms for computing characteristic strings….Pages 274-288
Recent methods for RNA modeling using stochastic context-free grammars….Pages 289-306
Efficient bounds for oriented chromosome inversion distance….Pages 307-325