A graph homomorphism approach for unraveling histories of metastatic cancers and viral outbreaks under evolutionary constraints

Kiril Kuzmin, Henri Schmidt, Maryam Kafi Kang, Sagi Snir, Benjamin J. Raphael and Pavel Skums ()
Additional contact information
Kiril Kuzmin: Georgia State University
Henri Schmidt: Princeton University
Maryam Kafi Kang: University of Connecticut
Sagi Snir: University of Haifa
Benjamin J. Raphael: Princeton University
Pavel Skums: University of Connecticut

Nature Communications, 2025, vol. 16, issue 1, 1-20

Abstract: Abstract Viral infections and cancers are driven by evolution of populations of highly mutable genomic variants. A key evolutionary process in these populations is their migration or spread via transmission or metastasis. Understanding this process is crucial for research, clinical practice, and public health, yet tracing spread pathways is challenging. Phylogenetics offers the main methodological framework for this problem, with challenges including determining the conditions when a phylogenetic tree reflects the underlying migration tree structure, and balancing computational efficiency, flexibility, and biological realism. We tackle these challenges using the powerful machinery of graph homomorphisms, a mathematical concept describing how one graph can be mapped onto another while preserving its structure. We focus on metastatic migrations and viral host-to-host transmissions in outbreak settings. We investigate how structural constraints on migration patterns influence the relationship between phylogenetic and migration trees and propose algorithms to evaluate trees consistency under varying conditions. Leveraging our findings, we introduce a framework for inferring transmission/migration trees by sampling potential solutions from a prior random tree distribution and identifying a subsample consistent with a given phylogeny. By varying the prior distribution, this approach generalizes several existing models, offering a versatile strategy applicable in diverse settings.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-025-63411-4 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-63411-4

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-025-63411-4

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().