From Sequences to Graphs

Annie Chateau is a lecturer at the University of Montpellier, France. Her research interests include algorithms and combinatorial structures. Mikaël Salson is a lecturer at the University of Lille, France. His work focuses mainly on indexing and sequence comparison.

Preface xi

Author Biographies xvii

Chapter 1 Methodological Concepts: Algorithmic Solutions of Bioinformatics Problems 1
Annie CHATEAU and Tom DAVOT-GRANGÉ

1.1 Data, Models, Problem Formalism in Bioinformatics 1

1.1.1 Data 1

1.1.2 Genome Modeling 4

1.1.3 Problems in Bioinformatics 5

1.2 Mathematical Preliminaries 6

1.2.1 Propositional Logic Preliminaries 6

1.2.2 Preliminaries on Sets 7

1.3 Vocabulary in Text Algorithmics 9

1.4 Graph Theory 10

1.4.1 Subgraphs 12

1.4.2 Path in a Graph 13

1.4.3 Matching 13

1.4.4 Planarity 14

1.4.5 Tree Decomposition 15

1.5 Algorithmic Problems 16

1.5.1 Definition 16

1.5.2 Graph Problem 17

1.5.3 Satisfiability Problems 19

1.6 Problem Solutions 20

1.6.1 Algorithm 20

1.6.2 Complexity 21

1.6.3 Runtime 24

1.7 Complexity Classes 26

1.7.1 Generality 26

1.7.2 Exact Algorithms 28

1.7.3 Approximation Algorithms 32

1.7.4 Solvers 34

1.8 Some Algorithmic Techniques 35

1.8.1 Dynamic Programming 35

1.8.2 Tree Traversal 38

1.9 Validation 41

1.9.1 The Different Types of Errors 42

1.9.2 Quality Measures 44

1.9.3 And in the Non-Binary Case? 46

1.10 Conclusion 47

1.11 References 47

Chapter 2 Sequence Indexing 49
Thierry LECROQ and Mikaël SALSON

2.1 Introduction 49

2.1.1 What is Indexing? 50

2.1.2 When to Index? 51

2.1.3 What to Index? 51

2.1.4 Indexing Structures and Queries Considered 52

2.1.5 Basic Notions and Vocabulary 53

2.2 Word Indexing 54

2.2.1 Bloom Filters 54

2.2.2 Inverted List 56

2.2.3 De Bruijn Graphs 60

2.2.4 Efficient Structures for Targeted Queries 61

2.3 Full-Text Indexing 62

2.3.1 Suffix Tree 62

2.3.2 (Extended) Suffix Array 64

2.3.3 Burrows–Wheeler Transform 67

2.4 Indexing Choice Criteria 76

2.4.1 Based on the Type of the Necessary Query 77

2.4.2 Based on the Space-Time and Data Quantity Trade-Off 77

2.4.3 Based on the Need to Add or Modify Indexed Data 79

2.4.4 Indexing Choices According to Applications 80

2.5 Conclusion and Perspectives 81

2.5.1 Efficient Methods for Indexing a Few Genomes or Sequencing Sets 81

2.5.2 Methods that Struggle to Take Advantage of Data Redundancy 82

2.6 References 83

Chapter 3 Sequence Alignment 87
Laurent NOÉ

3.1 Introduction 87

3.1.1 What is Pairwise Alignment? 87

3.1.2 How to Evaluate an Alignment? 88

3.2 Exact Alignment 90

3.2.1 Representation in Edit Graph Form 90

3.2.2 Global Alignment and Needleman–Wunsch Algorithm 93

3.2.3 Local Alignment and Smith–Waterman Algorithm 94

3.2.4 Alignment with Affine Indel Function and the Gotoh Algorithm 96

3.3 Heuristic Alignment 98

3.3.1 Seeds 99

3.3.2 Min-Hash and Global Sampling 105

3.3.3 Minimizing and Local Sampling 106

3.4 References 109

Chapter 4 Genome Assembly 113
Dominique LAVENIER

4.1 Introduction 113

4.2 Sequencing Technologies 116

4.2.1 Short Reads 117

4.2.2 Long Reads 118

4.2.3 Linked Reads 118

4.2.4 Hi-C Reads 119

4.2.5 Optical Mapping 119

4.3 Assembly Strategies 120

4.3.1 The Main Steps 120

4.3.2 Cleaning and Correction of Reads 121

4.3.3 Scaffold Construction 122

4.3.4 Scaffold Ordering 123

4.4 Scaffold Construction Methods 124

4.4.1 Greedy Assembly 124

4.4.2 OLC Assembly 126

4.4.3 DBG Assembly 127

4.4.4 Constrained Assembly 130

4.5 Scaffold-Ordering Methods 132

4.5.1 Hi-C Data-Based Methods 132

4.5.2 Optical Mapping-Based Methods 137

4.6 Assembly Validation 139

4.6.1 Metrics 140

4.6.2 Read Realignment 140

4.6.3 Gene Prediction 141

4.6.4 Competitions 141

4.7 Conclusion 142

4.8 References 143

Chapter 5 Metagenomics and Metatranscriptomics 147
Cervin GUYOMAR and Claire LEMAITRE

5.1 What is Metagenomics? 147

5.1.1 Motivations and Historical Context 147

5.1.2 The Metagenomics Data 148

5.1.3 Bioinformatics Challenges for Metagenomics 151

5.2 “Who Are They”: Taxonomic Characterization of Microbial Communities 153

5.2.1 Methods for Targeted Metagenomics 154

5.2.2 Whole-Genome Methods with Reference 155

5.2.3 Reference-Free Methods 160

5.3 “What Are They Able To Do?”: Functional Metagenomics 166

5.3.1 Gene Prediction and Annotation 166

5.3.2 Metatranscriptomics 167

5.3.3 Reconstruction of Metabolic Networks 168

5.4 Comparative Metagenomics 169

5.4.1 Comparative Metagenomics with Diversity Estimation 170

5.4.2 De Novo Comparative Metagenomics 170

5.5 Conclusion 175

5.6 References 176

Chapter 6 RNA Folding 185
Yann PONTY And Vladimir REINHARZ

6.1 Introduction 185

6.1.1 RNA Folding 186

6.1.2 Secondary Structure 189

6.2 Optimization for Structure Prediction 192

6.2.1 Computing the Minimum Free-Energy (MFE) Structure 192

6.2.2 Listing (Sub)optimal Structures 198

6.2.3 Comparative Prediction: Simultaneous Alignment/Folding of RNAs 203

6.2.4 Joint Alignment/Folding Model 204

6.3 Analyzing the Boltzmann Ensemble 210

6.3.1 Computing the Partition Function 210

6.3.2 Statistical Sampling 215

6.3.3 Boltzmann Probability of Structural Patterns 220

6.4 Studying RNA Structure in Practice 225

6.4.1 The Turner Model 225

6.4.2 Tools 228

6.5 References 228

Conclusion 233

List of Authors 237

Index 239