Scalable De Novo Genome Assembly Using a Pregel-Like Graph-Parallel System
- 5 June 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 18 (2) , 731-744
Abstract
De novo genome assembly is the process of stitching short DNA sequences to generate longer DNA sequences, without using any reference sequence for alignment. It enables high-throughput genome sequencing and thus accelerates the discovery of new genomes. In this paper, we present a toolkit, called PPA-assembler, for de novo genome assembly in a distributed setting. The operations in our toolkit provide strong performance guarantees, and can be assembled to implement various sequencing strategies. PPA-assembler adopts the popular de Bruijn graph based approach for sequencing, and each operation is implemented as a program in Google's Pregel framework which can be easily deployed in a generic cluster. Experiments on large real and simulated datasets demonstrate that PPA-assembler is much more efficient than the state-of-the-arts while providing comparable sequencing quality. PPA-assembler has been open-sourced at https://github.com/yaobaiwei/PPA-Assembler.Keywords
Funding Information
- NSF OAC (1755464)
- NSF DGE (1723250)
- ITF (6904945)
- GRF (14222816)
- NIH/NCATS (U54TR002731)
- NCI/NIH/DHHS (U01CA223976)
- National Institute on Minority Health and Health Disparities (U54MD000502)
- National Human Genome Research Institute (3U01HG007301-06S1)
- AHA (17IF33890015)
This publication has 30 references indexed in Scilit:
- SOAPdenovo2: an empirically improved memory-efficient short-read de novo assemblerGigaScience, 2012
- Exploiting sparseness in de novo genome assemblyBMC Bioinformatics, 2012
- SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell SequencingJournal of Computational Biology, 2012
- ART: a next-generation sequencing read simulatorBioinformatics, 2011
- Efficient de novo assembly of large genomes using compressed data structuresGenome Research, 2011
- GAGE: A critical evaluation of genome assemblies and assembly algorithmsGenome Research, 2011
- Ray: Simultaneous Assembly of Reads from a Mix of High-Throughput Sequencing TechnologiesJournal of Computational Biology, 2010
- ALLPATHS 2: small genomes assembled accurately and with high continuity from short paired readsGenome Biology, 2009
- ABySS: A parallel assembler for short read sequence dataGenome Research, 2009
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008