Introduction
DNA methylation, the addition of methyl groups to cytosine bases, is a critical epigenetic regulator of gene expression. Mapping these marks across the genome is essential for understanding biological development and disease. However, mammalian genomes are vast, containing approximately $10^9$ nucleotides, and sequencing data is often characterized by noise due to stochastic sampling and incomplete coverage.
Statistically, methylation patterns are frequently modeled using Binomial Hidden Markov Models (HMMs). In this framework, a hidden state—representing a genomic feature like a promoter or gene body—governs the probability of methylation at a specific site. The standard approach for parameter estimation in these models is the Expectation-Maximization (EM) algorithm. While effective, EM is an iterative process requiring multiple passes over the entire dataset, rendering it computationally prohibitive for large-scale mammalian genomic studies.
Methodology: Feature-Tensor-Decomposition
This paper introduces a novel spectral algorithm, Feature-Tensor-Decomp (FTD), designed to overcome the scalability limits of EM. Unlike iterative methods, spectral algorithms rely on moment-based estimation, requiring only a single pass over the data.
The Beta Map
The core innovation is the Beta Map, a feature map specifically tailored for Binomial HMMs. Traditional spectral methods were limited to categorical data; the Beta Map bridges this gap by mapping integer pairs (methylation count $\mu_t$ and total coverage $c_t$) to a $D$-dimensional vector. Inspired by the Beta-Binomial conjugate prior, this map represents observations as probability density functions. Higher sequencing coverage results in sharper, more informative feature vectors, naturally incorporating measurement confidence into the learning process.
Parameter Recovery and Stabilization
Following the transformation of data via the Beta Map, the algorithm employs tensor decomposition to recover model parameters. A novel recovery procedure translates the decomposed tensors back into binomial probability parameters ($p_h$). To address potential model mismatches in real-world data, a least-squares stabilization step is introduced to ensure that the recovered transition matrices contain valid, non-negative probabilities.
Experimental Results
The FTD algorithm was evaluated using both synthetic and real-world DNA methylation data.
Synthetic Evaluation
Synthetic sequences were generated from a 4-state Binomial HMM with varying mean coverage levels ($\mu \in \{25, 50, 100\}$). FTD demonstrates competitive accuracy compared to EM. Notably, for larger sample sizes, FTD exhibits lower estimation error and reduced variance, confirming its statistical consistency.
Computational Efficiency
The primary advantage of FTD is its speed. FTD is significantly faster than EM, with the performance gap widening as the sample size increases. On a dataset of $1.6 \times 10^6$ bins, FTD completed in under five minutes, whereas EM required substantially more time even on smaller subsets.
Real-World Application
The algorithm was applied to whole-genome bisulfite sequencing (BS-Seq) data from chromosome 1 of the mouse genome, focusing on excitatory neurons and VIP cells. FTD successfully identified biologically relevant states, including low-methylation regions (promoters) and high-methylation regions (gene bodies), as well as differential methylation patterns between cell types.
Conclusion
The Feature-Tensor-Decomp framework provides a scalable alternative to EM for learning Binomial HMMs. By leveraging the Beta Map and spectral decomposition, it achieves an order-of-magnitude speedup without sacrificing accuracy. Future work may explore extending this framework to other exponential family distributions, such as Poisson models for RNA-seq data, and optimizing the dimensionality of the feature map to balance accuracy and computational cost.
Summary updated