Simultaneous identification of duplications, losses, and lateral gene transfers
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Article number | 6205730 |
Pages (from-to) | 1515-1528 |
Journal / Publication | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
Volume | 9 |
Issue number | 5 |
Publication status | Published - 2012 |
Link(s)
Abstract
We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m+3 k/c n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m+2.78 k/cn). © 2004-2012 IEEE.
Research Area(s)
- fixed-parameter algorithms, Phylogenetic trees, reconciliations
Citation Format(s)
Simultaneous identification of duplications, losses, and lateral gene transfers. / Chen, Zhi-Zhong; Deng, Fei; Wang, Lusheng.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 9, No. 5, 6205730, 2012, p. 1515-1528.
In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 9, No. 5, 6205730, 2012, p. 1515-1528.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review