When Three Trees Go to Waruse asterix (*) to get italics

Leo van Iersel and Mark Jones and Mathias WellerPlease use the format "First name initials family name" as in "Marie S. Curie, Niels H. D. Bohr, Albert Einstein, John R. R. Tolkien, Donna T. Strickland"

2023

<p style="text-align: justify;">How many reticulations are needed for a phylogenetic network to display a given set of k phylogenetic trees on n leaves? For k = 2, Baroni, Semple, and Steel [Ann. Comb. 8, 391-408 (2005)] showed that the answer is n − 2. Here, we show that, for k ≥ 3 the answer is at least (3 /2 − epsilon)n. Concretely, we prove that, for each epsilon &gt; 0, there is some n ∈ N such that three n-leaf caterpillar trees can be constructed in such a way that any network displaying these caterpillars contains at least (3 /2 − epsilon)n reticulations. The case of three trees is interesting since it is the easiest case that cannot be equivalently formulated in terms of agreement forests. Instead, we base the result on a surprising lower bound for multilabelled trees (MUL-trees) displaying the caterpillars. Indeed, we show that one cannot do (more than an epsilon) better than the trivial MUL-tree resulting from a simple concatenation of the given caterpillars. The results are relevant for the development of methods for the Hybridization Number problem on more than two trees. This fundamental problem asks to construct a binary phylogenetic network with a minimum number of reticulations displaying a given set of phylogenetic trees.&nbsp;</p>

Phylogenetic Networks, Tree Containment, Caterpillar Tree, Hybridization Number

NonePlease indicate the methods that may require specialised expertise during the peer review process (use a comma to separate various required expertises).

Combinatorics, Evolutionary Biology, Graph theory

Steven Kelk, steven.kelk@maastrichtuniversity.nl, Vincent Moulton, v.moulton@uea.ac.uk, Charles Semple, charles.semple@canterbury.ac.nz, Simone Linz, s.linz@auckland.ac.nz, Louxin Zhang, matzlx@nus.edu.sg, Manuel Lafond, manuel.lafond@USherbrooke.ca, Kathrarina Huber, K.Huber@uea.ac.uk No need for them to be recommenders of PCI Math Comp Biol. Please do not suggest reviewers for whom there might be a conflict of interest. Reviewers are not allowed to review preprints written by close colleagues (with whom they have published in the last four years, with whom they have received joint funding in the last four years, or with whom they are currently writing a manuscript, or submitting a grant proposal), or by family members, friends, or anyone for whom bias might affect the nature of the review - see the code of conduct

2023-03-07 18:49:21

Simone Linz