Scaling metagenome sequence assembly with probabilistic de Bruijn graphs

DOI10.1073/pnas.1121464109zbMath1256.68052arXiv1112.4193OpenAlexW2163830511WikidataQ36170818 ScholiaQ36170818MaRDI QIDQ4907496

Arend Hintze, Rosangela Canino-Koning, Adina Howe, Jason Pell, James M. Tiedje, C. Titus Brown

Publication date: 2 February 2013

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.4193

zbMATH Keywords

deep sequencingcomplex populations\(k\)-mer connectivitymemory-efficient graph representation

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Genetics and epigenetics (92D10) Data structures (68P05) Computational methods for problems pertaining to biology (92-08)

Related Items (7)

An external-memory algorithm for string graph construction ⋮ Bloom Filter Trie – A Data Structure for Pan-Genome Storage ⋮ Wavelet analysis on symbolic sequences and two-fold de Bruijn sequences ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ The Contig Assembly Problem and Its Algorithmic Solutions ⋮ Improving MinHash via the containment index with applications to metagenomic analysis ⋮ A tale of optimizing the space taken by de Bruijn graphs

Uses Software

• ALLPATHS
• GAGE

Cites Work

• Unnamed Item
• An Eulerian path approach to DNA fragment assembly
• Network Applications of Bloom Filters: A Survey
• Evolutionary Bioinformatics
• Space/time trade-offs in hash coding with allowable errors

This page was built for publication: Scaling metagenome sequence assembly with probabilistic de Bruijn graphs