Combinatorial Pattern Matching

1. Front Matter

   PDF

2. A space efficient algorithm for finding the best non-overlapping alignment score

   • Gary Benson

   Pages 1-14

3. The parameterized complexity of sequence alignment and consensus

   • Hans Bodlaender, Rodney G. Downey, Michael R. Fellows, Harold T. Wareham

   Pages 15-30

4. Computing all suboptimal alignments in linear space

   • Kun -Mao Chao

   Pages 31-42

5. Approximation algorithms for multiple sequence alignment

   • Vineet Bafna, Eugene L. Lawler, Pavel A. Pevzner

   Pages 43-53

6. A context dependent method for comparing sequences

   • Xiaoqiu Huang

   Pages 54-63

7. Fast identification of approximately matching substrings

   • Archie L. Cobbs

   Pages 64-74

8. Alignment of trees — An alternative to tree edit

   • Tao Jiang, Lusheng Wang, Kaizhong Zhang

   Pages 75-86

9. Parametric recomputing in alignment graphs

   • Xiaoqiu Huang, Pavel A. Pevzner, Webb Miller

   Pages 87-101

10. A lossy data compression based on string matching: Preliminary analysis and suboptimal algorithms

    • Tomasz Luczak, Wojciech Szpankowski

    Pages 102-112

11. A text compression scheme that allows fast searching directly in the compressed file

    • Udi Manber

    Pages 113-124

12. An alphabet-independent optimal parallel search for three dimensional pattern

    • Marek Karpinski, Wojciech Rytter

    Pages 125-135

13. Unit route upper bound for string-matching on hypercube

    • L. Lestré

    Pages 136-145

14. Computation of squares in a string

    • S. Rao Kosaraju

    Pages 146-150

15. Minimization of sequential transducers

    • Mehryar Mohri

    Pages 151-163

16. Shortest common superstrings for strings of random letters

    • Kenneth S. Alexander

    Pages 164-172

17. Maximal common subsequences and minimal common supersequences

    • Robert W. Irving, Campbell B. Fraser

    Pages 173-183

18. Dictionary-matching on unbounded alphabets: Uniform length dictionaries

    • Dany Breslauer

    Pages 184-197

19. Proximity matching using fixed-queries trees

    • Ricardo Baeza-Yates, Walter Cunto, Udi Manber, Sun Wu

    Pages 198-212

20. Query primitives for tree-structured data

    • Pekka Kilpeläinen, Heikki Mannila

    Pages 213-225

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.

• Data Compression
• Datenkompression
• Folgenanalyse
• Information Retrieval
• Informationsabfrage
• Matching
• Pattern Matching
• Performance
• Sequence Analysis
• String Algorithms
• String-Algorithmen
• algorithmics
• algorithms
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics