TL;DR
This paper introduces NECAT, a novel tool that significantly improves the accuracy and speed of assembling genomes from Nanopore sequencing data. By employing a progressive error correction strategy and a two-stage assembly approach, NECAT effectively handles the complex error profiles of Nanopore reads, leading to more contiguous and reliable genome assemblies.
What Problem Does This Paper Address?
De novo genome assembly, the process of reconstructing a genome from scratch without a reference, is a fundamental task in genomics. Long-read sequencing technologies like Oxford Nanopore offer the promise of more contiguous genome assemblies by spanning repetitive regions. However, Nanopore reads are characterized by a high and complex error rate, which has historically hindered their effective use in de novo assembly. Existing error correction and assembly methods, often developed for other technologies like PacBio, struggle to efficiently and accurately process Nanopore data, leading to fragmented assemblies and increased computational costs. This paper aims to bridge this gap by developing a specialized tool, NECAT, to overcome these challenges.
Methods
NECAT introduces several key innovations:
- Progressive Error Correction: Instead of a single-pass correction, NECAT employs a two-step progressive approach. It first corrects low-error-rate subsequences (LERS) and then tackles high-error-rate subsequences (HERS) using a more sensitive method. This strategy allows for more thorough error correction.
- Adaptive Read Selection: To improve the accuracy of error correction, NECAT uses an adaptive mechanism to select high-quality supporting reads for each template read. This involves setting both global and individual overlapping-error-rate thresholds to balance the inclusion of sufficient supporting reads with the avoidance of false positives.
- Two-Stage Assembler: To leverage the full length of Nanopore reads, NECAT employs a two-stage assembly process. First, it generates contigs using corrected reads. Second, it bridges these contigs using the original, uncorrected Nanopore reads, effectively filling gaps and improving contiguity.
- Efficient Algorithms: NECAT incorporates optimized algorithms for various steps, including k-mer chaining for filtering false positives, blockwise and DALIGN alignment for read mapping, and Edlib for refined alignment.
Datasets
The performance of NECAT was evaluated using nine datasets from various species, including:
- E. coli
- Saccharomyces cerevisiae
- Arabidopsis thaliana
- Drosophila melanogaster
- Chlamydomonas reinhardtii
- Oryza sativa
- Solanum pennellii
- Human (NA12878)
- Human retinoblastoma cell line (WERI)
The WERI cell line dataset was generated in-house, while the others were obtained from public websites. The paper also references existing benchmarks and comparisons with tools like Canu and Canu+smartdenovo.
Key Insights and Ideas
- Error Distribution is Key: The broad distribution of error rates, both across different Nanopore reads and within individual reads, is the primary reason why traditional error correction methods fail. NECAT's progressive and adaptive approach directly addresses this.
- Long Reads Need Special Handling: Simply correcting Nanopore reads and then assembling them can lose the advantage of their length. NECAT's two-stage assembly, which uses raw reads for contig bridging, effectively preserves this advantage.
- Adaptive Thresholds are Crucial: A single, fixed threshold for read selection or overlap filtering is insufficient for Nanopore data. NECAT's use of both global and individual adaptive thresholds is critical for balancing accuracy and completeness.
- High-Quality Assemblies Aid Downstream Analysis: The improved accuracy and contiguity of assemblies produced by NECAT can significantly reduce false positives in downstream analyses like structural variation detection.
Key Results
- Speed: NECAT's error correction is 2.1-16.5 times faster than Canu. Its assembly step is also significantly faster, with speedups of 8.3-258.2 times compared to Canu and 3.2-57.0 times compared to Canu+smartdenovo.
- Accuracy and Contiguity: NECAT achieves superior error correction, with a higher percentage of reads having less than 5% error. Its progressive correction strategy also preserves read contiguity, as indicated by N50 values for corrected reads being comparable to or exceeding those of raw reads.
- Assembly Performance: NECAT demonstrates improved assembly performance across various species, often yielding higher NG50 values and fewer contigs compared to other tools. For example, it achieved an NG50 of 29 Mbp for the human WERI cell line, which is noted as the best N50 value for human genome assembly using Nanopore.
- Resource Efficiency: Assembling a 35X human genome with NECAT required only 7,225 CPU hours, showcasing its computational efficiency.
Limitations and Future Work
- High-Error-Rate Subsequences: While NECAT significantly improves error correction, it acknowledges that some high-error-rate subsequences (HERS) within long Nanopore reads may still fail to be corrected, potentially leading to read splitting.
- Computational Cost of Alignment: The paper notes that performing local alignment of supporting reads to a template is computationally expensive, especially for long reads. NECAT employs strategies like coverage count arrays (CCA) to mitigate this, but it remains a consideration.
- Future Work: The authors suggest that their results provide insights into why existing correction algorithms are not suitable for Nanopore reads and that NECAT is a useful tool for error correction, assembly, and structure variation detection. Further development could focus on even more robust handling of complex error patterns and optimizing alignment strategies.
Summary updated