Preface xv Introduction 1(6) Algorithms and Complexity 7(50) What Is an Algorithm? 7(7) Biological Algorithms versus Computer Algorithms 14(3) The Change Problem 17(3) Correct versus Incorrect Algorithms 20(4) Recursive Algorithms 24(4) Iterative versus Recursive Algorithms 28(5) Fast versus Slow Algorithms 33(4) Big-O Notation 37(3) Algorithm Design Techniques 40(9) Exhaustive Search 41(1) Branch-and-Bound Algorithms 42(1) Greedy Algorithms 43(1) Dynamic Programming 43(5) Divide-and-Conquer Algorithms 48(1) Machine Learning 48(1) Randomized Algorithms 48(1) Tractable versus Intractable Problems 49(2) Notes 51(3) Biobox: Richard Karp 52(2) Problems 54(3) Molecular Biology Primer 57(26) What Is Life Made Of? 57(2) What Is the Genetic Material? 59(1) What Do Genes Do? 60(1) What Molecule Codes for Genes? 61(1) What Is the Structure of DNA? 61(2) What Carries Information between DNA and Proteins? 63(2) How Are Proteins Made? 65(2) How Can We Analyze DNA? 67(6) Copying DNA 67(4) Cutting and Pasting DNA 71(1) Measuring DNA Length 72(1) Probing DNA 72(1) How Do Individuals of a Species Differ? 73(1) How Do Different Species Differ? 74(1) Why Bioinformatics? 75(8) Biobox: Russell Doolittle 79(4) Exhaustive Search 83(42) Restriction Mapping 83(4) Impractical Restriction Mapping Algorithms 87(2) A Practical Restriction Mapping Algorithm 89(2) Regulatory Motifs in DNA Sequences 91(2) Profiles 93(4) The Motif Finding Problem 97(3) Search Trees 100(8) Finding Motifs 108(3) Finding a Median String 111(3) Notes 114(5) Biobox: Gary Stormo 116(3) Problems 119(6) Greedy Algorithms 125(22) Genome Rearrangements 125(2) Sorting by Reversals 127(4) Approximation Algorithms 131(1) Breakpoints: A Different Face of Greed 132(4) A Greedy Approach to Motif Finding 136(1) Notes 137(6) Biobox: David Sankoff 139(4) Problems 143(4) Dynamic Programming Algorithms 147(80) The Power of DNA Sequence Comparison 147(1) The Change Problem Revisited 148(5) The Manhattan Tourist Problem 153(14) Edit Distance and Alignments 167(5) Longest Common Subsequences 172(5) Global Sequence Alignment 177(1) Scoring Alignments 178(2) Local Sequence Alignment 180(4) Alignment with Gap Penalties 184(1) Multiple Alignment 185(8) Gene Prediction 193(4) Statistical Approaches to Gene Prediction 197(3) Similarity-Based Approaches to Gene Prediction 200(3) Spliced Alignment 203(4) Notes 207(4) Biobox: Michael Waterman 209(2) Problems 211(16) Divide-and-Conquer Algorithms 227(20) Divide-and-Conquer Approach to Sorting 227(3) Space-Efficient Sequence Alignment 230(4) Block Alignment and the Four-Russians Speedup 234(4) Constructing Alignments in Subquadratic Time 238(2) Notes 240(4) Biobox: Webb Miller 241(3) Problems 244(3) Graph Algorithms 247(64) Graphs 247(13) Graphs and Genetics 260(2) DNA Sequencing 262(2) Shortest Superstring Problem 264(1) DNA Arrays as an Alternative Sequencing Technique 265(3) Sequencing by Hybridization 268(3) SBH as a Hamiltonian Path Problem 271(1) SBH as an Eulerian Path Problem 272(3) Fragment Assembly in DNA Sequencing 275(5) Protein Sequencing and Identification 280(4) The Peptide Sequencing Problem 284(3) Spectrum Graphs 287(3) Protein Identification via Database Search 290(2) Spectral Convolution 292(1) Spectral Alignment 293(6) Notes 299(3) Problems 302(9) Combinatorial Pattern Matching 311(28) Repeat Finding 311(2) Hash Tables 313(3) Exact Pattern Matching 316(2) Keyword Trees 318(2) Suffix Trees 320(4) Heuristic Similarity Search Algorithms 324(2) Approximate Pattern Matching 326(4) BLAST: Comparing a Sequence against a Database 330(1) Notes 331(6) Biobox: Gene Myers 333(4) Problems 337(2) Clustering and Trees 339(48) Gene Expression Analysis 339(4) Hierarchical Clustering 343(3) k-Means Clustering 346(2) Clustering and Corrupted Cliques 348(6) Evolutionary Trees 354(4) Distance-Based Tree Reconstruction 358(3) Reconstructing Trees from Additive Matrices 361(5) Evolutionary Trees and Hierarchical Clustering 366(2) Character-Based Tree Reconstruction 368(2) Small Parsimony Problem 370(4) Large Parsimony Problem 374(5) Notes 379(5) Biobox: Ron Shamir 380(4) Problems 384(3) Hidden Markov Models 387(22) CG-Islands and the ``Fair Bet Casino'' 387(3) The Fair Bet Casino and Hidden Markov Models 390(3) Decoding Algorithm 393(4) HMM Parameter Estimation 397(1) Profile HMM Alignment 398(2) Notes 400(7) Biobox: David Haussler 403(4) Problems 407(2) Randomized Algorithms 409(10) The Sorting Problem Revisited 409(3) Gibbs Sampling 412(2) Random Projections 414(2) Notes 416(1) Problems 417(2) Using Bioinformatics Tools 419(2) Bibliography 421(8) Index 429