Linking indexing data structures to de Bruijn graphs: Construction and update

Bastien Cazaux 1, 2 Thierry Lecroq 3 Eric Rivals 2, 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 TIBS - LITIS - Equipe Traitement de l'information en Biologie Santé
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : DNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent putative DNA segments. In a dBG of order k, nodes are substrings of length k of reads (or k-mers), while arcs are their k + 1-mers. As analysing reads often require to index all their substrings, it is interesting to exhibit algorithms that directly build a dBG from a pre-existing index, and especially a contracted dBG, where non-branching paths are condensed into single nodes. Here, we exhibit linear time algorithms for constructing the full or contracted dBGs from suffix trees, suffix arrays, and truncated suffix trees. With the latter the construction uses a space that is linear in the size of the dBG. Finally, we also provide algorithms to dynamically update the order of the graph without reconstructing it.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01617207
Contributor : Eric Rivals <>
Submitted on : Monday, October 16, 2017 - 1:31:08 PM
Last modification on : Tuesday, July 9, 2019 - 2:44:33 PM
Long-term archiving on : Wednesday, January 17, 2018 - 12:52:18 PM

File

Cazaux-etal-JCSS-16-temp.pdf
Files produced by the author(s)

Identifiers

Citation

Bastien Cazaux, Thierry Lecroq, Eric Rivals. Linking indexing data structures to de Bruijn graphs: Construction and update. Journal of Computer and System Sciences, Elsevier, 2019, 104, pp.165-183. ⟨10.1016/j.jcss.2016.06.008⟩. ⟨lirmm-01617207⟩

Share

Metrics

Record views

685

Files downloads

155