{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T11:33:37Z","timestamp":1785929617040,"version":"3.56.0"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T00:00:00Z","timestamp":1670889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The evolution of bacterial drug resistance and other features in biology, the progression of cancer and other diseases and a wide range of broader questions can often be viewed as the sequential stochastic acquisition of binary traits (e.g. 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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Here, we introduce HyperHMM, an adapted Baum\u2013Welch (expectation\u2013maximization) 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 previous hypercubic inference approaches. We show that HyperHMM allows any combination of traits to exert arbitrary positive or negative influence on the acquisition of other traits, relaxing a common limitation of only independent trait influences. We apply this approach to synthetic and biological datasets and discuss its more general application in learning evolutionary and progressive pathways.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Code for inference and visualization, and data for example cases, is freely available at https:\/\/github.com\/StochasticBiology\/hypercube-hmm.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac803","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T13:17:30Z","timestamp":1670937450000},"source":"Crossref","is-referenced-by-count":24,"title":["HyperHMM: efficient inference of evolutionary and progressive dynamics on hypercubic transition graphs"],"prefix":"10.1093","volume":"39","author":[{"given":"Marcus T","family":"Moen","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Bergen , Bergen, Vestland, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8559-3519","authenticated-orcid":false,"given":"Iain G","family":"Johnston","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Bergen , Bergen, Vestland, Norway"},{"name":"Computational Biology Unit, University of Bergen , Bergen, Vestland, Norway"},{"name":"CAMRIA Centre for Antimicrobial Resistance , Vestland, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,12,13]]},"reference":[{"key":"2023011906415578800_btac803-B1","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1214\/aoms\/1177697196","article-title":"A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains","volume":"41","author":"Baum","year":"1970","journal-title":"Ann. Math. Stat"},{"key":"2023011906415578800_btac803-B2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1093\/biostatistics\/kxj033","article-title":"A mutagenetic tree hidden Markov model for longitudinal clonal HIV sequence data","volume":"8","author":"Beerenwinkel","year":"2007","journal-title":"Biostatistics"},{"key":"2023011906415578800_btac803-B3","doi-asserted-by":"crossref","first-page":"e1","DOI":"10.1093\/sysbio\/syu081","article-title":"Cancer evolution: mathematical models and computational inference","volume":"64","author":"Beerenwinkel","year":"2015","journal-title":"Syst. Biol"},{"key":"2023011906415578800_btac803-B4","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1111\/2041-210X.13540","article-title":"sMap: evolution of independent, dependent and conditioned discrete characters in a Bayesian framework","volume":"12","author":"Bianchini","year":"2021","journal-title":"Methods Ecol. Evol"},{"key":"2023011906415578800_btac803-B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-7-88","article-title":"SIMMAP: stochastic character mapping of discrete traits on phylogenies","volume":"7","author":"Bollback","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023011906415578800_btac803-B6","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1111\/2041-210X.13534","article-title":"Generalized hidden Markov models for phylogenetic comparative datasets","volume":"12","author":"Boyko","year":"2021","journal-title":"Methods Ecol. Evol"},{"key":"2023011906415578800_btac803-B7","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1038\/ng.2878","article-title":"Evolution and transmission of drug-resistant tuberculosis in a Russian population","volume":"46","author":"Casali","year":"2014","journal-title":"Nat. Genet"},{"key":"2023011906415578800_btac803-B8","doi-asserted-by":"crossref","first-page":"1911","DOI":"10.1093\/bioinformatics\/btw035","article-title":"TRONCO: an R package for the inference of cancer progression models from heterogeneous genomic data","volume":"32","author":"De Sano","year":"2016","journal-title":"Bioinformatics"},{"key":"2023011906415578800_btac803-B9","doi-asserted-by":"crossref","first-page":"e1009055","DOI":"10.1371\/journal.pcbi.1009055","article-title":"Conditional prediction of consecutive tumor evolution using cancer progression models: what genotype comes next?","volume":"17","author":"Diaz-Colunga","year":"2021","journal-title":"PLoS Comput. Biol"},{"key":"2023011906415578800_btac803-B10","doi-asserted-by":"crossref","first-page":"e1007246","DOI":"10.1371\/journal.pcbi.1007246","article-title":"Every which way? On predicting tumor evolution using cancer progression models","volume":"15","author":"Diaz-Uriarte","year":"2019","journal-title":"PLoS Comput. Biol"},{"key":"2023011906415578800_btac803-B11","first-page":"61","author":"Fr\u00f6hlich","year":"2014"},{"key":"2023011906415578800_btac803-B12","first-page":"14580","article-title":"Scaling up continuous-time Markov chains helps resolve underspecification","volume":"34","author":"Gotovos","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst"},{"key":"2023011906415578800_btac803-B13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.cels.2019.10.009","article-title":"HyperTraPS: inferring probabilistic patterns of trait acquisition in evolutionary and disease progression pathways","volume":"10","author":"Greenbury","year":"2020","journal-title":"Cell Syst"},{"key":"2023011906415578800_btac803-B14","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1089\/cmb.2006.13.853","article-title":"New probabilistic network models and algorithms for oncogenesis","volume":"13","author":"Hjelm","year":"2006","journal-title":"J. Comput. Biol"},{"key":"2023011906415578800_btac803-B15","doi-asserted-by":"crossref","first-page":"101245","DOI":"10.1016\/j.isci.2020.101245","article-title":"Data-driven inference reveals distinct and conserved dynamic pathways of tool use emergence across animal taxa","volume":"23","author":"Johnston","year":"2020","journal-title":"iScience"},{"key":"2023011906415578800_btac803-B16","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.cels.2016.01.013","article-title":"Evolutionary inference across eukaryotes identifies specific pressures favoring mitochondrial gene retention","volume":"2","author":"Johnston","year":"2016","journal-title":"Cell Syst"},{"key":"2023011906415578800_btac803-B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41746-019-0140-y","article-title":"Precision identification of high-risk phenotypes and progression pathways in severe malaria without requiring longitudinal data","volume":"2","author":"Johnston","year":"2019","journal-title":"NPJ Digit. Med"},{"key":"2023011906415578800_btac803-B18","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1002\/gcc.20224","article-title":"The interactive online SKY\/M-FISH & CGH database and the Entrez cancer chromosomes search database: linkage of chromosomal aberrations with the genome sequence","volume":"44","author":"Knutsen","year":"2005","journal-title":"Genes Chromosomes Cancer"},{"key":"2023011906415578800_btac803-B19","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1080\/106351501753462876","article-title":"A likelihood approach to estimating phylogeny from discrete morphological character data","volume":"50","author":"Lewis","year":"2001","journal-title":"Syst. Biol"},{"key":"2023011906415578800_btac803-B20","doi-asserted-by":"crossref","first-page":"e108358","DOI":"10.1371\/journal.pone.0108358","article-title":"Inferring tree causal models of cancer progression with probability raising","volume":"9","author":"Loohuis","year":"2014","journal-title":"PLoS One"},{"key":"2023011906415578800_btac803-B21","doi-asserted-by":"crossref","first-page":"i727","DOI":"10.1093\/bioinformatics\/btw459","article-title":"Large-scale inference of conjunctive Bayesian networks","volume":"32","author":"Montazeri","year":"2016","journal-title":"Bioinformatics"},{"key":"2023011906415578800_btac803-B22","first-page":"911","volume-title":"Artificial Intelligence and Statistics","author":"Murray","year":"2016"},{"key":"2023011906415578800_btac803-B23","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1098\/rspb.1994.0006","article-title":"Detecting correlated evolution on phylogenies: a general method for the comparative analysis of discrete characters","volume":"255","author":"Pagel","year":"1994","journal-title":"Proc. R. Soc. Lond. B Biol. Sci"},{"key":"2023011906415578800_btac803-B24","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1086\/503444","article-title":"Bayesian analysis of correlated evolution of discrete characters by reversible-jump Markov chain Monte Carlo","volume":"167","author":"Pagel","year":"2006","journal-title":"Am. Nat"},{"key":"2023011906415578800_btac803-B25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-017-1554-7","article-title":"SFREEMAP-a simulation-free tool for stochastic mapping","volume":"18","author":"Pasqualin","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023011906415578800_btac803-B26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-021-81709-3","article-title":"Understanding learner behaviour in online courses with Bayesian modelling and time series characterisation","volume":"11","author":"Peach","year":"2021","journal-title":"Sci. Rep"},{"key":"2023011906415578800_btac803-B27","doi-asserted-by":"crossref","first-page":"e00277","DOI":"10.1016\/j.heliyon.2017.e00277","article-title":"Progression inference for somatic mutations in cancer","volume":"3","author":"Peterson","year":"2017","journal-title":"Heliyon"},{"key":"2023011906415578800_btac803-B28","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/MASSP.1986.1165342","article-title":"An introduction to hidden Markov models","volume":"3","author":"Rabiner","year":"1986","journal-title":"IEEE ASSP Mag"},{"key":"2023011906415578800_btac803-B29","doi-asserted-by":"crossref","first-page":"3016","DOI":"10.1093\/bioinformatics\/btv296","article-title":"CAPRI: efficient inference of cancer progression models from cross-sectional data","volume":"31","author":"Ramazzotti","year":"2015","journal-title":"Bioinformatics"},{"key":"2023011906415578800_btac803-B30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jocs.2018.10.009","article-title":"Efficient computational strategies to learn the structure of probabilistic graphical models of cumulative phenomena","volume":"30","author":"Ramazzotti","year":"2019","journal-title":"J. Comput. Sci"},{"key":"2023011906415578800_btac803-B31","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.tree.2004.07.002","article-title":"Bayesian inference of character evolution","volume":"19","author":"Ronquist","year":"2004","journal-title":"Trends Ecol. Evol"},{"key":"2023011906415578800_btac803-B32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-016-0929-9","article-title":"OncoNEM: inferring tumor evolution from single-cell sequencing data","volume":"17","author":"Ross","year":"2016","journal-title":"Genome Biol"},{"key":"2023011906415578800_btac803-B33","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1093\/bioinformatics\/btz513","article-title":"Modelling cancer progression using mutual hazard networks","volume":"36","author":"Schill","year":"2020","journal-title":"Bioinformatics"},{"key":"2023011906415578800_btac803-B34","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1038\/nrg.2016.170","article-title":"The evolution of tumour phylogenetics: principles and practice","volume":"18","author":"Schwartz","year":"2017","journal-title":"Nat. Rev. Genet"},{"key":"2023011906415578800_btac803-B35","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0025-5564(02)00086-X","article-title":"Estimating an oncogenetic tree when false negatives and positives are present","volume":"176","author":"Szabo","year":"2002","journal-title":"Math. Biosci"},{"key":"2023011906415578800_btac803-B36","author":"Szabo","year":"2022"},{"key":"2023011906415578800_btac803-B37","doi-asserted-by":"crossref","first-page":"e00961","DOI":"10.7554\/eLife.00961","article-title":"Phenotypic landscape inference reveals multiple evolutionary paths to C4 photosynthesis","volume":"2","author":"Williams","year":"2013","journal-title":"Elife"},{"key":"2023011906415578800_btac803-B38","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199602605.001.0001","volume-title":"Molecular Evolution: A Statistical Approach","author":"Yang","year":"2014"},{"key":"2023011906415578800_btac803-B39","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1093\/bioinformatics\/bts168","article-title":"Estimating the order of mutations during tumorigenesis from tumor genome sequencing data","volume":"28","author":"Youn","year":"2012","journal-title":"Bioinformatics"},{"key":"2023011906415578800_btac803-B40","doi-asserted-by":"crossref","first-page":"22889","DOI":"10.1109\/ACCESS.2018.2827024","article-title":"Inference of cancer progression with probabilistic graphical model from cross-sectional mutation data","volume":"6","author":"Zhang","year":"2018","journal-title":"IEEE Access"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/39\/1\/btac803\/48759287\/btac803.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btac803\/48763705\/btac803.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btac803\/48763705\/btac803.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T06:44:30Z","timestamp":1674110670000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btac803\/6895098"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2022,12,13]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac803","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,1,1]]},"published":{"date-parts":[[2022,12,13]]},"article-number":"btac803"}}