Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Cover; Half-title; Title; Copyright; Dedication; Contents; Preface; I Exact String Matching: The Fundamental String Problem; 1 Exact Matching: Fundamental Preprocessing and First Algorithms; 1.1 The naive method; 1.1.1. Early ideas for speeding up the naive method; 1.2 The preprocessing approach; 1.3 Fundamental preprocessing of the pattern; 1.4 Fundamental preprocessing in linear time; The Z algorithm; 1.5 The simplest linear-time exact matching algorithm; 1.5.1. Why continue?; 1.6 Exercises; …
Read More ↓Title Statements
- Full title :Algorithms on Strings, Trees and Sequences : Computer Science and Computational Biology.
Summary
Cover; Half-title; Title; Copyright; Dedication; Contents; Preface; I Exact String Matching: The Fundamental String Problem; 1 Exact Matching: Fundamental Preprocessing and First Algorithms; 1.1 The naive method; 1.1.1. Early ideas for speeding up the naive method; 1.2 The preprocessing approach; 1.3 Fundamental preprocessing of the pattern; 1.4 Fundamental preprocessing in linear time; The Z algorithm; 1.5 The simplest linear-time exact matching algorithm; 1.5.1. Why continue?; 1.6 Exercises; A digression on circular strings in DNA; 2 Exact Matching: Classical Comparison-Based Methods.
2.1 Introduction2.2 The Boyer-Moore Algorithm; 2.2.1. Right-to-left scan; 2.2.2. Bad character rule; 2.2.3. The (strong) good suffix rule; 2.2.4. Preprocessing for the good suffix rule; 2.2.5. The good suffix rule in the search stage of Boyer-Moore; 2.2.6. The complete Boyer-Moore algorithm; 2.3 The Knuth-Morris-Pratt algorithm; 2.3.1. The Knuth-Morris-Pratt shift idea; The Knuth-Morris-Pratt shift rule; 2.3.2. Preprocessing for Knuth-Morris-Pratt; 2.3.3. A full implementation of Knuth-Morris-Pratt; 2.4 Real-time string matching; 2.4.1. Converting Knuth-Morris-Pratt to a real-time method.
2.4.2. Preprocessing for real-time string matching2.5 Exercises; 3 Exact Matching: A Deeper Look at Classical Methods; 3.1 A Boyer-Moore variant with a ""simple"" linear time bound; 3.1.1. Key ideas; 3.1.2. One phase in detail; 3.1.3. Correctness and linear-time analysi; 3.2 Cole's linear worst-case bound for Boyer-Moore; 3.2.1. Cole's proof when the pattern does not occur in the text; 3.2.2. The case when the pattern does occur in the text; 3.2.3. Adding in the bad character rule; 3.3 The original preprocessing for Knuth-Morris-Pratt; 3.3.1. The method does not use fundamental preprocessing.
3.3.2. The easy case3.3.3. The general case; 3.3.4. How to compute the optimized shift values; 3.4 Exact matching with a set of patterns; 3.4.1. Naive use of keyword trees for set matching; 3.4.2. The speedup: generalizing Knuth-Morris-Pratt; 3.4.3. Failure functions for the keyword tree; 3.4.4. The failure links speed up the search; 3.4.5. Linear preprocessing for the failure function; 3.4.6. The full Aho-Corasick algorithm: relaxing the substring assumption; 3.5 Three applications of exact set matching; 3.5.1. Matching against a DNA or protein library of known patterns.
3.5.2. Exact matching with wild cards3.5.3. Two-dimensional exact matching; 3.6 Regular expression pattern matching; 3.6.1. Formal definitions; 3.7 Exercises; 4 Seminumerical String Matching; 4.1 Arithmetic versus comparison-based methods; 4.2 The Shift-And method; 4.2.1. How to construct array M; 4.2.2. Shift-And is effective for small patterns; 4.2.3. agrep: The Shift-And method with errors; 4.2.4. How to compute Mk; 4.3 The match-count problem and Fast Fourier Transform; 4.3.1. A fast worst-case method for the match-count problem?; 4.3.2. Using Fast Fourier Transform for match-counts.
4.4 Karp-Rabin fingerprint methods for exact match.
This 1997 book describes a range of string problems in computer science and molecular biology and the algorithms developed to solve them.
Edition Statements
- Publication Date:1997.
- Edition:Online-ausg
Publication Statements
- Publisher(s):Cambridge University Press
- Place of Publication:Cambridge
- Language:eng
- Publication Date:1997.
The Physical Object
- Description:Online-Ressource (1 online resource (554 Seiten))
Edition Identifiers
- ISBN:9781139811484, 1139811487, 9780521585194, 0521585198, 9780511574931, 0511574932
- DOI:10.1017/CBO9780511574931
- oclc:ocn830954786
- LC Classification:QA76.9.A43 G87 1997
- Dewey Decimal:005.1
Subjects
Writers
More from this Series
No reviews yet. Be the first to rate this work.
Related Works
more →
Bioinformatics: a computing perspective
Bioinformatics: a computing perspective
Bioinformatics: a computing perspective
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biol…
Gusfield, Dan
Algorithms on strings, trees, and sequences: computer science and computational biol…
Gusfield, Dan
Computer-aided drug design
Rate & Review