In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. This allows to define an operational distance on this space, as the minimum number of contractions and expansions required to transform one network into another. We highlight the difference between this distance and the computation of the maximum common contraction between two networks. Given its ability to outline a common structure between them, which can provide valuable biological insights, we study the algorithmic aspects of the latter. We first prove that computing a maximum common contraction between two networks is NP-hard, even when the maximum degree, the size of the common contraction, or the number of leaves is bounded. We also provide lower bounds to the problem based on the Exponential-Time Hypothesis. Nonetheless, we do provide a polynomial-time algorithm for weakly galled trees, a generalization of galled trees.
Marchand, Bertrand, Tahiri, Nadia, Fard, Shohreh Golpaigani et al. Finding maximum common contractions between phylogenetic networks. // Algorithms for Molecular Biology. – 2025. – DOI: 10.1186/s13015-025-00283-9. – URL: https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00283-9
Marchand, Bertrand, Tahiri, Nadia, Fard, Shohreh Golpaigani, Tremblay-Savard, Olivier, Lafond, & Manuel (2025). Finding maximum common contractions between phylogenetic networks. Algorithms for Molecular Biology. https://doi.org/10.1186/s13015-025-00283-9
Marchand, et al. “Finding maximum common contractions between phylogenetic networks.” Algorithms for Molecular Biology, 2025. doi:10.1186/s13015-025-00283-9.
@article{Marchand2025,
title = {Finding maximum common contractions between phylogenetic networks},
author = {Marchand and Bertrand and Tahiri and Nadia and Fard and Golpaigani, Shohreh and Tremblay-Savard and Olivier and Lafond and Manuel},
journal = {Algorithms for Molecular Biology},
year = {2025},
doi = {10.1186/s13015-025-00283-9},
url = {https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00283-9}
}
Background Aquaculture production of Atlantic salmon is a rapidly growing food sector, offering numerous advantages over terrestrial livestock. However, infectious diseases remain a major constraint, reducing production efficiency and...
The eukaryotic genome is folded into a functionally consequential three-dimensional architecture whose organizing principles have recently attracted substantial interest. Two physical mechanisms dominate current thinking: active loop...
Background The mitochondrial and nuclear genomes must coevolve to ensure cell homeostasis, legacy and consequence of their endosymbiotic origin. Mitonuclear coevolution is central to the oxidative phosphorylation pathway (OXPHOS), where...
Background Intrinsically disordered regions (IDRs) are widespread in proteins and play essential roles in regulation, signaling, and molecular recognition. IDRs of different lengths often exhibit distinct sequence and functional...