Genome-Scale Algorithm Design. Biological Sequence Analysis in the Era of High-Throughput Sequencing

Description

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