The hypercubic Mk model in reduced state space for the coupled, reversible coevolution of multiple binary characters

Many scientific questions involve the coevolution of coupled, binary features over time -- from phenotypes in evolutionary biology to mutations in cancer development. Evolutionary accumulation models (EvAMs) often neglect reversibility in these systems, uncertainty in observations, and/or phylogenetic connections between observations. By contrast, the Mk model from phylogenetic comparative methods supports reversibility, uncertainty, and relatedness, but compute time scales like O(4^L) in number of features L, making it challenging to apply to more than about six coupled, coevolving binary characters. Here, we introduce HyperMk2, a method using output from a Fitch-like parsimony algorithm to reduce the state space associated with many coevolving characters while retaining flexibility, reversibility, and phylogenetic information. This approach, while approximate, scales linearly in the number of distinct observations rather than exponentially in the number of characters, supporting the investigation of much larger systems than previously possible. We demonstrate how this method allows the inference of evolutionary dynamics of anti-microbial resistance in bacteria, including the identification of potential influences between characters, and discuss its broader application.