Paired de Bruijn Graphs: A Novel Approach for Incorporating Mate Pair Information into Genome Assemblers
- 1 November 2011
- journal article
- research article
- Published by Mary Ann Liebert Inc in Journal of Computational Biology
- Vol. 18 (11), 1625-1634
- https://doi.org/10.1089/cmb.2011.0151
Abstract
The recent proliferation of next generation sequencing with short reads has enabled many new experimental opportunities but, at the same time, has raised formidable computational challenges in genome assembly. One of the key advances that has led to an improvement in contig lengths has been mate pairs, which facilitate the assembly of repeating regions. Mate pairs have been algorithmically incorporated into most next generation assemblers as various heuristic post-processing steps to correct the assembly graph or to link contigs into scaffolds. Such methods have allowed the identification of longer contigs than would be possible with single reads; however, they can still fail to resolve complex repeats. Thus, improved methods for incorporating mate pairs will have a strong effect on contig length in the future. Here, we introduce the paired de Bruijn graph, a generalization of the de Bruijn graph that incorporates mate pair information into the graph structure itself instead of analyzing mate pairs at a post-processing step. This graph has the potential to be used in place of the de Bruijn graph in any de Bruijn graph based assembler, maintaining all other assembly steps such as error-correction and repeat resolution. Through assembly results on simulated perfect data, we argue that this can effectively improve the contig sizes in assembly.Keywords
This publication has 21 references indexed in Scilit:
- Assembly of large genomes using second-generation sequencingGenome Research, 2010
- Genome 10K: A Proposal to Obtain Whole-Genome Sequence for 10 000 Vertebrate SpeciesJournal of Heredity, 2009
- ABySS: A parallel assembler for short read sequence dataGenome Research, 2009
- De novo fragment assembly with short mate-paired reads: Does the read length matter?Genome Research, 2008
- Accurate whole human genome sequencing using reversible terminator chemistryNature, 2008
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008
- ALLPATHS: De novo assembly of whole-genome shotgun microreadsGenome Research, 2008
- Short read fragment assembly of bacterial genomesGenome Research, 2007
- A New Algorithm for DNA Sequence AssemblyJournal of Computational Biology, 1995
- Toward Simplifying and Accurately Formulating Fragment AssemblyJournal of Computational Biology, 1995