When is a set of phylogenetic trees displayed by a normal network?
Journal of Computer and System Sciences · 2026-09 · 160 · 103811
DOI: 10.1016/j.jcss.2026.103811 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Computer and System Sciences, 2026-09. Verfasst von Magnus Bordewich und 2 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Royal Society of New Zealand Marsden Fund, Royal Society Te Apārangi.
Abstract (Originalsprache)
A normal network is uniquely determined by the set of phylogenetic trees that it displays. Given a set $\mathcal{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 $\mathcal{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 $\mathcal{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 $\mathcal{P}$. We then exploit these sequences to show that, for all $n\ge 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.
Förderung
- Royal Society of New Zealand Marsden Fund
- Royal Society Te Apārangi
Zitieren
APA
Bordewich, M., Linz, S., & Semple, C. (2026). When is a set of phylogenetic trees displayed by a normal network?. Journal of Computer and System Sciences, 160, 103811. https://doi.org/10.1016/j.jcss.2026.103811
Vancouver
Bordewich M, Linz S, Semple C. When is a set of phylogenetic trees displayed by a normal network?. Journal of Computer and System Sciences. 2026;160:103811. doi:10.1016/j.jcss.2026.103811
BibTeX
@article{Bordewich2026,
author = {Bordewich, Magnus and Linz, Simone and Semple, Charles},
title = {When is a set of phylogenetic trees displayed by a normal network?},
journal = {Journal of Computer and System Sciences},
year = {2026},
volume = {160},
pages = {103811},
doi = {10.1016/j.jcss.2026.103811}
}
EUVIMED