Turn ‘noise’ to signal: accurately rectify millions of erroneous short reads through graph learning on edit distances

Pengyao Ping, Shuquan Su, Xinhui Cai, Lü Tian, Xuan Zhang, Hui Peng, Yi Pan, Wei Liu, Jinyan LibioRxiv 2024 · DOI

TL;DR

This paper introduces "noise2read," a novel graph-learning and machine learning approach to accurately correct millions of erroneous short DNA sequencing reads. By modeling PCR error mechanisms and leveraging edit distances, noise2read significantly improves data quality without introducing false sequences, leading to better downstream genomic analyses.

What Problem Does This Paper Address?

Next-generation sequencing (NGS) technologies generate vast amounts of short DNA reads. While the per-base error rate is low (0.1-0.5%), the cumulative effect means that 10-15% of reads in a dataset can contain errors. These erroneous reads, often millions in number, represent a significant loss of valuable information and can lead to inaccurate conclusions in downstream applications like genome assembly, variant calling, and gene expression analysis. Existing error correction methods often struggle to correct a substantial portion of these errors or, worse, introduce new, non-existent sequences, compromising data integrity. This paper aims to address this by providing a method that accurately corrects erroneous reads while preserving data integrity.

Methods

The core of noise2read lies in constructing a graph where nodes represent unique reads and edges connect reads with small edit distances (1 or 2). The key insight is that a rare read is likely erroneous if it has a neighboring read with high abundance, reflecting PCR amplification errors.

The method proceeds in three stages:

  1. 1nt-error correction: Identifies and corrects low-frequency reads that are likely errors by linking them to high-frequency neighbors.
  2. 2nt-error correction: Addresses more complex errors by considering pairs of reads with an edit distance of 2, focusing on substitutions.
  3. Amplicon correction (optional): A specialized stage for amplicon sequencing data to further refine corrections.

A crucial component is an Auto Machine Learning (AutoML) module that uses a gradient boosting classifier (XGBoost) to learn platform-specific error patterns. This module is trained on "edit-erring-READS" (likely erroneous reads) and "error-free-READS" (high-frequency, presumably correct reads) to predict and correct ambiguous or hard-case errors. Features for the ML model include Fourier Transforms, entropy measures, Fickett's scores, and read counts.

Datasets

The authors utilized a variety of datasets for training and evaluation:

  • UMI-based wet-lab datasets (D1-D8): These are considered "gold-standard" datasets with known ground truth, generated using a novel approach that involves UMI error correction and filtering of reads with more than 2 base errors.
  • Simulated datasets (D9-D13): Created from real sequencing data with artificially introduced errors to mimic various NGS scenarios.
  • miRNA sequencing datasets (D14-D17): Simulated datasets specifically for miRNA sequencing, including substitution and indel errors.
  • SARS-CoV-2 and Monkeypox virus data: Used to demonstrate the impact of error correction on genome abundance quantification.
  • IsomiR and SNP profiling datasets (D22-D31): Small RNA sequencing datasets used to assess the impact on isomiR and SNP identification.
  • Base editing datasets (D32-D33): Used to evaluate the impact of error correction on predicting base editing efficiencies.

The paper also references previously established UMI-based benchmark datasets (D34-D41).

Key Insights and Ideas

  • The "rare read is erroneous if it has a high-abundance neighbor" principle: This is the foundational idea, directly translating PCR error mechanisms into a computable rule for error detection.
  • Graph learning for error detection: Representing reads as nodes and their edit distances as edges allows for a systematic way to identify potential errors within the context of the entire dataset.
  • ML for hard-case errors: Using AutoML to learn platform-specific error patterns is crucial for correcting complex or ambiguous errors that simple edit-distance comparisons cannot resolve.
  • Preserving data integrity: A key differentiator is the emphasis on not introducing non-existing sequences, a common pitfall of other methods.
  • Impact on downstream applications: The paper strongly demonstrates that correcting sequencing errors has a tangible and significant positive impact on various genomic analyses, from abundance quantification to variant calling.

Key Results

  • Superior performance: noise2read consistently outperformed state-of-the-art methods across 19 metrics on numerous UMI-based wet-lab and simulated datasets.
  • Significant abundance changes: Error correction led to a 12% increase in SARS-CoV-2 reference genome coverage and a 52.12% boost for Monkeypox.
  • Improved isomiR and SNP profiling: The number of unique ambiguous isomiRs decreased by up to 31.75%, and unique SNPs decreased by up to 59.09%, suggesting many previously identified variants were actually sequencing errors.
  • High accuracy and low false positives: The method achieved high True Positive Rate (TPR) and True Negative Rate (TNR), while maintaining low False Positive Rate (FPR) and False Negative Rate (FNR).
  • Exceptional purity entropy: noise2read significantly decreased purity entropy, indicating a cleaner dataset with fewer erroneous reads.

Limitations and Future Work

  • Computational cost: The authors acknowledge that noise2read can be slow and memory-intensive, particularly during graph construction and AutoML training. They suggest efficiency tricks like reducing negative samples or trials for AutoML, and exploring attention-based deep learning models for feature extraction.
  • Performance on very short reads: noise2read may derive more false positives when dealing with errors between high-frequency reads of extremely short lengths (e.g., < 30bp). Future work may involve adjusting feature extraction.
  • Edit distance threshold (Emax): The current use of Emax=1 or 2 is based on the majority of errors. Future work will explore the impact of increasing this threshold to 3 and its effect on computational complexity.
  • Handling of indels: While the paper mentions handling indels when represented by 'N', the primary focus and evaluation seem to be on substitutions.

The authors express a desire to improve efficiency and explore novel feature engineering and deep learning architectures in future work.

Summary updated

Abstract

Abstract Although the per-base erring rate of NGS is very low at 0.1% to 0.5%, the percentage/probability of erroneous reads in a short-read sequencing dataset can be as high as 10% to 15% or in the number of millions. Correction of these wrongly sequenced reads to retrieve their huge missing value will improve many downstream applications. As current methods correct only some of the errors at the cost of introducing many new errors, we solve this problem by turning erroneous reads into their original states, without bringing up any non-existing reads to keep the data integrity. The novelty of our method is originated in a computable rule translated from PCR erring mechanism that: a rare read is erroneous if it has a neighbouring read of high abundance. With this principle, we construct a graph to link every pair of reads of tiny edit distances to detect a solid part of erroneous reads; then we consider them as training data to learn the erring mechanisms to identify possibly remaining hard-case errors between pairs of high-abundance reads. Compared with state-of-the-art methods on tens of datasets of UMI-based ground truth, our method has made a remarkably better performance under 19 metrics including two entropy metrics that measure noise levels in a dataset. Case studies found that our method can make substantial impact on genome abundance quantification, isoform identification, SNP profiling, and genome editing efficiency estimation. For example, the abundance level of the reference genome of SARS-CoV-2 can be increased by 12% and that of Monkeypox can be boosted by 52.12% after error correction. Moreover, the number of distinct isomiRs is decreased by 31.56%, unveiling there are so many previously identified isomiRs that are actually sequencing errors. Author summary Detecting short-read sequencing errors and correcting the related erroneous reads is a long-standing problem in bioinformatics. Current error correction algorithms correct only small parts of the errors but simultaneously introduce thousands of non-existing sequences. We present a new method to rectify erroneous reads under 300 bp produced by PCR-involved miRNA-sequencing, small RNA sequencing, or paired-end RNA sequencing, regardless of platform or sample type. Our method is the first kind considering the PCR erring mechanism and machine learning technique to improve sequencing data quality by turning millions of erroneous short reads into their original state without bringing up any non-existing sequences into the read set. Our error correction method can make a significant impact on a wide range of cutting-edge downstream applications. The observations and advantages in the case studies lay down strong evidence to question the accuracies of current downstream research outcomes and open new avenues to conduct downstream analysis whenever short-read data are adopted.
BibTeX
@misc{ping2024turn,
  author = {Pengyao Ping and Shuquan Su and Xinhui Cai and Lü Tian and Xuan Zhang and Hui Peng and Yi Pan and Wei Liu and Jinyan Li},
  title = {{Turn ‘noise’ to signal: accurately rectify millions of erroneous short reads through graph learning on edit distances}},
  year = {2024},
  doi = {10.1101/2024.04.05.588226},
  howpublished = {bioRxiv},
}
Figure