Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-38036-5_14
Title: Reconstructing k-reticulated phylogenetic network from a set of gene trees
Authors: Vu, H.
Chin, F.
Hon, W.K.
Leung, H.
Sadakane, K.
Sung, K.W.K. 
Yiu, S.-M.
Issue Date: 2013
Source: Vu, H.,Chin, F.,Hon, W.K.,Leung, H.,Sadakane, K.,Sung, K.W.K.,Yiu, S.-M. (2013). Reconstructing k-reticulated phylogenetic network from a set of gene trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7875 LNBI : 112-124. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-38036-5_14
Abstract: The time complexity of existing algorithms for reconstructing a level-x phylogenetic network increases exponentially in x. In this paper, we propose a new classification of phylogenetic networks called k-reticulated network. A k-reticulated network can model all level-k networks and some level-x networks with x > k. We design algorithms for reconstructing k-reticulated network (k = 1 or 2) with minimum number of hybrid nodes from a set of m binary trees, each with n leaves in O(mn 2) time. The implication is that some level-x networks with x > k can now be reconstructed in a faster way. We implemented our algorithm (ARTNET) and compared it with CMPT. We show that ARTNET outperforms CMPT in terms of running time and accuracy. We also consider the case when there does not exist a 2-reticulated network for the input trees. We present an algorithm computing a maximum subset of the species set so that a new set of subtrees can be combined into a 2-reticulated network. © 2013 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/78317
ISBN: 9783642380358
ISSN: 03029743
DOI: 10.1007/978-3-642-38036-5_14
Appears in Collections:Staff Publications

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

Page view(s)

42
checked on Feb 17, 2018

Google ScholarTM

Check

Altmetric


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