Contents......Page 3
Notation......Page 10
Preface......Page 14
Preliminaries......Page 20
DNA, RNA, proteins......Page 21
Genetic variations......Page 24
High-throughput sequencing......Page 25
Complexity analysis......Page 28
Data representations......Page 30
Reductions......Page 31
Literature......Page 35
Dynamic range minimum queries......Page 38
Bitvector rank and select operations......Page 40
Wavelet tree......Page 42
Literature......Page 45
Directed acyclic graphs (DAGs)......Page 48
Arbitrary directed graphs......Page 51
Literature......Page 56
Flows and their decompositions......Page 59
Minimum-cost flowsand circulations......Page 63
Bipartite matching problems......Page 69
Covering problems......Page 76
Literature......Page 82
Fundamentals of Biological Sequence Analysis......Page 86
Alignments......Page 87
Edit distance......Page 88
Longest common subsequence......Page 99
Approximate string matching......Page 102
Biological sequence alignment......Page 104
Gene alignment......Page 114
Multiple alignment......Page 117
Literature......Page 124
Hidden Markov Models (HMMs)......Page 129
Definitionand basic problems......Page 130
The forward and backward algorithms......Page 134
Estimating HMM parameters......Page 136
Literature......Page 138
Genome-Scale Index Structures......Page 142
-mer index......Page 143
Suffixarray......Page 146
Suffixtree......Page 154
Applications of the suffixtree......Page 159
Literature......Page 165
Burrows–Wheeler indexes......Page 171
Burrows–Wheeler transform (BWT)......Page 172
BWT index......Page 174
9.3 Space-efficientconstruction of the BWT......Page 180
Bidirectional BWT index......Page 185
9.5 BWT index for labeled trees......Page 191
9.6 BWT index for labeled DAGs......Page 196
BWT indexes for de Bruijn graphs......Page 202
Literature......Page 208
Genome-Scale Algorithms......Page 213
Read alignment......Page 214
Pattern partitioning......Page 215
Backtracking on BWT indexes......Page 217
Suffixfltering for approximate overlaps......Page 222
Paired-end and mate pair reads......Page 224
Split alignment of reads......Page 225
Alignment of reads to a pan-genome......Page 227
Literature......Page 229
Genome analysis & comparison......Page 233
Space-efficientgenome analysis......Page 234
Comparing genomes without alignment......Page 242
Literature......Page 268
Genome compression......Page 275
Lempel–Ziv parsing......Page 276
12.2 Bit-optimal Lempel–Ziv compression......Page 283
Literature......Page 292
Sequencing by hybridization......Page 295
Contig assembly......Page 297
Scaffolding......Page 304
Gap fillin......Page 310
Literature......Page 312
Applications......Page 318
Genomics......Page 319
Variation calling......Page 320
Variation calling over pan-genomes......Page 325
Haplotype assembly and phasing......Page 327
Literature......Page 334
Estimating the expression of annotated transcripts......Page 337
Transcript assembly......Page 341
Simultaneous assembly and expression estimation......Page 349
Transcript alignment with co-linear chaining......Page 354
Literature......Page 357
Metagenomics......Page 362
Species estimation......Page 363
Read clustering......Page 369
Comparing metagenomic samples......Page 376
Literature......Page 378
Refs......Page 382
Index......Page 398