BGREAT: A De Bruijn graph read mapping tool

Antoine Limasset 1 Pierre Peterlongo 1
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Mapping reads on references is a central task in numerous genomic studies. Since references are mainly extracted from assembly graphs, it is of high interest to map efficiently on such structures. The problem of mapping sequences on a De Bruijn graph has been shown NP-complete[1] and no scalable generic tool exists yet. We motivate here the problem of mapping reads on a de Bruijn graph and we present a practical solution and its implementation called BGREAT. BGREAT handles real world instances of billions reads with moderate resources. Mapping on de Bruijn graph enable to keep whole genomic information and get rid off possible assembly mistakes. However the problem is theoretically hard to handle on real-world dataset. Using a set of heuristics, our proposed tool is able to map million read by CPU hours even on complex human genomes. BGREAT is available at github.com/Malfoy/BGREAT [1]Limasset, A., & Peterlongo, P. (2015). Read Mapping on de Bruijn graph. arXiv preprint arXiv:1505.04911. [2]Langmead, Ben, et al. "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biol 10.3 (2009): R25.
Type de document :
Poster
JOBIM 2015, Jul 2015, Clermont ferrant, France
Liste complète des métadonnées

https://hal.inria.fr/hal-01192857
Contributeur : Antoine Limasset <>
Soumis le : jeudi 3 septembre 2015 - 16:51:19
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Annexe

Identifiants

  • HAL Id : hal-01192857, version 1

Citation

Antoine Limasset, Pierre Peterlongo. BGREAT: A De Bruijn graph read mapping tool. JOBIM 2015, Jul 2015, Clermont ferrant, France. 〈hal-01192857〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

121