Spectral Learning of Binomial HMMs for DNA Methylation Data

Chicheng Zhang, Eran A. Mukamel, Kamalika ChaudhuriarXiv 2018 · OpenReview

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.

Estimation error of FTD vs EM across different mean coverage levels and sample sizes.

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.

Runtime comparison between FTD and EM algorithms across varying sample sizes.

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

Abstract

We consider learning parameters of Binomial Hidden Markov Models, which may be used to model DNA methylation data. The standard algorithm for the problem is EM, which is computationally expensive for sequences of the scale of the mammalian genome. Recently developed spectral algorithms can learn parameters of latent variable models via tensor decomposition, and are highly efficient for large data. However, these methods have only been applied to categorial HMMs, and the main challenge is how to extend them to Binomial HMMs while still retaining computational efficiency. We address this challenge by introducing a new feature-map based approach that exploits specific properties of Binomial HMMs. We provide theoretical performance guarantees for our algorithm and evaluate it on real DNA methylation data.
BibTeX
@misc{zhang2018spectral,
  author = {Chicheng Zhang and Eran A. Mukamel and Kamalika Chaudhuri},
  title = {{Spectral Learning of Binomial HMMs for DNA Methylation Data}},
  year = {2018},
  eprint = {1802.02498},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.02498},
}
Figure