Identifying duplications and lateral gene transfers simultaneously and rapidly

This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in O(m + 3^kn) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between S and G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn² + 3^k) time. In the most interesting case where 3^k ≥ mn², our algorithm is O(n) times faster.