DBG2OLC: Efficient Assembly of Large Genomes Using Long Erroneous Reads of the Third Generation Sequencing Technologies

Abstract

The highly anticipated transition from next generation sequencing (NGS) to third generation sequencing (3GS) has been difficult primarily due to high error rates and excessive sequencing cost. The high error rates make the assembly of long erroneous reads of large genomes challenging because existing software solutions are often overwhelmed by error correction tasks. Here we report a hybrid assembly approach that simultaneously utilizes NGS and 3GS data to address both issues. We gain advantages from three general and basic design principles: ( i ) Compact representation of the long reads leads to efficient alignments. ( ii ) Base-level errors can be skipped; structural errors need to be detected and corrected. ( iii ) Structurally correct 3GS reads are assembled and polished. In our implementation, preassembled NGS contigs are used to derive the compact representation of the long reads, motivating an algorithmic conversion from a de Bruijn graph to an overlap graph, the two major assembly paradigms. Moreover, since NGS and 3GS data can compensate for each other, our hybrid assembly approach reduces both of their sequencing requirements. Experiments show that our software is able to assemble mammalian-sized genomes orders of magnitude more quickly than existing methods without consuming a lot of memory, while saving about half of the sequencing cost.

Full text

Its licence does not allow us to show the full text. Read it at PubMed Central:

References 32

1. 1.

   Venter J. C. et al. The sequence of the human genome. Science 291, 1304–1351, doi: (2001 ).

   Not in our library10.1126/science.1058040

2. 2.

   Koren S. et al. Hybrid error correction and de novo assembly of single-molecule sequencing reads. Nature biotechnology 30, 693–700, doi: (2012 ).

   Not in our library10.1038/nbt.2280

3. 3.

   Laver T. et al. Assessing the performance of the Oxford Nanopore Technologies MinION. Biomolecular Detection and Quantification 3, 1–8 (2015 ).

   Not in our library10.1016/j.bdq.2015.02.001

4. 4.

   Pacific Biosciences of California, I. Data Release: ~54x Long-Read Coverage for PacBio-only De Novo Human Genome Assembly, http://www.pacb.com/blog/data-release-54x-long-read-coverage-for (Published: 2014, Date of access: 17/03/2016).

   Not in our library

5. 5.
   Exploiting sparseness in de novo genome assembly · 2012

   No notice
6. 6.

   Koren S. & Phillippy A. M. One chromosome, one contig: complete microbial genomes from long-read sequencing and assembly. Current Opinion in Microbiology 23, 110–120, doi: (2015 ).

   Not in our library10.1016/j.mib.2014.11.014

7. 7.

   Berlin K. et al. Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nature biotechnology 33, 623–630 (2015 ).

   Not in our library10.1038/nbt.3238

8. 8.
   LoRDEC: accurate and efficient long read error correction · 2014

   No notice
9. 9.

   Lee H. et al. Error correction and assembly complexity of single molecule sequencing reads. BioRxiv. 006395, doi: (2014 ).

   Not in our library10.1101/006395

10. 10.

    Hackl T., Hedrich R., Schultz J. & Forster F. proovread: large-scale high-accuracy PacBio correction through iterative short read consensus. Bioinformatics doi: (2014 ).

    Not in our library10.1093/bioinformatics/btu392

11. 11.
    SSPACE-LongRead: scaffolding bacterial draft genomes using long read sequence information · 2014

    No notice
12. 12.

    Deshpande V., Fung E. K., Pham S. & Bafna V. In Algorithms in Bioinformatics Vol. 8126 Lecture Notes in Computer Science (eds Aaron Darling & Jens Stoye ) Ch. 27, 349–363 (Springer: Berlin Heidelberg,, 2013 ).

    Not in our library

13. 13.

    Chin C. S. et al. Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing data. Nature methods 10, 563–569, doi: (2013 ).

    Not in our library10.1038/nmeth.2474

14. 14.

    Ribeiro F. J. et al. Finished bacterial genomes from shotgun sequence data. Genome research 22, 2270–2277, doi: (2012 ).

    Not in our library10.1101/gr.141515.112

15. 15.
    Mind the Gap: Upgrading Genomes with Pacific Biosciences RS Long-Read Sequencing Technology · 2012

    No notice
16. 16.

    Bashir A. et al. A hybrid approach for the automated finishing of bacterial genomes. Nature biotechnology 30, 701–707, doi: (2012 ).

    Not in our library10.1038/nbt.2288

17. 17.
    Improving PacBio Long Read Accuracy by Short Read Alignment · 2012

    No notice
18. 18.

    Nagarajan N. & Pop M. Sequence assembly demystified. Nature reviews. Genetics 14, 157–167, doi: (2013 ).

    Not in our library10.1038/nrg3367

19. 19.

    Myers E. W. The fragment assembly string graph. Bioinformatics 21 Suppl 2, ii79–85, doi: (2005 ).

    Not in our library10.1093/bioinformatics/bti1114

20. 20.

    Pevzner P. A., Tang H. & Waterman M. S. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences 98, 9748–9753, doi: (2001 ).

    Not in our library10.1073/pnas.171285098

21. 21.

    Miller J. R. et al. Aggressive assembly of pyrosequencing reads with mates. Bioinformatics 24, 2818–2824, doi: (2008 ).

    Not in our library10.1093/bioinformatics/btn548

22. 22.

    Simpson J. T. & Durbin R. Efficient de novo assembly of large genomes using compressed data structures. Genome research 22, 549–556, doi: (2012 ).

    Not in our library10.1101/gr.126953.111

23. 23.

    Treangen T. J., Sommer D. D., Angly F. E., Koren S. & Pop M. Next generation sequence assembly with AMOS. Current Protocols in Bioinformatics, doi: (2011 ).

    Not in our library10.1002/0471250953.bi1108s33

24. 24.

    Batzoglou S. et al. ARACHNE: a whole-genome shotgun assembler. Genome research 12, 177–189, doi: (2002 ).

    Not in our library10.1101/gr.208902

25. 25.

    Myers G. Efficient local alignment discovery amongst noisy long reads. Algorithms in Bioinformatics 52–67, doi: (2014 ).

    Not in our library10.1007/978-3-662-44753-6

26. 26.

    Chaisson M. J., Brinza D. & Pevzner P. A. De novo fragment assembly with short mate-paired reads: Does the read length matter? Genome research 19, 336–346, doi: (2009 ).

    Not in our library10.1101/gr.079053.108

27. 27.
    Versatile and open software for comparing large genomes · 2004

    No notice
28. 28.
    Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory · 2012

    No notice
29. 29.

    Smith T. F. & Waterman M. S. Identification of Common Molecular Subsequences. J Mol Biol 147, 195–197, doi: (1981 ).

    Not in our library10.1016/0022-2836(81)90087-5

30. 30.

    Ye C. & Ma Z. S. Sparc: a sparsity-based consensus algorithm for long erroneous sequencing reads. PeerJ 4, e2016 (2016 ).

    Not in our library10.7717/peerj.2016

31. 31.

    Chakraborty M., Baldwin-Brown J. G., Long A. D. & Emerson J. J. A practical guide to de novo genome assembly using long reads. bioRxiv. 029306 (2015 ).

    Not in our library

32. 32.

    Gurevich A., Saveliev V., Vyahhi N. & Tesler G. QUAST: quality assessment tool for genome assemblies. Bioinformatics 29, 1072–1075, doi: (2013 ).

    Not in our library10.1093/bioinformatics/btt086

Cited by papers we hold 9

• High contiguity de novo genome assembly and DNA modification analyses for the fungus fly, Sciara coprophila, using single-molecule sequencing · 2021
  Not checked
• Insights into genomic evolution from the chromosomal and mitochondrial genomes of Ustilaginoidea virens · 2021
  Not checked
• Massive gene presence-absence variation shapes an open pan-genome in the Mediterranean mussel · 2020
  No notice
• TGS-GapCloser: A fast and accurate gap closer for large genomes with low coverage of error-prone long reads · 2020
  No notice
• Structural variants exhibit widespread allelic heterogeneity and shape variation in complex traits · 2019
  No notice
• Highly Contiguous Genome Assemblies of 15 Drosophila Species Generated Using Nanopore Sequencing · 2018
  No notice
• FMLRC: Hybrid long read error correction using an FM-index · 2018
  No notice
• Hidden genetic variation shapes the structure of functional elements in Drosophila · 2017
  No notice
• Canu: scalable and accurate long-read assembly via adaptive k -mer weighting and repeat separation · 2017
  No notice

Reads

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.