Metrics for comparing Lateral-Gene transfer networks

This work studies phylogenetic network comparison using edge contractions and expansions, defines an operational distance, proves computing maximum common contractions is NP-hard, and provides a polynomial-time algorithm for weakly galled trees.

This work studies the comparison of phylogenetic networks through edge contractions and expansions, showing that these operations connect the space of all networks on the same set of leaves even when cycles are forbidden, defines an operational distance based on the minimum number of such edits needed to transform one network into another, distinguishes this distance from the computation of a maximum common contraction, proves that finding a maximum common contraction is NP-hard under various constraints and provides lower bounds based on the Exponential-Time Hypothesis, and finally offers a polynomial-time algorithm for computing maximum common contractions in weakly galled trees, a generalization of galled trees, highlighting its potential for revealing common biological structures.

Source: Marchand, Tahiri, Fard, Tremblay-Savard and Lafond (2025)

  • Marchand, B., Tahiri, N., Tremblay-Savard, O., & Lafond, M. (2025). On the Comparison of LGT networks and Tree-based Networks. bioRxiv, 2025-11.
  • Marchand, B., Tahiri, N., Fard, S. G., Tremblay-Savard, O., & Lafond, M. (2025). Finding maximum common contractions between phylogenetic networks. Algorithms for Molecular Biology, 20(1), 18.

FUNDING:

  • Natural Sciences and Engineering Research Council of Canada/Fonds de recherche du Québec – Nature et technologies (NSERC/FRQNT) NOVA