Preface | p. vii |
Simple String Search | p. 1 |
Storing a String in an Array | p. 1 |
Brute-Force String Search | p. 2 |
Encoding Strings into Integers | p. 4 |
Sorting k-mer Integers and a Binary Search | p. 7 |
Binary Search for the Boundaries of Blocks | p. 8 |
Sorting | p. 11 |
Insertion Sort | p. 11 |
Merge Sort | p. 12 |
Worst-Case Time Complexity of Algorithms | p. 16 |
Heap Sort | p. 17 |
Randomized Quick Sort | p. 22 |
Improving the Performance of Quick Sort | p. 27 |
Ternary Split Quick Sort | p. 32 |
Radix Sort | p. 33 |
Lookup Tables | p. 39 |
Direct-Address Tables | p. 39 |
Hash Tables | p. 41 |
Table Size | p. 44 |
Using the Frequencies of k-mers | p. 45 |
Techniques for Reducing Table Size | p. 46 |
Suffix Arrays | p. 51 |
Suffix Trees | p. 52 |
Suffix Arrays | p. 54 |
Binary Search of Suffix Arrays for Queries | p. 56 |
Using the Longest Common Prefix Information to Accelerate the Search | p. 58 |
Computing the Longest Common Prefixes | p. 62 |
Application to Occurrence Frequencies of k-mers | p. 65 |
Application to the Longest Common Factors | p. 67 |
Suffix Array Construction - Doubling | p. 68 |
Larsson-Sadakane Algorithm | p. 69 |
Linear-Time Suffix Array Construction | p. 74 |
A Note on Practical Performance | p. 81 |
Space-Efficient String Search | p. 83 |
Rabin-Karp Algorithm | p. 83 |
Accelerating the Brute-Force String Search | p. 86 |
Knuth-Morris-Pratt Algorithm | p. 88 |
Bad Character Heuristics | p. 94 |
Approximate String Search | p. 99 |
Edit Operations and Alignments | p. 101 |
Edit Graphs and Dynamic Programming | p. 103 |
Needleman-Wunsch Algorithm | p. 105 |
Smith-Waterman Algorithm for Computing Local Alignments | p. 108 |
Overlap Alignments | p. 111 |
Alignment of cDNA Sequences with Genomes and Affine Gap Penalties | p. 114 |
Gotoh's Algorithm for Affine Gap Penalties | p. 116 |
Hirschberg's Space Reduction Technique | p. 120 |
Seeded Alignments | p. 125 |
Sensitivity and Specificity | p. 126 |
Computing Sensitivity and Specificity | p. 129 |
Multiple Hits of Seeds | p. 131 |
Gapped Seeds | p. 134 |
Chaining and Comparative Genomics | p. 135 |
Design of Highly Specific Oligomers | p. 141 |
Seeds for Computing Mismatch Tolerance | p. 145 |
Naive Algorithm | p. 145 |
BYP Method | p. 146 |
Partially Matching Seeds | p. 147 |
Overlapping, Partially Matching Seeds | p. 151 |
Whole Genome Shotgun Sequencing | p. 155 |
Sanger Method | p. 156 |
Improvements to the Sequencing Method | p. 159 |
Cloning Genomic DNA Fragments | p. 160 |
Basecalling | p. 163 |
Overview of Shotgun Sequencing | p. 165 |
Lander-Waterman Statistics | p. 170 |
Double-Stranded Assembly | p. 172 |
Overlap-Layout-Consensus | p. 175 |
Overlap | p. 175 |
Layout | p. 177 |
Consensus | p. 180 |
Practical Whole Genome Shotgun Assembly | p. 182 |
Vector Masking | p. 183 |
Quality Trimming | p. 186 |
Contamination Removal | p. 187 |
Overlap and Layout | p. 188 |
Seed and Extend | p. 188 |
Seeding | p. 190 |
Greedy Merging Approach | p. 191 |
Longer Repeat Sequence | p. 192 |
Iterative Improvements | p. 193 |
Accelerating Overlap Detection | p. 194 |
Repeat Sequence Detection | p. 196 |
Error Correction | p. 199 |
Repeat Separation | p. 199 |
Maximal Read Heuristics | p. 201 |
Paired Pair Heuristics | p. 202 |
Parallelization | p. 203 |
Eliminating Chimeric Reads | p. 204 |
Scaffolding | p. 205 |
How Many Mate Pairs Are Needed for Scaffolding? | p. 207 |
Iterative Improvements | p. 208 |
Consensus | p. 210 |
Quality Assessment | p. 211 |
Past and Future | p. 213 |
Software Availability | p. 221 |
Bibliography | p. 223 |
Index | p. 233 |
Table of Contents provided by Ingram. All Rights Reserved. |