Cargando…

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

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 tr...

Descripción completa

Detalles Bibliográficos
Autores principales: van Iersel, Leo, Kelk, Steven, Stamoulis, Georgios, Stougie, Leen, Boes, Olivier
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2017
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6428403/
https://www.ncbi.nlm.nih.gov/pubmed/30956378
http://dx.doi.org/10.1007/s00453-017-0366-5
_version_ 1783405405031890944
author van Iersel, Leo
Kelk, Steven
Stamoulis, Georgios
Stougie, Leen
Boes, Olivier
author_facet van Iersel, Leo
Kelk, Steven
Stamoulis, Georgios
Stougie, Leen
Boes, Olivier
author_sort van Iersel, Leo
collection PubMed
description 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.
format Online
Article
Text
id pubmed-6428403
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-64284032019-04-05 On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems van Iersel, Leo Kelk, Steven Stamoulis, Georgios Stougie, Leen Boes, Olivier Algorithmica Article 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. Springer US 2017-08-22 2018 /pmc/articles/PMC6428403/ /pubmed/30956378 http://dx.doi.org/10.1007/s00453-017-0366-5 Text en © The Author(s) 2017 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Article
van Iersel, Leo
Kelk, Steven
Stamoulis, Georgios
Stougie, Leen
Boes, Olivier
On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title_full On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title_fullStr On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title_full_unstemmed On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title_short On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems
title_sort on unrooted and root-uncertain variants of several well-known phylogenetic network problems
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6428403/
https://www.ncbi.nlm.nih.gov/pubmed/30956378
http://dx.doi.org/10.1007/s00453-017-0366-5
work_keys_str_mv AT vanierselleo onunrootedandrootuncertainvariantsofseveralwellknownphylogeneticnetworkproblems
AT kelksteven onunrootedandrootuncertainvariantsofseveralwellknownphylogeneticnetworkproblems
AT stamoulisgeorgios onunrootedandrootuncertainvariantsofseveralwellknownphylogeneticnetworkproblems
AT stougieleen onunrootedandrootuncertainvariantsofseveralwellknownphylogeneticnetworkproblems
AT boesolivier onunrootedandrootuncertainvariantsofseveralwellknownphylogeneticnetworkproblems