Outbreaks, Metastases and Homomorphisms: Phylogenetic Inference of Migration Histories of Heterogeneous Populations under Evolutionary and Structural Constraints

Abstract Many human diseases, including viral infections and cancers, are driven by the evolutionary dynamics of heterogeneous populations of genomic variants. A major type of evolutionary behavior of these populations is migration including viral transmissions and cancer metastatic spread. A common strategy for migration pathways reconstruction involves constructing a phylogenetic tree of observed genotypes and inferring its ancestral states corresponding to migration sites. Key challenges here include determining the conditions when a phylogenetic tree topology reflects the underlying migration tree structure, and balancing computational tractability, flexibility, and biological realism of inference algorithms and models. In this study, we address these challenges using the powerful machinery of graph homomorphisms, a mathematical concept that describes how one graph can be mapped onto another while preserving its structure. We investigate how structural constraints on migration patterns and migration tree topologies influence the relationship between phylogenies and migration trees, characterize trees compatible with a given phylogeny and propose a series of algorithms to assess whether given phylogenetic and migration trees are compatible under various migration scenarios. Leveraging our findings, we present a framework for inferring migration trees by sampling potential trees from a prior random tree distribution and identifying a subsample compatible with a given phylogeny. By varying prior tree distributions, this approach expands upon several existing models, offering a versatile strategy applicable to a variety of biological processes. We validate our methodology using simulated datasets and real data from studies of viral outbreaks and cancer metastasis, demonstrating its effectiveness across different contexts.