A new algorithm for de novo genome assembly

Summary

A new overlap graph based genome assembler called Paired-End Genome ASsembly Using Short-sequences (PEGASUS) for paired-end short reads produced by NGS techniques, which exhibits comparable and in many cases better performance than the leading genome assemblers.

Keywords

De Bruijn graph, Sequence assembly, Genome, Hybrid genome assembly, k-mer

References

ALLPATHS: de novo assembly of whole-genome shotgun microreads.Van Loenen, Berry Leanne — 2008
An efficient implementation of a scaling minimum-cost flow algorithmAndrew V. Goldberg — 1993
Large-scale genome sequence processing雅弘笠原, 真一森下 — 2006
Exact and approximation algorithms for DNA sequence reconstructionJohn Kececioglu — 1992
A whole-genome assembly of Drosophila.Eugene W. Myers, Granger G. Sutton, Art L. Delcher — 2000
A new method of sequencing DNA.Edward David Hyman — 1988
Amplification of complex gene libraries by emulsion PCRRichard Williams, Sergio G. Peisajovich, Oliver J. Miller — 2006
Suffix arrays: a new method for on-line string searchesUdi Manber, Gene Myers — 1993
Toward Simplifying and Accurately Formulating Fragment AssemblyEugene W. Myers — 1995
Linguistics of nucleotide sequences. II: Stationary words in genetic texts and the zonal structure of DNA.Pavel A. Pevzner, Mark Borodovsky, Anrey A. Mironov — 1989
Real-time DNA sequencing using detection of pyrophosphate release.Mostafa Ronaghi, Samer Karamohamed, Bertil Pettersson — 1996
An efficient reduction technique for degree-constrained subgraph and bidirected network flow problemsHarold N. Gabow — 1983
Lightweight Data Indexing and Compression in External MemoryPaolo Ferragina, Travis Gagie, Giovanni Manzini — 2009
The Human Genome Project: Lessons from Large-Scale BiologyFrancis S. Collins, Michael J. Morgan, A.A.N. Patrinos — 2003
A New Algorithm for DNA Sequence AssemblyRamana M. Idury, Michael S. Waterman — 1995
Automated DNA sequencing of the human HPRT locus.Al Edwards, Hartmut Voss, Peter Rice — 1990
De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer.David Hernández, Patrice François, Laurent Farinelli — 2008
Single-molecule sequencing of an individual human genomeDmitry Pushkarev, Norma Neff, Stephen R. Quake — 2009
Maximum Likelihood Genome AssemblyPaul Medvedev, Michael Brudno — 2009
A new approach to fragment assembly in DNA sequencingPavel A. Pevzner, Haixu Tang, Michael S. Waterman — 2001

Cited by

Omega: an Overlap-graph de novo Assembler for MetagenomicsBahlul Haider, Tae-Hyuk Ahn, Brian Bushnell — 2014
Error Correction and de novo Genome Assembly of DNA Sequencing DataMichael Molnar — 2017

Related papers

De novo assembly methods for next generation sequencing dataYiming He, Zhen Zhang, Xiaoqing Peng — 2013
Paired de Bruijn Graphs: A Novel Approach for Incorporating Mate Pair Information into Genome AssemblersPaul Medvedev, Son Pham, Mark Chaisson — 2011
Empirical evaluation of methods for de novo genome assemblyFiraol Dida, Gangman Yi — 2021
Efficient algorithms for sequence assemblySanguthevar Rajasekaran, Subrata Saha — 2013
De Bruijn Graph-Based Whole-Genomic Sequence Assembly Algorithms and ApplicationsXiaojun Kang, Shanyu Tang, Yongge Ma — 2013
Clover: a clustering-oriented de novo assembler for Illumina sequencesMing-Feng Hsieh, Chin Lung Lu, Chuan Yi Tang — 2020
Effective Utilization of Paired Reads to Improve Length and Accuracy of Contigs in Genome AssemblyRahul Nihalani, Srinivas Aluru — 2016
Next generation sequencing under de novo genome assemblySonia Farhana Nimmy, Md. Sarwar Kamal — 2015
Assembly Algorithms for Next-Generation Sequencing DataJason Miller, Sergey Koren, Granger Sutton — 2010
Ray: Simultaneous Assembly of Reads from a Mix of High-Throughput Sequencing TechnologiesSébastien Boisvert, François Laviolette, Jacques Corbeil — 2010