Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
详细信息 查看全文
- 作者：Katharina T. Huber ; Leo van Iersel ; Vincent Moulton ; Celine Scornavacca…
- 关键词：Phylogenetic tree ; Phylogenetic network ; Polynomial ; time algorithm ; Exponential ; time algorithm ; NP ; hard ; Supernetwork ; Trinet ; Aho algorithm
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：77
- 期：1
- 页码：173-200
- 全文大小：988KB
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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 \(\mathbb {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 phylogenetic networks.