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), which can be modelled as Markov processes on a hypercubic transition network. We seek subgraphs of such networks that can generate a given set of paired before-after observations and minimize a topological cost function, involving criteria on out-branching which are interpretable in terms of biological parsimony. A transition network supporting a single, deterministic dynamic pathway is maximally simple and lowest cost, and branches (corresponding to possibly different next steps) increase cost, particularly if these branches are "deep", occurring at early stages in the dynamics. In this sense, the lowest-cost subgraph measures how stereotypical the evolutionary or accumulation process is, and also identifies good start points for likelihood-based inference. The problem is solvable in polynomial time for cross-sectional observations by building on an existing method due to Gutin, 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. We demonstrate use cases in the evolution of antimicrobial resistance, organelle genomes, and cancer progression, and provide a software implementation at https://github.com/StochasticBiology/hyperDAGs.