title: Median Approximations for Genomes Modeled as Matrices.
abstract: 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 [Formula: see text]-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.
authors.affiliation: Institute of Computing, University of Campinas, Campinas, Brazil. jppzanetti@gmail.com.
authors.forename: Joao Paulo Pereira
authors.initials: JPP
authors.lastname: Zanetti
authors.affiliation: Institute of Computing, University of Campinas, Campinas, Brazil.
authors.forename: Priscila
authors.initials: P
authors.lastname: Biller
authors.affiliation: Institute of Computing, University of Campinas, Campinas, Brazil.|Scylla Bioinformatics, Campinas, Brazil.
authors.forename: Joao
authors.initials: J
authors.lastname: Meidanis
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D019143:Evolution, Molecular; D016678:Genome; D055641:Mathematical Concepts; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny
keywords: Approximated algorithms; Genome median problem; Phylogenetic reconstruction; Subspace decomposition