Des séquences aux graphes

Ce chapitre aborde les notions théoriques préliminaires à la lecture des chapitres suivants. Il revient notamment sur la logique, l'algorithmique du texte, les graphes, la notion de classification des problèmes et la complexité algorithmique. Y sont abordés également des problématiques liées à la nature de la bioinformatique, comme la nature des données, et la validation des méthodologies.

Ce chapitre présente un mode d'emploi sur l'indexation des séquences, en mettant l'accent sur les structures de données utilisées pour réaliser cette indexation. Ainsi les tables de hachages, filtres de Bloom, graphes de De Bruijn sont abordés pour l'indexation de mots, et les arbres des suffixes, table des suffixes ou encore transformée de Burrows-Wheeler sont décrits pour l'indexation de textes.

Les différentes facettes de l'alignement deux-à-deux des séquences font l'objet de ce chapitre. On y aborde l'alignement exact avec les algorithmes de Needleman-Wunsch, Smith-Waterman et Gotoh, ainsi que l'alignement heuristique, à travers les algorithmes à graines et les heuristiques d'échantillonnage global (min-hash) ou local (minimizer).

Ce chapitre présente l'assemblage de génomes, entre la présentation des différentes données de séquençage, la description des différentes stratégies de construction des scaffolds (glouton, overlap-layout-consensus, graphes de De Bruijn, contraintes), leur ordonnancement et jusqu'à la validation des assemblages.

Ce chapitre propose une étude de la métagénomique, en présentant les méthodes répondant à la question de l'identification des organismes présents dans des communautés microbiennes, avec ou sans références, ainsi qu'à la détermination de l'aspect fonctionnel (métatranscriptomique, inférence de réseaux métaboliques) ou encore à la comparaison d'échantillons métagénomiques.

Focalisé sur les séquences d'ARN, ce chapitre présente les méthodes d'inférence des repliements en structure secondaire. Il s'intéresse d'une part aux approches d'optimisation (énergie minimale), et d'autre part aux approches ensemblistes et probabilistes, et enfin au modèle de Turner s'intéressant aux motifs, avant d'aborder les différentes implémentations de ces modèles.