Show simple item record

dc.contributor.authorGunawan, Andreas D.M.
dc.contributor.authorDasGupta, Bhaskar
dc.contributor.authorZhang, Louxin
dc.date.accessioned2017-01-17T19:37:35Z
dc.date.available2018-02-12T10:30:06Z
dc.date.issued2017-02
dc.identifier.bibliographicCitationGunawan, A. D. M., DasGupta, B. and Zhang, L. A decomposition > theorem and two algorithms for reticulation-visible networks. Information > and Computation. 2017. 252: 161-175. DOI: 10.1016/j.ic.2016.11.001.en_US
dc.identifier.issn08905401
dc.identifier.urihttp://hdl.handle.net/10027/21450
dc.descriptionCopyright © 2017 Elsevier B.V. or its licensors or contributors. ScienceDirect ® is a registered trademark of Elsevier B.V.en_US
dc.description.abstractIn studies of molecular evolution, phylogenetic trees are rooted binary trees, whereas phy- logenetic networks are rooted acyclic digraphs. Edges are directed away from the root and leaves are uniquely labeled with taxa in phylogenetic networks. For the purpose of validating evolutionary models, biologists check whether or not a phylogenetic tree (resp. cluster) is contained in a phylogenetic network on the same taxa. These tree and cluster containment problems are known to be NP-complete. A phylogenetic network is reticulation-visible if every reticulation node separates the root of the network from at least a leaf. We answer an open problem by proving that the problem is solvable in quadratic time for reticulation- visible networks. The key tool used in our answer is a powerful decomposition theorem. It also allows us to design a linear-time algorithm for the cluster containment problem for networks of this type and to prove that every galled network with n leaves has 2(n − 1) reticulation nodes at most.en_US
dc.description.sponsorshipThe work was supported by a Singapore MOE ARF Tier-1 Grant R-146-000-177-112 and the Merlion Programme 2013. DasGupta was supported by NSF Grant IIS-1160995. This work was also presented at the RECOMB’2016.en_US
dc.publisherElsevier Inc.en_US
dc.subjectPhylogenetic networksen_US
dc.subjectReticulation-visibilityen_US
dc.subjectTree containment problemen_US
dc.subjectCluster containment problemen_US
dc.titleA decomposition theorem and two algorithms for reticulation-visible networksen_US
dc.typeArticleen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record