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 | Citation: | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.