On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems

Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie, Olivier Boes

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.

Original languageEnglish
Pages (from-to)2993-3022
Number of pages30
JournalAlgorithmica
Volume80
Issue number11
DOIs
Publication statusPublished - Nov 2018

Fingerprint

Phylogenetic Network
Roots
Display devices
Phylogenetic Tree
Rooted Trees
Binary
Kernelization
Bisection
Argumentation
Placement
Display
Trivial
NP-complete problem
Choose

Keywords

  • APX-hardness
  • Binary trees
  • Fixed parameter tractability
  • Kernelization
  • NP-completeness
  • Phylogenetic networks

Cite this

van Iersel, Leo ; Kelk, Steven ; Stamoulis, Georgios ; Stougie, Leen ; Boes, Olivier. / On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems. In: Algorithmica. 2018 ; Vol. 80, No. 11. pp. 2993-3022.
@article{36e6bb75415c467a8ec627f6b4980e6d,
title = "On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems",
abstract = "The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.",
keywords = "APX-hardness, Binary trees, Fixed parameter tractability, Kernelization, NP-completeness, Phylogenetic networks",
author = "{van Iersel}, Leo and Steven Kelk and Georgios Stamoulis and Leen Stougie and Olivier Boes",
year = "2018",
month = "11",
doi = "10.1007/s00453-017-0366-5",
language = "English",
volume = "80",
pages = "2993--3022",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "11",

}

On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems. / van Iersel, Leo; Kelk, Steven; Stamoulis, Georgios; Stougie, Leen; Boes, Olivier.

In: Algorithmica, Vol. 80, No. 11, 11.2018, p. 2993-3022.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems

AU - van Iersel, Leo

AU - Kelk, Steven

AU - Stamoulis, Georgios

AU - Stougie, Leen

AU - Boes, Olivier

PY - 2018/11

Y1 - 2018/11

N2 - The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.

AB - The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the “root uncertain” variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.

KW - APX-hardness

KW - Binary trees

KW - Fixed parameter tractability

KW - Kernelization

KW - NP-completeness

KW - Phylogenetic networks

UR - http://www.scopus.com/inward/record.url?scp=85027830569&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027830569&partnerID=8YFLogxK

U2 - 10.1007/s00453-017-0366-5

DO - 10.1007/s00453-017-0366-5

M3 - Article

VL - 80

SP - 2993

EP - 3022

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 11

ER -