Simultaneous identification of duplications, losses, and lateral gene transfers

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

23 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6205730
Pages (from-to)1515-1528
Journal / PublicationIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume9
Issue number5
Publication statusPublished - 2012

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