product iamge

Combinatorial Pattern Matching: 15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 5-7, 2004. Proceedings

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

This book constitutes the refereed proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, held in Istanbul, Turkey in July 2004.

The 36 revised full papers presented were carefully reviewed and selected from 79 submissions. The papers are devoted to current theoretical and computational aspects of searching and matching of strings and more complicate patterns, such as trees, regular expressions, graphs, point sets, and arrays. Among the application fields addressed are computational biology, bioinformatics, genomics, proteinomics, the web, data compression, coding, multimedia, information retrieval, data analysis, pattern recognition, and computer vision.

Author(s): Eric Tannier, Marie-France Sagot (auth.), Suleyman Cenk Sahinalp, S. Muthukrishnan, Ugur Dogrusoz (eds.)
Series: Lecture Notes in Computer Science 3109
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004

Language: English
Pages: 492
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Discrete Mathematics in Computer Science; Information Storage and Retrieval; Document Preparation and Text Processing; Pattern Recognition

Front Matter....Pages -
Sorting by Reversals in Subquadratic Time....Pages 1-13
Computational Problems in Perfect Phylogeny Haplotyping: Xor-Genotypes and Tag SNPs....Pages 14-31
Sorting by Length-Weighted Reversals: Dealing with Signs and Circularity....Pages 32-46
Optimizing Multiple Spaced Seeds for Homology Search....Pages 47-58
Approximate Labelled Subtree Homeomorphism....Pages 59-73
On the Average Sequence Complexity....Pages 74-88
Approximate Point Set Pattern Matching on Sequences and Planes....Pages 89-101
Finding Biclusters by Random Projections....Pages 102-116
Real-Time String Matching in Sublinear Space....Pages 117-129
On the k -Closest Substring and k -Consensus Pattern Problems....Pages 130-144
A Trie-Based Approach for Compacting Automata....Pages 145-158
A Simple Optimal Representation for Balanced Parentheses....Pages 159-172
Two Algorithms for LCS Consecutive Suffix Alignment....Pages 173-193
Efficient Algorithms for Finding Submasses in Weighted Strings....Pages 194-204
Maximum Agreement and Compatible Supertrees....Pages 205-219
Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem....Pages 220-229
Small Phylogeny Problem: Character Evolution Trees....Pages 230-243
The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices....Pages 244-253
A Computational Model for RNA Multiple Structural Alignment....Pages 254-269
Computational Design of New and Recombinant Selenoproteins....Pages 270-284
A Combinatorial Shape Matching Algorithm for Rigid Protein Docking....Pages 285-296
Multi-seed Lossless Filtration....Pages 297-310
New Results for the 2-Interval Pattern Problem....Pages 311-322
A Linear-Time Algorithm for Computing Translocation Distance between Signed Genomes....Pages 323-332
Sparse Normalized Local Alignment....Pages 333-346
Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences....Pages 347-358
Maximal Common Connected Sets of Interval Graphs....Pages 359-372
Performing Local Similarity Searches with Variable Length Seeds....Pages 373-387
Reversal Distance without Hurdles and Fortresses....Pages 388-399
A Fast Set Intersection Algorithm for Sorted Sequences....Pages 400-408
Faster Two Dimensional Pattern Matching with Rotations....Pages 409-419
Compressed Compact Suffix Arrays....Pages 420-433
Approximate String Matching Using Compressed Suffix Arrays....Pages 434-444
Compressed Index for a Dynamic Collection of Texts....Pages 445-456
Improved Single and Multiple Approximate String Matching....Pages 457-471
Average-Case Analysis of Approximate Trie Search....Pages 472-483
Back Matter....Pages -