Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Katharina Huber; Leo van Iersel; Vincent Moulton; Celine Scornavacca; Taoyang Wu

doi:10.1007/s00453-015-0069-8

Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca, Taoyang Wu

Research output: Contribution to journal › Article › peer-review

24 Citations (Scopus)

20 Downloads (Pure)

Abstract

Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3^{|X|} poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted 1 phylogenetic networks.

Original language	English
Pages (from-to)	173-200
Number of pages	28
Journal	Algorithmica
Volume	77
Issue number	1
Early online date	14 Sept 2015
DOIs	https://doi.org/10.1007/s00453-015-0069-8
Publication status	Published - Jan 2017

Keywords

phylogenetic tree
phylogenetic network
polynomial-time algorithm
exponential-time algorithm
NP-hard
supernetwork
trinet

Access to Document

10.1007/s00453-015-0069-8

final
This 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.
Accepted author manuscript, 435 KB

Katharina Huber
- K.Huberuea.acuk
- School of Computing Sciences - Associate Professor
- Computational Biology - Member
Person: Research Group Member, Academic, Teaching and Research
Vincent Moulton
- v.moultonuea.acuk
- School of Computing Sciences - Professor in Computational Biology
- Norwich Epidemiology Centre - Member
- Computational Biology - Group Lead
Person: Research Group Member, Academic, Teaching and Research
Taoyang Wu
- Taoyang.Wuuea.acuk
- School of Computing Sciences - Associate Professor in Computing Sciences
- Centre for Ecology, Evolution and Conservation - Member
- Computational Biology - Member
- Data Science and AI - Associate Member
- Health Computing - Associate Member
Person: Research Group Member, Research Centre Member, Academic, Teaching and Research

Cite this

@article{724c66a86fee4cb2b9ba548f7fe5e3a3,

title = "Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets",

abstract = "Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3^{|X|} poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted 1 phylogenetic networks.",

keywords = "phylogenetic tree, phylogenetic network, polynomial-time algorithm, exponential-time algorithm, NP-hard, supernetwork, trinet",

author = "Katharina Huber and {van Iersel}, Leo and Vincent Moulton and Celine Scornavacca and Taoyang Wu",

note = "{\textcopyright} The Author(s) 2015 This 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. ",

year = "2017",

month = jan,

doi = "10.1007/s00453-015-0069-8",

language = "English",

volume = "77",

pages = "173--200",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

AU - Huber, Katharina

AU - van Iersel, Leo

AU - Moulton, Vincent

AU - Scornavacca, Celine

AU - Wu, Taoyang

N1 - © The Author(s) 2015 This 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.

PY - 2017/1

Y1 - 2017/1

N2 - Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3^{|X|} poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted 1 phylogenetic networks.

AB - Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3^{|X|} poly(|X|)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted 1 phylogenetic networks.

KW - phylogenetic tree

KW - phylogenetic network

KW - polynomial-time algorithm

KW - exponential-time algorithm

KW - NP-hard

KW - supernetwork

KW - trinet

U2 - 10.1007/s00453-015-0069-8

DO - 10.1007/s00453-015-0069-8

M3 - Article

SN - 0178-4617

VL - 77

SP - 173

EP - 200

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets

Abstract

Keywords

Access to Document

Profiles

Katharina Huber

Vincent Moulton

Taoyang Wu

Cite this