EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

When is a set of phylogenetic trees displayed by a normal network?

Magnus Bordewich, Simone Linz, Charles Semple

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →