The papers contained in this volume were presented at the Fourth Annual Symposium on Combinatorial Pattern Matching, held in Padova, Italy, in June 1993. Combinatorial pattern matching addresses issues of searching and matching of strings and more complicated patterns such as trees, regular expressions, extended expressions, etc. The goal is to derive nontrivial 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, a steady flow of high-quality scientific studies of this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. The area is expected to grow even further due to the increasing demand for speedand efficiency that comes especially from molecular biology and the Genome project, but also from other diverse areas such as information retrieval, pattern recognition, compilers, data compression, and program analysis.
Author(s): Tatsuya Akutsu (auth.), Alberto Apostolico, Maxime Crochemore, Zvi Galil, Udi Manber (eds.)
Series: Lecture Notes in Computer Science 684
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1993
Language: English
Pages: 270
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Document Preparation and Text Processing; Information Storage and Retrieval; Coding and Information Theory; Combinatorics
A linear time pattern matching algorithm between a string and a tree....Pages 1-10
Tight comparison bounds for the string prefix-matching problem....Pages 11-19
3-D docking of protein molecules....Pages 20-34
Minimal separators of two words....Pages 35-53
Covering a string....Pages 54-62
On the worst-case behaviour of some approximation algorithms for the shortest common supersequence of k strings....Pages 63-73
An algorithm for locating non-overlapping regions of maximum alignment score....Pages 74-86
Exact and approximation algorithms for the inversion distance between two chromosomes....Pages 87-105
The maximum weight trace problem in multiple sequence alignment....Pages 106-119
An algorithm for approximate tandem repeats....Pages 120-133
Two dimensional pattern matching in a digitized image....Pages 134-151
Analysis of a string edit problem in a probabilistic framework....Pages 152-163
Detecting false matches in string matching algorithms....Pages 164-178
On suboptimal alignments of biological sequences....Pages 179-196
A fast filtration algorithm for the substring matching problem....Pages 197-214
A unifying look at d-dimensional periodicities and space coverings....Pages 215-227
Approximate string-matching over suffix trees....Pages 228-242
Multiple sequence comparison and n -dimensional image reconstruction....Pages 243-253
A new editing based distance between unordered labeled trees....Pages 254-265
