Efficient inference of evolutionary and progressive dynamics on hypercubic transition graphs

The progression of cancer and other diseases, the evolution of organismal features in biology, and a wide range of broader questions can often be viewed as the sequential stochastic acquisition of binary traits (for example, genetic changes, symptoms, or characters). Using potentially noisy or incomplete data to learn the sequences by which such traits are acquired is a problem of general interest. The problem is complicated for large numbers of traits which may, individually or synergistically, influence the probability of further acquisitions both positively and negatively. Hypercubic inference approaches, based on hidden Markov models on a hypercubic transition network, address these complications, but previous Bayesian instances can consume substantial time for converged results, limiting their practical use. Here we introduce HyperHMM, an adapted Baum-Welch (expectation maximisation) algorithm for hypercubic inference with resampling to quantify uncertainty, and show that it allows orders-of-magnitude faster inference while making few practical sacrifices compared to existing approaches. We apply this approach to synthetic and biological datasets and discuss its more general application in learning evolutionary and progressive pathways.