Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2006.06.022
Title: Inferring a level-1 phylogenetic network from a dense set of rooted triplets
Authors: Jansson, J. 
Sung, W.-K. 
Keywords: Algorithm
Phylogenetic network construction
Rooted triplet
Sorting network
Issue Date: 2006
Source: Jansson, J., Sung, W.-K. (2006). Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theoretical Computer Science 363 (1) : 60-68. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2006.06.022
Abstract: We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O (| T |2) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O (| T |5 / 3)-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets. © 2006 Elsevier B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39312
ISSN: 03043975
DOI: 10.1016/j.tcs.2006.06.022
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

37
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

33
checked on Nov 17, 2017

Page view(s)

47
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.