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

✍ Scribed by Veli Mäkinen et al.

• Publisher: Cambridge University Press
• Year: 2015
• Tongue: English
• Leaves: 413
• Category: Library

✦ Synopsis

High-throughput sequencing has revolutionised the field of biological sequence analysis. Its application has enabled researchers to address important biological questions, often for the first time. This book provides an integrated presentation of the fundamental algorithms and data structures that power modern sequence analysis workflows. The topics covered range from the foundations of biological sequence analysis (alignments and hidden Markov models), to classical index structures (k-mer indexes, suffix arrays and suffix trees), Burrows–Wheeler indexes, graph algorithms and a number of advanced omics applications. The chapters feature numerous examples, algorithm visualisations, exercises and problems, each chosen to reflect the steps of large-scale sequencing projects, including read alignment, variant calling, haplotyping, fragment assembly, alignment-free genome comparison, transcript prediction and analysis of metagenomic samples. Each biological problem is accompanied by precise formulations, providing graduate students and researchers in bioinformatics and computer science with a powerful toolkit for the emerging applications of high-throughput sequencing.

Provides an integrated picture of the fundamental algorithms and data structures that power modern sequence analysis, covering a range of topics including foundations, classical index structures and Burrows–Wheeler indexes
Chapters feature numerous examples, algorithm visualisations, problems and end-of-chapter exercises, providing students with a powerful toolkit for the emerging applications of high-throughput sequencing
Presents only the minimum data structures necessary so that students are not burdened with technical results and can also focus on more conceptual algorithm design questions

✦ Table of Contents

Frontmatter
pp i-iv

Contents
pp v-x

Miscellaneous Frontmatter
pp xi-xi
https://doi.org/10.1017/CBO9781139940023.001

Notation
pp xii-xvi

Preface
pp xvii-xxii
https://doi.org/10.1017/CBO9781139940023.002

Part I - Preliminaries
pp 1-2

1 - Molecular biology and high-throughput sequencing
pp 3-9
https://doi.org/10.1017/CBO9781139940023.003

2 - Algorithm design
pp 10-19
https://doi.org/10.1017/CBO9781139940023.004

3 - Data structures
pp 20-29
https://doi.org/10.1017/CBO9781139940023.005

4 - Graphs
pp 30-40
https://doi.org/10.1017/CBO9781139940023.006

5 - Network flows
pp 41-68
https://doi.org/10.1017/CBO9781139940023.007

Part II - Fundamentals of Biological Sequence Analysis
pp 69-70

6 - Alignments
pp 71-112
https://doi.org/10.1017/CBO9781139940023.008

7 - Hidden Markov models (HMMs)
pp 113-126
https://doi.org/10.1017/CBO9781139940023.009

Part III - Genome-Scale Index Structures
pp 127-128

8 - Classical indexes
pp 129-156
https://doi.org/10.1017/CBO9781139940023.010

9 - Burrows–Wheeler indexes
pp 157-198
https://doi.org/10.1017/CBO9781139940023.011

Part IV - Genome-Scale Algorithms
pp 199-200

10 - Read alignment
pp 201-219
https://doi.org/10.1017/CBO9781139940023.012

11 - Genome analysis and comparison
pp 220-261
https://doi.org/10.1017/CBO9781139940023.013

12 - Genome compression
pp 262-281
https://doi.org/10.1017/CBO9781139940023.014

13 - Fragment assembly
pp 282-304
https://doi.org/10.1017/CBO9781139940023.015

Part V - Applications
pp 305-306

14 - Genomics
pp 307-324
https://doi.org/10.1017/CBO9781139940023.016

15 - Transcriptomics
pp 325-349
https://doi.org/10.1017/CBO9781139940023.017

16 - Metagenomics
pp 350-369
https://doi.org/10.1017/CBO9781139940023.018

References
pp 370-385
https://doi.org/10.1017/CBO9781139940023.019

Index
pp 386-391