Baeza-Yates, Ricardo, Chávez, Edgar, Crochemore, Maxime (Eds.)
2003, XI, 401 p.
Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.
You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.
After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.
The papers contained in this volume were presented at the 14th Annual Sym- sium on Combinatorial Pattern Matching, held June 25–27, 2003 at the Centro Cultural Universitario of the Universidad Michoacana, in Morelia, Michoac´ an, Mexico. They were selected from 57 abstracts submitted in response to the call for papers. In addition, there were invited lectures by Vladimir Levenshtein, from the University of Bergen, Norway, and Ian Munro, from the University of Waterloo, Canada. Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated patterns such as trees, regular expres- ons, graphs, point sets, and arrays, in various formats. The goal is to derive n- trivialcombinatorialpropertiesofsuchstructuresandtoexploittheseproperties in order to achieve superior performance for the corresponding computational problems. Another important goal is to analyze and pinpoint the properties and conditions under which searches cannot be performed e?ciently. Over the past decade a steady ?ow of high quality-research on this subject haschangedasparsesetofisolatedresultsintoafull-?edgedareaofalgorithmics. This area is continuing to grow even further due to the increasing demand for speed and e?ciency that stems from important applications such as the World Wide Web, computational biology, computer vision, and multimedia systems. These involve requirements for information retrieval in heterogeneous databases, datacompression,andpatternrecognition.TheobjectiveoftheannualCPM- theringistoprovideaninternationalforumforresearchincombinatorialpattern matching and related applications.
Multiple Genome Alignment: Chaining Algorithms Revisited.- Two-Dimensional Pattern Matching with Rotations.- An Improved Algorithm for Generalized Comparison of Minisatellites.- Optimal Spaced Seeds for Hidden Markov Models, with Application to Homologous Coding Regions.- Fast Lightweight Suffix Array Construction and Checking.- Distributed and Paged Suffix Trees for Large Genetic Databases.- Analysis of Tree Edit Distance Algorithms.- An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees.- Average-Optimal Multiple Approximate String Matching.- Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms.- Haplotype Inference by Pure Parsimony.- A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions.- Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals.- Linear-Time Construction of Suffix Arrays.- Space Efficient Linear Time Construction of Suffix Arrays.- Tuning String Matching for Huge Pattern Sets.- Sparse LCS Common Substring Alignment.- On Minimizing Pattern Splitting in Multi-track String Matching.- Alignment between Two Multiple Alignments.- An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum.- Pattern Discovery in RNA Secondary Structure Using Affix Trees.- More Efficient Left-to-Right Pattern Matching in Non-sequential Equational Programs.- Complexities of the Centre and Median String Problems.- Extracting Approximate Patterns.- A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression.- Constrained Tree Inclusion.- Working on the Problem of Sorting by Transpositions on Genome Rearrangements.- Efficient Selection of Unique and Popular Oligos for Large EST Databases.