On the Approximability of Comparing Genomes with Duplicates - Angibaud, Sébastien; Fertin, Guillaume; Rusu, Irena; Thévenin, Annelyse; Vialette, Stéphane (Journal of Graph Algorithms and Applications, 2009)
A central problem in comparative genomics consists in computing a(dis-)similarity measure between two genomes, e.g. in order toconstruct a phylogenetic tree. A large number of such measures hasbeen proposed in the recent past: number of reversals,number of breakpoints, number of common orconserved intervals etc. In their initialdefinitions, all these measures suppose that genomes contain noduplicates. However, we now know that genes can be duplicated withinthe same genome. One possible approach to overcome this difficulty isto establish a one-to-one correspondence (i.e. a matching) betweengenes of both genomes, where the correspondence is chosen in order tooptimize the studied measure. Then, after a gene relabeling accordingto this matching and a deletion of the unmatched signed genes, twogenomes without duplicates are obtained and the measure can becomputed. <!----> In this paper, we are interested in three measures (number ofbreakpoints, number of common intervals and number ofconserved intervals) and three models of matching (exemplar,intermediate and maximum matchingmodels).We prove that, for each model and each measure M, computing amatching between two genomes that optimizes M is. We show that this result remains true even for twogenomes G1 and G2 such that G1 contains no duplicates and nogene of G2 appears more than twice. Therefore, our results extendthose of [,,].Besides, in order to evaluate the possible existence of approximationalgorithms concerning the number ofbreakpoints, we also study the complexity of thefollowing decision problem: is there an exemplarization (resp. anintermediate matching, a maximum matching) that induces nobreakpoint ? In particular, we extend a resultof [] by proving theproblem to be in the exemplar model for a new class ofinstances, we note that the problems are equivalent in theintermediate and the exemplar models and we show that the problem is in in themaximum matching model.Finally, we focus on a fourth measure, closely related to the number of breakpoints: the numberof adjacencies, for which we give several constant ratioapproximation algorithms in the maximum matching model, in the case where genomes containthe same number of duplications of each gene. <!----> Keywords: genome rearrangements, , duplicate genes,breakpoints, adjacencies, common intervals, conserved intervals,approximation algorithms. <!---->