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 gener
Algorithms on Strings, Trees, and sequences 3 Algorithms on Strings, Trees, and sequences COMPUTER SCIENCE AND COMPUTATIONAL BIOLOGY Dan gusfield University of California, Davis EEF CAMBRIDGE 吸罗 UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi, Dubai, Tokyo, Mexico City Cambridge University Press The edinburgh building, Cambridge CB2 RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Informationonthistitlewww.cambridge.org/9780521585194 C) Dan Gusfield 1997 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collecti licensing agreements, no reproduction of any part may take place without the written permission of cambridge University Press First publshed 1997 a catalogue record for this publication is available from the British library Library of Congress Cataloguing-in-Publication data field. D Algorithms on strings, trees, and sequences computer science and computational biology /Dan Gusfield cm ISBN0-521-58519-8(hc) 1. Computer algorithms. 2. Molecular biology Data processing I. Title s、QA769433871997 73-dc21 86-46612 IsBN 978-0-521-58519-4 Ilardback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third- party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Information regarding prices, travel timetables, and other factual information given in this work are correct at the time of first printing but Cambridge University Press does not guarantee the accuracy of such information thereafter. Dedicated to the memory of Gene lawler: Teacher, Colleague, and friend Contents Preface I Exact String Matching: The Fundamental String Problem 1 Exact Matching: Fundamental Preprocessing and First Algorithms 1.1 The naive method 1.2 The preprocessing approach 1.3 Fundamental preprocessing of the pattern 1.4 Fundamental preprocessing in linear time 1. 5 The simplest linear-time exact matching algorithm 1.6 Exercises 2 Exact Matching: Classical Comparison-Based Methods 2.1 Introduction 2.2 The boyer-Moore Algorithm 2.3 The Knuth-Morris-Pratt algorithm 2.4 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.2 Cole's linear worst-case bound for boyer-Moore 3.3 The original preprocessing for Knuth-Morris-Pratt 3.4 Exact matching with a set of patterns 3.5 Three applications of exact set matching 3.6 Regular expression pattern matchin 3.7 Exercises 4 Seminumerical string matching 4.1 Arithmetic versus comparison-based methods 4. 2 The Shift-And method 4.3 The match-count problem and Fast Fourier Trans form 4.4 Karp-Rabin fingerprint methods for exact match 4.5 Exercises I 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.2 Weiner's linear-time suffix tree algorithm 6.3 Mc Creight's suffix tree algorithm 6. 4 Generalized suffix tree for a set of strings 6.5 Practical implementation issues 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.3 APL3 The substring problem for a database of patterns 7.4 APLA: Longest common substring of two strings 7.5 APL5: Recognizing dNa contamination 7.6 APL6: Common substrings of more than two strings 7.7 APL7: Building a smaller directed graph for exact matching 7.8 APLg: A reverse role for suffix trees, and major space reduction 7.9 APL9: Space-efficient longest common substring algorithm 7.10 APL10: All-pairs suffix-prefix matching 7.11 Introduction to repetitive structures in molecular strings 7.12 APLll: Finding all maximal repetitive structures in linear time 7.13 APL12: Circular string linearization 7.14 APL13: Suffix arrays- more space reduction 7.15 APL14: Suffix trees in genome-scale projects 7.16 APL15: A Boyer-Moore approach to exact set matching 7.17 APL16: Ziv-Lempel data compression 7.18 APLI7: Minimum length encoding of DNA 7.19 Additional applications 7. 20 Exercises 8 Constant-Time Lowest Common Ancestor retrieval 8 8.1 Introduction 8.2 The assumed machine model 8.3 Complete binary trees: a very simple case 8.4 How to solve lca queries in B 8.5 First steps in mapping T to B 8.6 The mapping of T to 3 8.7 The linear-time preprocessing ofT 8.8 Answering an lca query in constant time 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.2 Finding all maximal palindromes in linear time 9.3 Exact matching with wild cards 9. 4 The k-mismatch problem 9.5 Approximate palindromes and repeats 9.6 Faster methods for tandem repeats 9.7 A linear-time solution to the multiple common substring problem 9.8 Exercises Il Inexact Matching, Sequence Alignment, Dynamic Programming 10 The Importance of (Sub)sequence Comparison in Molecular Biology 11 Core String Edits, Alignments, and Dynamic Programming 11.1 Introduction 11.2 The edit distance between two stri 1.3 Dynamic programming calculation of edit distance 11.4 Edit graphs 11.5 Weighted edit distance 11.6 String similarit 11.7 Local alignment: finding substrings of high similarity 11.8 Gaps 11.9 Exercises 12 Refining Core String Edits and Alignments 12.1 Computing alignments in only linear space 12.2 Faster algorithms when the number of differences are bounded 12.3 Exclusion methods: fast expected running time 12. 4 Yet more suffix trees and more hybrid dynamic programming 12.5 A faster(combinatorial)algorithm for longest common subsequence 12.6 Convex gap weights 12.7 The Four-Russians speedup 12. 8 Exercises 13 Extending the core problems 13.1 Parametric sequence alignment 13.2 Computing suboptimal alignments 13. 3 Chaining diverse local alignments 13. 4 Exercises 4 Multiple String Comparison- The Holy grail 14.1 Why multiple string comparison? 14.2 Three big-picture"biological uses for multiple string comparison 14.3 Family and superfamily representation 14.4 Multiple sequence comparison for structural inference 14.5 Introduction to computing multiple string alignments 14.6 Multiple alignment with the sum-of-pairs(sp)objective function 14.7 Multiple alignment with consensus objective functions 14.8 Multiple alignment to a (phylogenetic)tree 14.9 Comments on bounded-error approximations 14.10 Common multiple alignment methods 14.11 Exercises 15 Sequence Databases and Their Uses- The mother lode 15.1 Success stories of database search 15.2 The database industr 15.3 Algorithmic issues in database search 15.4 Real sequence database search 15.5 FASTA 15.6 BLAST 15.7 PAM: the first major amino acid substitution matrices 15. 8 PROSITE 15.9 BLOCKS and BLOSUM 15.10 The blosUM substitution matrices 15.11 Additional considerations for database searching 10