Metheor: Ultrafast DNA methylation heterogeneity calculation from bisulfite read alignments

Dohoon Lee, Bonil Koo, Jeewon Yang, Sun Kim

Abstract

Phased DNA methylation states within bisulfite sequencing reads are a valuable source of information used to estimate epigenetic diversity across cells and epigenomic instability in individual cells. However, in routine analyses, this heterogeneity is often overlooked due to the computational intensity of existing tools. We present Metheor, a Rust-based, extremely fast and lightweight bioinformatics toolkit. Metheor reduces execution time by up to 300-fold and memory footprint by up to 60-fold compared to existing implementations, while producing identical results. This performance leap facilitates the inclusion of DNA methylation heterogeneity measures in large-scale downstream epigenomic analyses.

Introduction: The Heterogeneity Bottleneck

DNA methylation is a key epigenetic regulator, typically analyzed by calculating the average methylation level at specific CpG sites. However, this "CpG-centric" approach hides critical "phasing" information—the specific patterns of methylation across a single DNA molecule. These patterns reveal epigenetic diversity within cell populations and can signal genomic instability in diseases like cancer.

Illustration of DNA methylation patterns and discordant reads (PDR) used to measure heterogeneity.

While measures for this heterogeneity exist (e.g., PDR, Methylation Entropy), legacy software tools are often slow, written in interpreted languages, and computationally inefficient. As sequencing datasets grow to hundreds of millions of reads, these tools become a massive bottleneck, often requiring days of computation and hundreds of gigabytes of RAM.

Methods: A Read-Centric "One-Sweep" Approach

Metheor, implemented in Rust for maximum efficiency and memory safety, introduces a shift in algorithmic strategy:

  • Read-Centric "One-Sweep" Processing: Standard tools are "CpG-centric," iterating through genomic sites and fetching every overlapping read repeatedly. Metheor instead iterates through the alignment file (BAM) exactly once. It processes each read, updates statistics for all contained CpG sites, and moves on, drastically reducing I/O operations.
  • Local Pairwise Methylation Discordance (LPMD): Alongside six established measures, the authors introduce LPMD. Unlike the popular PDR metric, which can be biased by read length, LPMD calculates discordance based on pairs of CpGs within specific genomic distances, making it more robust across different sequencing protocols.
  • Reservoir Sampling: To handle the exponential computational cost of comparing read pairs in high-depth regions, Metheor uses reservoir sampling to maintain a representative subset of reads, keeping computation time predictable.

Results: Dramatic Performance Gains

Metheor was benchmarked against existing tools like WSHPackage and Methclone using simulated and real-world RRBS datasets. The results demonstrated a 300-fold speedup in execution time and a 60-fold reduction in memory footprint.

Performance comparison showing Metheor's near-constant wall time versus the exponential growth of WSHPackage as read counts increase.

One of the most striking findings was that Metheor, running on a single thread, outperformed WSHPackage even when the latter was given 32 threads. This highlights that algorithmic efficiency—specifically the reduction of redundant I/O operations—often trumps raw parallelization. Furthermore, Metheor's memory usage scales linearly with data size, allowing it to run on standard workstations rather than high-RAM server nodes.

Conclusion

Metheor removes the computational barriers to including DNA methylation heterogeneity in routine bioinformatics pipelines. Its speed and low resource requirements enable the use of complex epigenetic biomarkers in clinical settings, potentially improving cancer diagnostics and treatment monitoring. The software is freely available for non-commercial users at https://github.com/dohlee/metheor.

Summary updated

Abstract

Abstract Motivation Phased DNA methylation states within bisulfite sequencing reads are valuable source of information that can be used to estimate epigenetic diversity across cells as well as epigenomic instability in individual cells. Various measures capturing the heterogeneity of DNA methylation states have been proposed for a decade. However, in routine analyses on DNA methylation, this heterogeneity is often overlooked by computing average methylation levels at CpG sites. In this study, to facilitate the application of the DNA methylation heterogeneity measures in downstream epigenomic analyses, we present a Rust-based, extremely fast and lightweight bioinformatics toolkit called Metheor. Results We benchmark the performance of Metheor against existing code implementation for DNA methylation heterogeneity measures in three different scenarios of simulated bisulfite sequencing datasets. Metheor was shown to dramatically reduce the execution time up to 300-fold and memory footprint up to 60-fold, while producing the same results with the original implementation. Availability Source code for Metheor is at https://github.com/dohlee/metheor and is freely available for non-commercial users. Contact [email protected]
BibTeX
@article{lee2023metheor,
  author = {Dohoon Lee and Bonil Koo and Jeewon Yang and Sun Kim},
  title = {{Metheor: Ultrafast DNA methylation heterogeneity calculation from bisulfite read alignments}},
  journal = {PLOS Computational Biology},
  year = {2023},
  doi = {10.1371/journal.pcbi.1010946},
}
Figure