Simultaneous identification of duplications, losses, and lateral gene transfers.
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/c)n).
Division of Information System Design, Tokyo Denki University, Hatoyama, Saitama, Japan. zzchen@mail.dendai.ac.jp
Zhi-Zhong
ZZ
Chen
Fei
F
Deng
Lusheng
L
Wang
D000465:Algorithms; D019143:Evolution, Molecular; D020440:Gene Duplication; D022761:Gene Transfer, Horizontal / Q000235:genetics*; D008957:Models, Genetic