BGREAT: A De Bruijn graph read mapping tool - Archive ouverte HAL Access content directly
Poster Communications Year :

BGREAT: A De Bruijn graph read mapping tool

(1) , (1)
1

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.
Vignette du fichier
PosterV2.pdf (16.61 Mo) Télécharger le fichier
Format : Poster
Origin : Files produced by the author(s)

Dates and versions

hal-01192857 , version 1 (03-09-2015)

Identifiers

  • HAL Id : hal-01192857 , version 1

Cite

Antoine Limasset, Pierre Peterlongo. BGREAT: A De Bruijn graph read mapping tool. JOBIM 2015, Jul 2015, Clermont ferrant, France. ⟨hal-01192857⟩
246 View
120 Download

Share

Gmail Facebook Twitter LinkedIn More