Projet ANR-12-EMMA-0019 – GATB : Boite à outils « Assemblage pour la Génomique »
Programme : Emergence (Emergence)
Année de financement : 2012
Coordinateur du projet : Monsieur Dominique LAVENIER (Institut National de la Recherche en Informatique et Automatique )
Partenaires : Inria Centre Paris - Rocquencourt; Institut national de recherche en informatique et en automatique; Institut national de recherche en informatique et en automatique
Montant : 183372.0 euros
Durée : 24 mois
Résumé : Boite à Outils «Assemblage et Analyse pour la génomique«La génomique est confrontée à un changement sans précédent suite au nouvelles technologies de séquençage à haut débit car celles-ci génèrent d'énormes volumes de données. Le projet GATB vise les traitements critiques ou des milliards de courts fragments d'ADN doivent être traités, conduisant à des temps de calculs importants sur des machines possédant de grosses mémoires vives. Cela constitue un sérieux handicap pour bon nombre d'analyses, tant d'un point de vue académique qu'industriel.
Conception rapide et efficace de logiciels NGSla boite à outils «Assemblage et Analyse pour la génomique« a pour but de proposer une méthode de conception rapide pour développer facilement des outils de traitement des données génomiques. le projet GATB a été architecturé autour d'une librairie C++ de fonctions de haut niveau qui intègrent les avancées récentes relatives aux structures de données NGS. L'environnement GATB offre:1 - Une librairie «open-source« à partir de laquelle de nouveaux outils NGS peuvent être créés facielement et rapidement;2 - Des fonctions optimisées avec une empreinte mémoire très faible. A titre d'exemple, l'assemblage d'un génome humain demande moins de 6 Giga octets de mémoire alors que des logiciels concurrents peuvent demander plusieurs centaines de Go.3 - une implémentation parallèle et transparente visant les processeurs multi-coeurs qui représentent aujourd'hui les principales ressources matérielles
Une structure de graphe optimisée basée sur le flitre de BloomUne des préoccupation majeure de la librairie GATB est de proposer des modules capables de tourner sur des machines standard, c'est à dire des ordinateurs ayant des taille raisonnable de mémoire vive.La structure de données centrale est le graphe de de-Bruijn à partir duquel de nombreuses actions peuvent être mises en œuvre: correction d'erreur, assemblage, détection de motifs (ex: SNP), etc. Le graphe est construit en extrayant et en comptant les différents K-mers des jeux de données NGS,La construction couteuse en temps et en mémoire est effectuée par une algorithme efficace (disk streaming) qui adapte l'organisation des données en fonction de la taille mémoire disponible. Un compromis entre temps d'exécution et taille mémoire est alors mis en place: plus on dispose d'espace mémoire, plus le calcul est rapide.L'empreinte mémoire du graphe de de-Bruijn est réduite grâce à une représentation optimisée via un filtre de Bloom. Seuls les nœuds du graphe sont mémorisés. Les arêtes sont déduites par interrogation du filtre de Bloom. Les faux positifs (dus au comportement probabiliste du filtre de Bloom) sont supprimées en ajoutant une (petite) structures de données supplémentaire qui énumères les arêtes critiques. Cette représentation extrêmement efficace permet, par exemple, de mémoriser le graphe complet d'un génome humain en moins de 6 Go.
Résumé de la soumission : Depuis quelques années, la génomique est témoin d'un profond changement induit parles progrès drastiques du séquençage haut débit, également appelé Next Generation Sequencing (NGS). Ces technologies génèrent d'énormes volumesde données génomiques. Des développements logiciels critiques sont aujourd'huinécessaires pour extraire des connaissances à partir de ces masses de données.Le projet GATB se focalise sur un traitement bien spécifique : l'assemblage.Ce dernier consiste à reconstruire le texte d'un génome à partir d'un ensemble de petitesséquences d'ADN ou d'ARN, appelées read, générées par les séquenceurs NGS.Pour des génomes complexes, des milliards de read doivent être ordonnés,ce qui conduit à des temps de calcul exorbitants et  demande des ordinateurséauipés de très grosses mémoires. C'est un goulot d'étranglement important pour denombreux traitements, tant pour le milieu académique qu'industriel.L'équipe de recherche GenScale/INRIA développe des outils d'assemblage innovants,rapides et à faible empreinte mémoire. Deux prototypes, Monument et Mapsembler, ontété développés comme "preuve de concept". Monument est spécialisé dans l'assemblagede-novo pour reconstruire un génome complet. Mapseembleur, quant à lui, est un outilplus général pour le traitement des masses de données génomiques, mais offrela possibilité d'assembler des régions spécifiques d'un génome.Dans ce projet, nous proposons de développer une boite à outils "assemblage"pour permettre aux utilisateurs de customiser leur processus d'assemblage en fonction(1) de la nature des données produites par les séquenceurs; (2) de la complexité des génomes à assembler; (3) de la question biologique posée. L'objectif final est de préparer un transfert technologiquevers un large panel de domaines applicatifs (santé, agronomie, environnement, etc.).
Résultats : Plus généralement, le projet GATB a été construit suivant une architecture à 3 niveaux :
GATB-core: une librairie C++ qui donne access à tous les services indispensable pour construire de nouveaux outisl de traitemenet de données NGS. Cette librairie est disponible en open source et diffusé à la communauté scientifique
GATB-TOOLS: un ensemble d'outils élémentaires construits sur la base de la librairie C++. Pendant le projet, les outils suivants ont été développés :
 - Minia: contigueur
 - DSK: compteur de k-mers
 - Bloocoo: correcteur de reads
 - TakeABreak: inversion de  breakpoint
 - Leon: compresseur de reads
 - DicoSNP: détection de SNPs
-  MindTheGap: assemblage et détection d'insertions
-  Mapseembler2: assemblage ciblé
Tous ces outils sont disponibles à partir du site web GATB
GATB-PIPELINE: un ensemble de pipelines de traitements complexes qui lient les outils du niveau précédent.
Perspectives : La boite à outils GATB offre aujourd'hui une technologie de pointe pour développer des logiciels pour le traitement des données de séquençage haut débit, notamment pour l'exploitation de fragments courts. A moyen terme, il s'agit de la faire évoluer vers les nouvelles technologies de séquençage qui produisent de longs fragments.
Le bibliothèque GATB-core est disponible auprès des académiques et des industriels sous une licence A-GPL. Un projet de start-up pour exploiter cette technologie est en cours (printemps 2015).
Publications et brevets : E. Drezen, G. Rizk, R. Chikhi, C. Deltel, C. Lemaitre, P. Peterlongo, D. Lavenier, GATB: Genome Assembly & Analysis Tool Box, Bioinformatics, 2014
    G. Rizk, A. Goin, R. Chikhi, C. Lemaitre, MindTheGap : integrated detection and assembly of short and long insertions, Bioinformatics, August 2014
    G. Rizk, D. Lavenier, R. Chikhi, DSK: k-mer counting with very low memory usage, Bioinformatics, 2013 Mar 1;29(5):652-3
    R. Chikhi, G. Rizk. Space-efficient and exact de Bruijn graph representation based on a Bloom filter, Algorithms for Molecular Biology 2013, 8:22
    G. Collet, G. Rizk, R. Chikhi, D. Lavenier, Minia on Raspberry Pi, assembling a 100 Mbp genome on a Credit Card Sized Computer, Poster at the JOBIM conference, 2013 Jul 1-4 (Toulouse) Best poster award.
    K.l Salikhov, G. Sacomoto, G. Kucherov, Using Cascading Bloom Filters to Improve the Memory Usage for de Brujin Graphs, Algorithms in Bioinformatics, Lecture Notes in Computer Science, Volume 8126, 2013, pp 364-376