AI summaryⓘ
The authors extend a classic method for identifying where gene duplications happened in the evolutionary history of species, which originally worked only on simple trees, to more complex structures called phylogenetic networks. They created an algorithm, NetEC, that can test and find the best places for these duplication events even when species histories involve mixing or blending (reticulations). Although parts of their method run quickly, the overall problem can be very complex, so they also provide a faster but approximate option. They show their approach works well on both simulated data and a large real dataset with thousands of gene histories, revealing accurate duplication events despite the complicated evolutionary scenarios.
gene duplicationphylogenetic networksspecies treeduplication episodesdynamic programmingreticulationevolutionary biologyalgorithm complexitygenome evolutionPandanales
Authors
Paweł Górecki, Agnieszka Mykowiecka, Jarosław Paszek
Abstract
The classical duplication episode clustering (EC) model introduced by Guigó et al. in the 1990s provides a foundational approach for inferring genomic duplication events crucial to understanding genome evolution. This model clusters single gene duplications from a collection of gene trees at locations in the species tree to minimize the total number of such locations, called duplication episodes. Here, we introduce NetEC, a novel extension of this problem to phylogenetic networks. To solve NetEC, we first develop a polynomial-time dynamic programming (DP) algorithm for testing whether a given set of network nodes can serve as episode locations. We then propose a main inference algorithm that utilizes this DP component to optimize the episode count; while the feasibility test runs in polynomial time, the full optimization has exponential worst-case complexity, and an optional heuristic mode is provided for larger instances. We also propose an extended episode analysis procedure that identifies additional genomic duplication candidates below reticulation nodes, complementing the main algorithm by resolving potential upward clustering of duplications induced by reticulation. We evaluate our method on simulated data and on an empirical Pandanales dataset comprising over 29,000 gene trees, demonstrating exact and accurate inference of genomic duplication events even in the presence of multiple reticulations.