Genome Matrices and the Median Problem

par

Joao Meidanis

 University of Campinas, Brazil

Résumé:

The genome median problem is an important problem in phylogenetic reconstruction under
rearrangement models. It can be stated as follows: Given three genomes, find a fourth that
minimizes the sum of the pairwise rearrangement distances between it and the three input genomes.
In this paper, we model genomes as matrices and study the matrix median problem using the rank
distance. It is known that, for any metric distance, at least one of the corners is a 4343
-approximation of the median. Our results allow us to compute up to three additional matrix median
candidates, all of them with approximation ratios at least as good as the best corner, when the
input matrices come from genomes. We also show a class of instances where our candidates are
optimal. From the application point of view, it is usually more interesting to locate medians
farther from the corners, and therefore, these new candidates are potentially more useful. In
addition to the approximation algorithm, we suggest a heuristic to get a genome from an arbitrary
square matrix. This is useful to translate the results of our median approximation algorithm back
to genomes, and it has good results in our tests. To assess the relevance of our approach in the
biological context, we ran simulated evolution tests and compared our solutions to those of an
exact DCJ median solver. The results show that our method is capable of producing very good
candidates.