Implementing de Bruijn graphs compactly is an important problem because of their role in genome assembly. There are currently two main approaches, one using Bloom filters and the other using a kind of Burrows-Wheeler Transform on the edge labels of the graph. The second representation is more elegant and can even handle many graph-orders at once, but it does not cleanly support traversing edges backwards or inserting new nodes or edges. In this paper we resolve the first of these issues and partially address the second.

Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M., Puglisi, S. (2016). Bidirectional variable-order de Bruijn graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.164-178). Heidelberg : Springer Verlag [10.1007/978-3-662-49529-2_13].

Bidirectional variable-order de Bruijn graphs

PREVITALI, MARCO;
2016

Abstract

Implementing de Bruijn graphs compactly is an important problem because of their role in genome assembly. There are currently two main approaches, one using Bloom filters and the other using a kind of Burrows-Wheeler Transform on the edge labels of the graph. The second representation is more elegant and can even handle many graph-orders at once, but it does not cleanly support traversing edges backwards or inserting new nodes or edges. In this paper we resolve the first of these issues and partially address the second.
paper
Computer Science (all); Theoretical Computer Science
English
Latin American Symposium on Theoretical Informatics, LATIN 11-15 April
2016
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
9783662495285
2016
9644
164
178
http://springerlink.com/content/0302-9743/copyright/2005/
none
Belazzougui, D., Gagie, T., Mäkinen, V., Previtali, M., Puglisi, S. (2016). Bidirectional variable-order de Bruijn graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.164-178). Heidelberg : Springer Verlag [10.1007/978-3-662-49529-2_13].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/112969
Citazioni
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
Social impact