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 xiAuthor Biographies xviiChapter 1 Methodological Concepts: Algorithmic Solutions of Bioinformatics Problems 1Annie CHATEAU and Tom DAVOT-GRANGÉ1.1 Data, Models, Problem Formalism in Bioinformatics 11.1.1 Data 11.1.2 Genome Modeling 41.1.3 Problems in Bioinformatics 51.2 Mathematical Preliminaries 61.2.1 Propositional Logic Preliminaries 61.2.2 Preliminaries on Sets 71.3 Vocabulary in Text Algorithmics 91.4 Graph Theory 101.4.1 Subgraphs 121.4.2 Path in a Graph 131.4.3 Matching 131.4.4 Planarity 141.4.5 Tree Decomposition 151.5 Algorithmic Problems 161.5.1 Definition 161.5.2 Graph Problem 171.5.3 Satisfiability Problems 191.6 Problem Solutions 201.6.1 Algorithm 201.6.2 Complexity 211.6.3 Runtime 241.7 Complexity Classes 261.7.1 Generality 261.7.2 Exact Algorithms 281.7.3 Approximation Algorithms 321.7.4 Solvers 341.8 Some Algorithmic Techniques 351.8.1 Dynamic Programming 351.8.2 Tree Traversal 381.9 Validation 411.9.1 The Different Types of Errors 421.9.2 Quality Measures 441.9.3 And in the Non-Binary Case? 461.10 Conclusion 471.11 References 47Chapter 2 Sequence Indexing 49Thierry LECROQ and Mikaël SALSON2.1 Introduction 492.1.1 What is Indexing? 502.1.2 When to Index? 512.1.3 What to Index? 512.1.4 Indexing Structures and Queries Considered 522.1.5 Basic Notions and Vocabulary 532.2 Word Indexing 542.2.1 Bloom Filters 542.2.2 Inverted List 562.2.3 De Bruijn Graphs 602.2.4 Efficient Structures for Targeted Queries 612.3 Full-Text Indexing 622.3.1 Suffix Tree 622.3.2 (Extended) Suffix Array 642.3.3 Burrows–Wheeler Transform 672.4 Indexing Choice Criteria 762.4.1 Based on the Type of the Necessary Query 772.4.2 Based on the Space-Time and Data Quantity Trade-Off 772.4.3 Based on the Need to Add or Modify Indexed Data 792.4.4 Indexing Choices According to Applications 802.5 Conclusion and Perspectives 812.5.1 Efficient Methods for Indexing a Few Genomes or Sequencing Sets 812.5.2 Methods that Struggle to Take Advantage of Data Redundancy 822.6 References 83Chapter 3 Sequence Alignment 87Laurent NOÉ3.1 Introduction 873.1.1 What is Pairwise Alignment? 873.1.2 How to Evaluate an Alignment? 883.2 Exact Alignment 903.2.1 Representation in Edit Graph Form 903.2.2 Global Alignment and Needleman–Wunsch Algorithm 933.2.3 Local Alignment and Smith–Waterman Algorithm 943.2.4 Alignment with Affine Indel Function and the Gotoh Algorithm 963.3 Heuristic Alignment 983.3.1 Seeds 993.3.2 Min-Hash and Global Sampling 1053.3.3 Minimizing and Local Sampling 1063.4 References 109Chapter 4 Genome Assembly 113Dominique LAVENIER4.1 Introduction 1134.2 Sequencing Technologies 1164.2.1 Short Reads 1174.2.2 Long Reads 1184.2.3 Linked Reads 1184.2.4 Hi-C Reads 1194.2.5 Optical Mapping 1194.3 Assembly Strategies 1204.3.1 The Main Steps 1204.3.2 Cleaning and Correction of Reads 1214.3.3 Scaffold Construction 1224.3.4 Scaffold Ordering 1234.4 Scaffold Construction Methods 1244.4.1 Greedy Assembly 1244.4.2 OLC Assembly 1264.4.3 DBG Assembly 1274.4.4 Constrained Assembly 1304.5 Scaffold-Ordering Methods 1324.5.1 Hi-C Data-Based Methods 1324.5.2 Optical Mapping-Based Methods 1374.6 Assembly Validation 1394.6.1 Metrics 1404.6.2 Read Realignment 1404.6.3 Gene Prediction 1414.6.4 Competitions 1414.7 Conclusion 1424.8 References 143Chapter 5 Metagenomics and Metatranscriptomics 147Cervin GUYOMAR and Claire LEMAITRE5.1 What is Metagenomics? 1475.1.1 Motivations and Historical Context 1475.1.2 The Metagenomics Data 1485.1.3 Bioinformatics Challenges for Metagenomics 1515.2 “Who Are They”: Taxonomic Characterization of Microbial Communities 1535.2.1 Methods for Targeted Metagenomics 1545.2.2 Whole-Genome Methods with Reference 1555.2.3 Reference-Free Methods 1605.3 “What Are They Able To Do?”: Functional Metagenomics 1665.3.1 Gene Prediction and Annotation 1665.3.2 Metatranscriptomics 1675.3.3 Reconstruction of Metabolic Networks 1685.4 Comparative Metagenomics 1695.4.1 Comparative Metagenomics with Diversity Estimation 1705.4.2 De Novo Comparative Metagenomics 1705.5 Conclusion 1755.6 References 176Chapter 6 RNA Folding 185Yann PONTY And Vladimir REINHARZ6.1 Introduction 1856.1.1 RNA Folding 1866.1.2 Secondary Structure 1896.2 Optimization for Structure Prediction 1926.2.1 Computing the Minimum Free-Energy (MFE) Structure 1926.2.2 Listing (Sub)optimal Structures 1986.2.3 Comparative Prediction: Simultaneous Alignment/Folding of RNAs 2036.2.4 Joint Alignment/Folding Model 2046.3 Analyzing the Boltzmann Ensemble 2106.3.1 Computing the Partition Function 2106.3.2 Statistical Sampling 2156.3.3 Boltzmann Probability of Structural Patterns 2206.4 Studying RNA Structure in Practice 2256.4.1 The Turner Model 2256.4.2 Tools 2286.5 References 228Conclusion 233List of Authors 237Index 239