14:00
15:00

Cluster reduction is a technique that can be used to speed up the construction of phylogenetic networks from sets of trees, or so we thought. Baroni, Semple, and Steel proved that cluster reduction is safe for 2 trees, that is, it preserves the optimality of the constructed network when the input consists of 2 trees. While there are inputs where cluster reduction isn’t applicable, Li and Zeh verified experimentally that on 2-tree inputs, it is the single most important technique for constructing optimal networks efficiently in practice, that not using cluster reduction would be folly. This talk shows cluster reduction isn’t safe for 8 or more trees. It will mention but not prove a number of other results in our paper: cluster reduction isn’t safe for computing an optimal orchard that displays 8 or more trees, cluster reduction is safe for 3 trees, and cluster reduction is safe for computing optimal tree-child networks. What happens with 4-7 trees is an open problem, but our intuition is that cluster reduction stops being safe already for 4 trees. Proving this would require different techniques than the ones we use. In particular, we prove that if there exists a set of t trees that cannot be displayed by a network with at most 2n reticulations, then there exists a set of 2t trees for which cluster reduction fails, but every set of 3 trees can be displayed by a network with at most 2n reticulations.

The second part of the talk focuses on proving that there exists a set of 4 trees that cannot be displayed by a network with at most 2n reticulations, which implies our result that cluster reduction isn’t safe starting with 8 trees. More generally, we show that for t = o(lg n), there exists a set of t trees for which the naïve network that displays these trees and has (t – 1)n reticulations is best possible up to lower order terms. Our result also shows that for t = lg n, there exists a set of t trees that cannot be displayed by a network with o(n lg n) reticulations. This is interesting because Bordewich and Semple showed that there exists even a tree-based network with O(n lg n) reticulations that displays all trees on n leaves. Our result shows that the number of reticulations increases by only a constant factor when going from lg n trees to all trees.

This is joint work with Leo van Iersel, Mark Jones, Kaari Landry, Simone Linz, and Mathias Weller.

[Norbert Zeh] (Dalhousie University)

Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178