Projet GATB (Boite à outils « Assemblage pour la Génomique ») | ANR - Agence Nationale de la Recherche Projet ANR | ANR - Agence Nationale de la Recherche

L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

Emergence (Emergence)
Edition 2012


GATB


Boite à outils « Assemblage pour la Génomique »

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 NGS
la 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 Bloom
Une 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é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).

Productions scientifiques 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


Partenaires

INRIA Institut National de la Recherche en Informatique et Automatique

INRIA Institut National de la Recherche en Informatique et Automatique

INRIA Institut National de la Recherche en Informatique et Automatique

Aide de l'ANR 183 372 euros
Début et durée du projet scientifique février 2013 - 24 mois

Résumé de soumission

Depuis quelques années, la génomique est témoin d'un profond changement induit par
les progrès drastiques du séquençage haut débit, également appelé
Next Generation Sequencing (NGS). Ces technologies génèrent d'énormes volumes
de données génomiques. Des développements logiciels critiques sont aujourd'hui
né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 petites
sé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 de
nombreux 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'assemblage
de-novo pour reconstruire un génome complet. Mapseembleur, quant à lui, est un outil
plus général pour le traitement des masses de données génomiques, mais offre
la 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 technologique
vers un large panel de domaines applicatifs (santé, agronomie, environnement, etc.).

 

Programme ANR : Emergence (Emergence) 2012

Référence projet : ANR-12-EMMA-0019

Coordinateur du projet :
Monsieur Dominique LAVENIER (Institut National de la Recherche en Informatique et Automatique )

Site internet du projet : http://gatb.inria.fr

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.