Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology

Traditionally an area of study in computer science, string algorithms have, in recent years, become an increasingly important part of biology, particularly genetics. This volume is a comprehensive look at computer algorithms for string processing. In addition to pure computer science, Gusfield adds extensive discussions on biological problems that are cast as string problems and on methods developed to solve them. This text emphasizes the fundamental ideas and techniques central to today's applications. New approaches to this complex material simplify methods that up to now have been for the specialist alone. With over 400 exercises to reinforce the material and develop additional topics, the book is suitable as a text for graduate or advanced undergraduate students in computer science, computational biology, or bio-informatics. Contents Preface PART 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 patter 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. Introduction 2.2. The Boyer-Moore Algorithm 2.2.1. Right-to-left scan 2.2.2. Bad character rule Extended bad character rule Implementing the extended bad character rule 2.2.3. The (strong) good suffix rule 2.2.4. Preprocessing for the good suffix rule .2.5. The good suffix rule in the search stage of Boyer-Moore 2.2.6. The complete Boyer-Moore algorith 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 matching 2.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 Phase algorithm 3.1.3. Correctness and linear-time analysis 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 case 3.3.3. The general case 3.3.4. How to compute the optimized shift value 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 cards 3.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 4.4.1. Arithmetic replaces comparisons 4.4.2. Fingerprints of P and T 4.4.3. Why fingerprints? 4.5. Exercise PART II Suffix Trees and Their Uses 5 Introduction to Suffix Trees 5.1. A short history 5.2. Basic definitions 5.3. A motivating example 5.4. A naive algorithm to build a suffix tree 6 Linear-Time Construction of Suffix Trees 6.1. Ukkonen's linear-time suffix tree algorithm 6.1.1. Implicit suffix trees 6.1.2. Ukkonen's algorithm at a high level 6.1.3. Implementation and speedup 6.1.4. A simple implementation detail 6.1.5. Two more little tricks and we're done 6.1.6. Creating the true suffix tree 6.2. Weiner's linearMtime suffix tree algorithm 6.2.1. A straightforward construction 6.2.2. Toward a more efficient implementation 623 The basic idea of Weiner's algorithm 6.2.4. The full algorithm for creating Ti from Ti+1 Correctness How to update the vectors 6.2.5. Time analysis of Weiner's algorithm 6.2.6. Last comments about Weiner's algorithm 6.3. McCreight's suffix tree algorithm 6.4. Generalized suffix tree for a set of strings 6.5. Practical implementation issues 6.5.1. Alphabet independence: all linears are equal, but some are more equal than others 6.6. Exercises 7 First Applications of Suffix Trees 7.1. APLl: Exact string matching 7.2. APL2: Suffix trees and the exact set matching problem 7.2.1. Comparing suffix trees and keyword treesfor exact set matching 7.3. APL3: The substring problem for a database of patterns 7.4. APL4: Longest common substring of two strings 7.5. APLS: Recognizing DNA contamination 7 .6. APL6: Common substrings of more than two strings Formal problem statement and first method 7.6.1. Computing the C(v) numbers 7.7. APL7: Building a smaller directed graph for exact matching 7.8. APL8: A reverse role for suffix trees, and major space reduction 7.8.1. Matching statistics: duplicating bounds and reducing space 7.8.2. Correctness and time analysis for matching statistics 7.8.3. A small but important extension 7.9. APL9: Space-efficient longest common substring algorithm 7.10. APLlO: All-pairs suffix-prefix matching 7.10.1. Solving the all-pairs suffix-prefix problem in linear time 7.11. Introduction to repetitive structures in molecular strings 7.11.1. Repetitive structures in biological strings 7.11.2. Uses of repetitive structures in molecular biolog 7.12. APLll: Finding all maximal repetitive structures in linear time 7.12.1. A linear-time algorithm to find all maximal repeats 7 .12 .2 . Finding supennaximal repeats in linear time 7.12.3. Finding all the maximal pairs in linear time 7.13. APL12: Circular string linearization 7.13.1. Solution via suffix trees 7.14. APL13: Suffix arrays- more space reduction 7.14.1. Suffix tree to suffix array in linear time 7.14.2. How to search for a pattern using a suffix array 7.14.3. A simple accelerant 7.14.4. A super-accelerant 7.14.5. How to obtain the Lcp values 7.14.6. Where do large alphabet problems arise? 7.15. APL14: Suffix trees in genome-scale projects 7.16. APL15: A Boyer-Moore approach to exact set matching 7.16.1. The search 7.16.2 . Bad character rule 7.16.3. Good suffix rule 7.16.4. How to determine i2 and i3 7.16.5. An implementation eliminating redundancy 7.17. APL16: Ziv-Lempel data compression 7.17.1. Implementation using suffix trees 7.17.2. A one-pass version 7.17.3. The real Ziv-Lempel 7.18. APL17: Minimum length encoding of DNA 7.19. Additional applications 7 .20. Exercises 8 Constant-Time Lowest Common Ancestor Retrieval 8.1. Introduction 8.1.1. What do ancestors have to do with strings? 8.2. The assumed machine model 8.3. Complete binary trees: a very simple case 8.4. How to solve lea queries in 1 8.5. First steps in mapping T to 1 8.6. The mapping ofT to 1 8.7. The linear-time preprocessing of T What is this crazy mapping doing? 8.8. Answering an lea query in constant time How to find the height of /(z) 8.9. The binary tree is only conceptual 8.10. For the purists: how to avoid bit-level operations 8.11. Exercises 9 More Applications of Suffix Trees 9.1. Longest common extension: a bridge to inexact matching 9.1.1. Linear-time solution 9.1.2. Space-efficient longest common extension 9.2. Finding all maximal palindromes in linear time 9.2.1. Linear-time solution 9.2.2. Complemented and separated palindromes 9.3. Exact matching with wild cards 9.4. The k-mismatch problem 9.4.1. The solution 9.5. Approximate palindromes and repeats 9.6. Faster methods for tandem repeats 9.6.1. The speedup fork-mismatch tandem repeats 9.7. A linear-time solution to the multiple common substring problem 9.7.1. The method 9.7.2. Time analysis 9.7.3. Related uses 9.8. Exercises PART III Inexact Matching, Sequence Alignment, and Dynamic Programming 10The Importance of (Sub)sequence Comparison in Molecular Biology The first fact of biological sequence analysis 11Core String Edits, Alignments, and Dynamic Programming 11.1. Introduction 11.2. The edit distance between two strings 11.2.1. String alignment 11.3. Dynamic programming calculation of edit distance 11.3.1. The recurrence relation 11.3.2. Tabular computation of edit distance 11.3.3. The traceback 11.4. Edit graphs 11.5. Weighted edit distance 11.5.1. Operation weights 11.5.2. Alphabet-weight edit distance 11.6. String similarity 11.6.1. Computing similarity 11.6.2. Special cases of similarity 11.6.3. Alignment graphs for similarity 11.6.4. End-space free variant 11.6.5. Approximate occu.rrences of P in T 11.7. Local alignment: finding substrings of high similarity 11.7.1. Computing local alignment 11.7.2. How to solve the local suffix alignment problem 11.7.3. Three final comments on local alignment Terminology for local and global alignment 11.8. Gaps 11.8.1. Introduction to Gaps 11.8.2. Why gaps? 11.8.3. eDNA matching: a concrete illustration 11.8.4. Choices for gap weights 11.8.5. Arbitrary gap weights 11.8.6. Affine (and constant) gap weights 11.9. Exercises 12 Refining Core String Edits and Alignments 12.1. Computing alignments in only linear space 12.1.1. Space reduction for computing similarity 12.1.2. How to find the optimal alignment in linear space 12.1.3. The full idea: use recursion 12.1.4. Time analysis 12.1.5. Extension to local alignment 12.2. Faster algorithms when the number of differences is bounded 12.2.1. Where do bounded difference problems arise? 12.2.2. Illustrations from molecular biolog 12.2.3. k-difference global alignment 12.2.4. The return of the suffix tree: k-difference inexact matching 12.2.5. The primer (and probe) selection problem revisited- An application of bounded difference matching 12.3. Exclusion methods: fast expected running time 12.3.1. The BYP method 12.3.2. Expected time analysis of algorithm BYP 12.3.3. The Chang-Lawler method 12.3.4. Multiple filtration fork-mismatches 12.3.5. Myers's sublinear-time method 12.3.6. Final comment on exclusion methods 12.4. Yet more suffix trees and more hybrid dynamic programmi 12.4.1. The P-against-all problem 12.4.2. The (threshold) all-against-all problem 12.5. A faster (combinatorial) algorithm for longest common subsequence 12.5.1. Longest increasing subsequence 12.5.2. Longest common subsequence reduces to longest increasing subsequence 12.5.3. How good is the method 12.5.4. The lcs of more than two strings 12.6. Convex gap weights 12.6.1. Forward dynamic programming 12.6.2. The basis of the speedup 12.6.3. Cell pointers and row partition 12.6.4. Final implementation details and time analysis 12.7. The Four-Russians speedup 12.7.1. t -blocks 12.7.2. The Four-Russians idea for the restricted block function 12.7.3. The trick: offset encoding 12.7.4. Practical approaches 12.8. Exercises 13 Extending the Core Problems 13.1. Parametric sequence alignment 13.1.1. Introduction 13.1.2. Definitions and first results 13.1.3. Parametric alignment with the use of scoring matrices 13.1.4. Efficient algorithms for computing a polygonal decomposition 13.1.5. Time analysis and the next idea 13.1.6. Bounding the number of polygons in the decomposition 13.1.7. Uses for parametric alignment 13.2. Computing suboptimal alignments 13.2.1. First definitions and first results 13.2.2. A useful reweighting 13.2.3. Counting and enumerating near-optimal paths 13.2.4. An alternative approach to suboptimal alignment 13.3. Chaining diverse local alignments 13.4. Exercises 14 Multiple String Comparison - The Holy Grail 14.1. Why multiple string comparison? 14.1.1. Biological basis for multiple string comparison 14.2. Three "big-picture" biological uses for multiple string comparison 14.3. Family and superfamily representation 14.3.1. Family representations and alignments with profiles 14.3.2. Signature representations of families 14.4. Multiple sequence comparison for structural inference 14.5. Introduction to computing multiple string alignments 14.5.1. How to score multiple alignments 14.6. Multiple alignment with the sum-of-pairs (SP) objective function 14.6.1. An exact solution to the SP alignment problem 14.6.2. A bounded-error approximation method for SP alignment 14.6.3. Weighted SP alignment 14.7. Multiple alignment with consensus objective functions 14.7.1. Steiner consensus strings 14.7.2. Consensus strings from multiple alignment 14.7.3. Approximating the optimal consensus multiple alignment 14.8. Multiple alignment to a (phylogenetic) tree 14.8.1. A heuristic for phylogenetic alignment 14.9. Comments on bounded-error approximations 14.10. Common multiple alignment methods 14.10.1. Iterative pairwise alignment 14.10.2. Two specific illustrations of iterative pairwise alignment 14.10.3. Repeated-motif methods 14.10.4. Two newer approaches to multiple string comparison 14.11. Exercises 15 Sequence Databases and Their Uses- The Mother Lode 15.1. Success stories of database search 15.1.1. The first success story 15.1.2. A more recent example of successful database search 15.1.3. Indirect applications of database search 15.2. The database industry 15.3. Algorithmic issues in database searc 15.3.1. Should there be any? 15.4. Real sequence database search 15.5. FASTA 15.6. BLAST 15.6.1. The hit (hot-spot) strategy of BLAST 15.6.2. The effectiveness of BLAST 15.7. PAM: the first major amino acid substitution matrices 15.7.1. PAM units and PAM matrices 15.7.2. PAM units 15.7.3. PAM matrices 15.7.4. How are PAM matrices actually derived? 15.7.5. The use of the PAM matr 15.8. PROSITE 15.9. BLOCKS and BLOSUM 15.10. The BLOSUM substitution matrices 15.11. Additional considerations for database searching 15.11.1. Statistical significance 15.11.2. A theory of log-odds scores 15.11.3. Importance of searching protein with protein 15.12. Exercises PART IV Currents, Cousins, and Cameos 16 Maps, Mapping, Sequencing, and Superstrings 16.1. A look at some DNA mapping and sequencing problems 16.2. Mapping and the genome project 16.3. Physical versus genetic maps 16.4. Physical mapping 16.5. Physical mapping: STS-content mapping and ordered clone libraries 16.5.1. Reconstruction of STS order 16.6. Physical mapping: radiation-hybrid mapping 16.6.1. Reconstruction of STS order in radiation hybrids 16.6.2. Traveling salesman formulation of STS ordering 16.6.3. Back to STS-content mapping: the case of errors 16.7. Physical mapping: fingerprinting for general map construction 16.8. Computing the tightest layout 16.9. Physical mapping: last comments Pooling 16.10. An introduction to map alignment 16.10.1. A nonunary dynamic programming approach to map alignment 16.10.2. Extensions of the map alignment model 16.11. Large-scale sequencing and sequence assembly 16.12. Directed sequencing 16.13. Top-down, bottom-up sequencing: the picture using YACs 16.13.1. Is mapping necessary for sequencing? 16.13.2. Fragment selection for sequencing 16.13.3. Some real numbers 16.14. Shotgun DNA sequencing 16.15. Sequence assembly 16.15.1. Step one: overlap detection 16.15.2. Step two: substring layout 16.15.3. Step three: deciding the consensus 16.16. Final comments on top-down, bottom-up sequencing 16.17. The shortest superstring problem 16.17.1. Introduction to superstrings 16.17.2. The objective function for superstrings 16.17.3. Cyclic strings and cycle covers 16.17.4. How cycle covers define superstrings 16.17.5. Factor-of-four approximation 16.17.6. Improvement to a factor of three 16.17.7. Efficient implementation 16.18. Sequencing by hybridization 16.18.1. Reduction to Euler paths 16.18.2. Continuity of compatible strings 16.18.3. Last comments on SBH 16.19. Exercises 17 Strings and Evolutionary Trees 17.1. Ultrametric trees and ultrametric distances 17.1.1. Introduction 17.1.2. Evolutionary trees as ultrametric trees 17.1.3. How to test for an ultrametric tree 17.1.4. How are ultrametric data obtained? 17.2. Additive-distance tree 17.2.1. Introduction 17.2.2. Algorithms for the additive tree problem 17.3. Parsimony: character-based evolutionary reconstruction 17.3.1. Introduction 17.3.2. Where do character data come from? 17.3.4. An O(nm)-time algorithm for the perfect phylogeny problem 17 .3.5. Tree compatibility: an application of perfect phylogeny 17.3.6. Generalized perfect phylogeny 17.4. The centrality of the ultrametric problem 17.4.1. The additive tree problem viewed as an ultrametric problem 17.4.2. The perfect phylogeny problem viewed as an ultrametric problem 17.5. Maximum parsimony, Steiner trees, and perfect phylogeny 17.5.1. Basic definitions 17.5.2. Approximations to maximum parsimony 17.6. Phylogenetic alignment, again 17.6.1. The Fitch-Hartigan minimum mutation problem 17.6.2. Phylogenetic alignment used to compute PAM matrices 17.7. Connections between multiple alignment and tree construction 17.8. Exercises 18 Three Short Topics 18.1. Matching DNA to protein with frameshift errors 18.1.1. Matching a string to a network 18.1.2. DNA/protein matching cast as network matching 18.2. Gene prediction 18.2.1. Exon assembly 18.3. Molecular computation: computing with (not about)DNA strings 18.3.1. Lipton's approach to the Satisfiability problem 18.3.2. Critique 18.4. Exercises 19 Models of Genome-Level Mutations 19.1. Introduction 19.1.1. Genome rearrangements give new evolutionary insights 19.2. Genome rearrangements with inversions 19.2.1. Definitions and initial facts 19.2.2. The heuristics 19.3. Signed inversions 19.4. Exercises Epilogue - Where Next? Bibliography Glossary Publisher Description (unedited Publisher Data) String Algorithms Are A Traditional Area Of Study In Computer Science. In Recent Years Their Importance Has Grown Dramatically With The Huge Increase Of Electronically Stored Text And Of Molecular Sequence Data (dna Or Protein Sequences) Produced By Various Genome Projects. This Book Is A General Text On Computer Algorithms For String Processing. In Addition To Pure Computer Science, The Book Contains Extensive Discussions On Biological Problems That Are Cast As String Problems, And On Methods Developed To Solve Them. It Emphasises The Fundamental Ideas And Techniques Central To Today's Applications. New Approaches To This Complex Material Simplify Methods That Up To Now Have Been For The Specialist Alone. With Over 400 Exercises To Reinforce The Material And Develop Additional Topics, The Book Is Suitable As A Text For Graduate Or Advanced Undergraduate Students In Computer Science, Computational Biology, Or Bio-informatics. Its Discussion Of Current Algorithms And Techniques Also Makes It A Reference For Professionals. Library Of Congress Subject Headings For This Publication: Computer Algorithms, Bioinformatics, Molecular Biology Data Processing. Exact Matching: Fundamental Preprocessing And First Algorithms -- Exact Matching: Classical Comparison-based Methods -- Exact Matching: A Deeper Look At Classical Methods -- Seminumerical String Matching -- Introduction To Suffix Trees -- Linear-time Construction Of Suffix Trees -- First Applications Of Suffix Trees -- Constant-time Lowest Common Ancestor Retrieval -- More Applications Of Suffix Trees -- The Importance Of (sub)sequence Comparison In Molecular Biology --core String Edits, Alignments, And Dynamic Programming -- Refining Core String Edits And Alignments -- Extending The Core Problems -- Multiple String Comparison -- The Holy Grail -- Sequence Databases And Their Uses- The Mother Lode -- Maps, Mapping, Sequencing, And Superstrings -- Strings And Evolutionary Trees -- Three Short Topics -- Models Of Genome-level Mutations. Dan Gusfield. Includes Bibliographical References (p. 505-523) And Index. String algorithms are a traditional area of study in computer science. In recent years their importance has grown dramatically with the huge increase of electronically stored text and of molecular sequence data (DNA or protein sequences) produced by various genome projects. This 1997 book is a general text on computer algorithms for string processing. In addition to pure computer science, the book contains extensive discussions on biological problems that are cast as string problems, and on methods developed to solve them. It emphasises the fundamental ideas and techniques central to today's applications. New approaches to this complex material simplify methods that up to now have been for the specialist alone. With over 400 exercises to reinforce the material and develop additional topics, the book is suitable as a text for graduate or advanced undergraduate students in computer science, computational biology, or bio-informatics. Its discussion of current algorithms and techniques also makes it a reference for professionals 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 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 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