Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/39370
DC FieldValue
dc.titleInferring a level-1 phylogenetic network from a dense set of rooted triplets
dc.contributor.authorJansson, J.
dc.contributor.authorSung, W.-K.
dc.date.accessioned2013-07-04T07:40:06Z
dc.date.available2013-07-04T07:40:06Z
dc.date.issued2004
dc.identifier.citationJansson, J.,Sung, W.-K. (2004). Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3106 : 462-471. ScholarBank@NUS Repository.
dc.identifier.issn03029743
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39370
dc.description.abstractGiven a set T of rooted triplets with leaf set L, we consider the problem of determining whether there exists a phylogenetic network consistent with T, and if so, constructing one. 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(n6) time when T is dense (i.e., contains at least one rooted triplet for each cardinality three subset of L), where n = |L|. Note that the size of the input is Θ(n3) if T is dense. We also give an O(n5)-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. © Springer-Verlag Berlin Heidelberg 2004.
dc.sourceScopus
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume3106
dc.description.page462-471
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

Google ScholarTM

Check


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