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.
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.
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