Identifying parsimonious pathways of accumulation and convergent evolution from binary data

How stereotypical, and hence predictable, are evolutionary and accumulation dynamics? Here we consider processes - from genome evolution to cancer progression - involving the irreversible accumulation of binary features (characters). We seek models of how these characters evolve in the form of transition networks, describing transitions between sets of characters, that reflect the simplest possible sets of character dynamics that can explain all the observations. A transition network supporting a single, deterministic dynamic pathway is maximally simple and lowest cost, and branches (corresponding to different possible "next steps" for evolution) increase cost, particularly if these branches are "deep", occurring at early stages in the dynamics. In this sense, the optimal description measures how stereotypical the evolutionary or accumulation process is - how predictable are its dynamics in independent samples or lineages. The problem is solvable in polynomial time for cross-sectional observations by building on an existing method, and we provide a polynomial-time estimate in the more general case of pairs of observed states. We use this approach to define a "stereotypy index" reflecting the extent of evolutionary predictability, and to efficiently estimate likely orderings of evolutionary events, common precursor steps, relationships between characters, and pathways of evolution. We demonstrate use cases in the evolution of antimicrobial resistance, organelle genomes, squamate and human morphology, and cancer progression, demonstrating that evolution in many cases evolution is significantly more stereotypical than expected from random character evolution. We provide a software implementation at https://github.com/StochasticBiology/hyperDAGs.