Videos

Maximum Common Contractions Between Phylogenetic Networks

Presenter
October 25, 2024
Abstract
I will present recent results on the comparison of phylogenetic networks based on edge contractions and expansions, as originally proposed by Robinson and Foulds for trees. These operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. The minimum number of contractions and expansions required to transform one network into another can therefore be used as a similarity measure. Moreover, the maximum common contraction between two networks can extract structural elements shared by two networks, which can provide valuable biological insight. In this talk, I will discuss differences between the operational distance and common contractions - the former defines a metric space but not the latter. We also provide algorithmic results on finding common contractions, namely NP-hardness even in restricted networks, but positive results on weakly-galled networks, a generalization of galled trees.