2024/07/09 by Bordewich, Magnus, Linz, Simone, Semple, Charles
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.06638
A normal network is uniquely determined by the set of phylogenetic trees that it displays. Given a set P of rooted binary phylogenetic trees, this paper presents a polynomial-time algorithm that reconstructs the unique binary normal network whose set of displayed binary trees is P, if such a network exists. Additionally, we show that any two rooted phylogenetic trees can be displayed by a normal network and show that this result does not extend to more than two trees. This is in contrast to tree-child networks where it has been previously shown that any collection of rooted phylogenetic trees can be displayed by a tree-child network. Lastly, we introduce a type of cherry-picking sequence that characterises when a collection P of rooted phylogenetic trees can be displayed by a normal network and, further, characterise the minimum number of reticulations needed over all normal networks that display P. We then exploit these sequences to show that, for all n≥ 3, there exist two rooted binary phylogenetic trees on n leaves that can be displayed by a tree-child network with a single reticulation, but cannot be displayed by a normal network with less than n-2 reticulations.