Source-linked AI summary
DBG2OLC: Efficient Assembly of Large Genomes Using Long Erroneous Reads of the Third Generation Sequencing Technologies
Chengxi Ye, Chris Hill, Shigang Wu, Jue Ruan, Zhanshan, Ma
TL;DR
Assembling long erroneous reads remains computationally and structurally challenging. DBG2OLC presents a de novo assembly pipeline that reduces computational and sequencing requirements, while enabling direct assembly of erroneous long reads.
Problem
Computationally expensive pairwise alignment and chimeric reads hamper efficient, contiguous assembly of long sequencing reads.
Method
DBG2OLC builds a de novo assembly pipeline that uses algorithmic techniques to address computational and sequencing challenges in 3GS assembly.
Results
The pipeline reduces computational and sequencing requirements, and erroneous long reads can be directly assembled with improved assembly outcomes.
Takeaways & Limitations
DBG2OLC supports more efficient 3GS assembly by directly assembling erroneous long reads while reducing computational and sequencing requirements.
Takeaways & Limitations
About 90% of computation time is concentrated in one component, and higher coverage increases sequencing cost.
Abstract
from arXiv · showhide
(An updated version of this manuscript has been accepted to Scientific Reports in 2016, please refer to http://www.nature.com/articles/srep31900) 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 lead 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, which established 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 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 efficiently in time than existing methods, while saving about half of the sequencing cost.
Introduction
Third-generation sequencing offers longer reads but remains difficult to adopt because high error rates, costly sequencing, and computationally intensive assembly limit large-genome applications. The study introduces a hybrid approach that exploits NGS assembly and long-read overlaps to enable efficient, error-robust assembly while reducing sequencing requirements and cost.
- Limitations: Existing 3GS assembly approaches require high sequencing coverage and substantial error-correction resources, especially for large genomes.Existing assemblers usually require 50x-100x coverage, while mammalian-sized genome assembly can require up to 10^5 or 10^6 CPU hours.
- Contribution: The authors design algorithms for efficient assembly of large mammalian-sized genomes using 3GS data.The approach addresses computational resource consumption, sequencing coverage requirements, and robustness to sequencing errors.
- Method: The pipeline directly analyzes long-read overlap information without base-level correction and uses NGS assembly to reduce the burden of aligning 3GS sequences.This converts NGS assembly information into a compact representation for efficient long-read analysis rather than using NGS only to polish 3GS data.
- Impact: Using NGS data lowers the sequencing depth required for 3GS assembly, reducing total sequencing cost while combining benefits of hybrid and non-hybrid assembly.The two data types can compensate for one another, and the pipeline also provides an efficient solution to the traditional read threading problem.
Methods and Implementations
DBG2OLC converts accurate NGS contigs and erroneous 3GS reads into a compact overlap-graph assembly through a five-procedure pipeline. The approach accelerates read processing by compressing reads, correcting structural errors, constructing best overlaps, and polishing reconstructed sequences.
- Pipeline: DBG2OLC converts NGS-derived de Bruijn graph contigs and long reads into an overlap-graph assembly through five pipeline procedures.The pipeline constructs NGS contigs, anchors and compresses long reads, cleans structural errors, builds overlaps, then reconstructs and polishes sequences.
- Read compression: Three factors of reduction in read length usually result from compression across five datasets and different sequencing technologies.The compact representation also spans small regions with low or no NGS coverage, while NGS contigs can cover small 3GS gaps.
- Alignment and correction: An inverted index selects candidate compressed reads by shared contig identifiers, after which Smith-Waterman alignment calculates pairwise overlaps efficiently.Match and mismatch scores depend on contig lengths or the number of matching k-mers.
- Alignment and correction: Multiple sequence alignment removes chimeric reads and spurious contig identifiers, while remaining minor errors are tolerated during overlap detection.This correction slightly increases the required 3GS coverage because each compressed read must be confirmed by at least another read.
- Overlap graph and polishing: The best overlap graph filters contained nodes, detects suffix-prefix overlaps, chains nodes, simplifies tips and bubbles, and retains unresolved repeats as breakpoints.Only linear unbranched graph regions are converted back to raw nucleotide reads for consensus polishing.
Results
DBG2OLC produced high-contiguity, structurally correct assemblies from low-coverage long-read data while using substantially less time and memory than existing pipelines. Its performance scaled near linearly with data size, and its hybrid design reduced sequencing and computational costs.
- Large-genome performance: DBG2OLC produced comparably good medium-to-large-genome assemblies with one to two orders of magnitude less time and memory than most existing pipelines.A 3 Gbp H. sapiens draft assembly without polishing finished in 3 CPU days using 30x 3GS and 50x NGS data.
- Computational efficiency: The pipeline scaled near linearly with data size, supporting large-scale genome assembly.For A. thaliana (120Mbp), DBG2OLC computation finished in one hour after another hour for NGS-contig construction; peak memory usage was 6GB, versus over one thousand CPU hours for existing pipelines.
- Assembly quality: 10x-20x PacBio coverage yielded assembly N50s significantly (>10x) better than Illumina data alone.Nearly perfect diagonal dot plots indicated structurally correct assemblies from as low as 10x long-read data.
- Human genome: On a large human dataset, DBG2OLC reached NG50 433kbp from 10x PacBio data and 50x Illumina-derived DBG contigs.The final assembly had N50=6Mbp, comparable to state-of-the-art results; consensus took roughly 2000 CPU hours versus 405,000 CPU hours for a reported overlapping process.
- Small-genome validation: DBG2OLC assembled the E. coli genome into one single contig, and the polished assembly had an error rate of 0.23%.The results supported high contiguity and accuracy despite lower PacBio sequencing coverage.
- Design principles: DBG2OLC’s efficiency derives from compact long-read representation, skipping base-level errors while correcting structural errors, and assembling and polishing structurally correct reads.The implementation connects de Bruijn and overlap-graph frameworks by converting a de Bruijn graph to an overlap graph.
Summary and Discussion
DBG2OLC reduces the computational and sequencing requirements of 3GS assembly by directly assembling erroneous long reads without base-level error correction. Chimeric reads create structural errors that hamper contiguity, while removing them could enable near-perfect assemblies at lower coverage.
- Contributions: DBG2OLC reduces the computational and sequencing requirements of 3GS assembly through a validated de novo assembly pipeline.The pipeline directly assembles erroneous long reads and improves assembly without base-level error correction.
- Limitations: 3GS technologies generate chimeric reads, with the problem apparently more severe on PacBio, creating structural errors that tangle assembly graphs and reduce contiguity.DBG2OLC addresses chimeric-read cleanup with multiple sequence alignment.
- Limitations: Multiple sequence alignment for chimeric-read cleanup slightly increases the coverage requirement, identifying a limitation for DBG2OLC.This limitation motivates future development of sequencing technologies and correction algorithms.
- Future directions: Near-perfect assemblies may be achievable with even lower coverage if chimeras and structural errors can be removed.This is presented as a conjecture about future improvements rather than a demonstrated result.
Figures
The figures depict a four-step assembly workflow: compress long reads into ordered contig lists, identify best overlaps, build an assembly backbone, and derive a consensus sequence.
- Compression: Long reads are mapped to de Bruijn graph contigs and converted into ordered lists called compressed reads.The long reads are shown in red, while the de Bruijn graph contigs use other colors.
- Overlap calculation: Overlaps between compressed reads are calculated using anchors, after which contained reads are removed and reads are chained by best overlap.
- Layout: The assembly backbone is constructed from the best overlaps among the non-contained reads.
- Consensus: All related reads are aligned to the backbone, and the most likely sequence is calculated as the consensus output.
1. Source Code
Source code for SparseAssembler, DBG2OLC, and Sparc is available on GitHub, with separate-folder compilation using g++ -O3 commands.
- Source Code: Source code for SparseAssembler, DBG2OLC, and Sparc is available on GitHub and can be compiled separately with g++ -O3 commands.The provided commands produce executables named SparseAssebmler, DBG2OLC, and Sparc.
2. Datasets used in the paper
The paper uses Illumina, PacBio/Nanopore, and reference-genome datasets. These datasets are documented in Tables S1–S3.
- Table S1 lists the Illumina datasets used in the paper.
- Table S2 lists the PacBio/Nanopore datasets used in the paper.
- Table S3 lists the reference genomes used in the paper.
3. Exemplary Assembly Commands
The workflow builds accurate DBG contigs, overlaps them with long reads using DBG2OLC, and then calls consensus. Example runs report N50 values of 29 kbp for the initial contigs, 32kbp after tuning, and 583kbp after long-read assembly.
- Step 1: DBG contigs: Step 1 constructs short, accurate raw DBG contigs without repeat resolving, gap closing, or scaffolding heuristics.The resulting Contigs.txt is used by DBG2OLC.
- Step 2: Overlap and layout: Step 2 feeds the DBG contigs and long reads to DBG2OLC for overlap and layout.The example uses k 17, AdaptiveTh 0.0001, KmerCovTh 2, MinOverlap 20, and RemoveChimera 1 with 20x PacBio reads.
- Step 2: Overlap and layout: 583kbp N50 is achieved in the DBG2OLC test run.DBG2OLC calculates long-read overlap scores by aligning compressed reads and scoring matching k-mers; parameters can be fine-tuned afterward.
- Step 3: Call consensus: Step 3 calls consensus from the DBG2OLC backbone, consensus information, DBG contigs, and PacBio reads using Sparc or PBdagcon.The workflow requires Blasr and the consensus module to be installed and available in the path variable.
4. Dotplots of Alignments to the Reference Genomes
Dot plots assessed DBG2OLC assemblies by aligning them to 454, high-coverage PacBio, or reference genomes across multiple long-read coverages and organisms. The plots were generated with nucmer and mummerplot.
- Plot generation: The dot plots were generated with nucmer using 200-bp alignment parameters and rendered with mummerplot as large PNG figures.The commands used were nucmer -mumreference -b 200 -g 200 -c 200 and mummerplot --png --l --large -f --fat.
- S. cer alignment dotplots: The high-coverage PacBio assembly of S. cer was also aligned directly to the 454 assembly.This comparison is shown in Figure S9.
- A. thaliana alignment dotplots: DBG2OLC A. thaliana assemblies were aligned to the high-coverage PacBio assembly using 10x, 20x, and 40x PacBio reads with 50x Illumina reads.These comparisons are shown in Figures S10–S12.
- E. coli alignment dotplot: The DBG2OLC E. coli assembly was aligned to the reference genome using 30x Oxford Nanopore reads and 50x Illumina reads.This comparison is shown in Figure S13.