@techreport{TR-IC-12-27,
number = {IC-12-27},
author = {Priscila Biller and João Paulo Pereira Zanetti and Pedro
Feijão and João Meidanis},
title = {{On the algebraic genome median}},
month = {December},
year = {2012},
institution = {Institute of Computing, University of Campinas},
note = {In English, 15 pages.
\par\selectlanguage{english}\textbf{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. Recently, Feijão and
Meidanis extended the algebraic theory for genome rearrangement
to allow for linear chromosomes, thus yielding a new
rearrangement model (the algebraic model), very close to the
celebrated DCJ model. \par In this paper, we study the genome
median problem under the algebraic model, whose complexity is
currently open, proposing a more generalized form of the
problem, the matrix median problem, that can be approximated in
linear time to a factor of $\frac{4}{3}$ of the optimum. The
study of the matrix median might help in the solution of the
algebraic median problem.
}
}