Please use this identifier to cite or link to this item:
Type: Artigo
Title: Median Approximations For Genomes Modeled As Matrices
Author: Pereira Zanetti
Joao Paulo; Biller
Priscila; Meidanis
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 4/3-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.
Subject: Phylogenetic Reconstruction
Genome Median Problem
Approximated Algorithms
Subspace Decomposition
Editor: Springer
New York
Citation: Bulletin Of Mathematical Biology. Springer, v. 78, p. 786 - 814, 2016.
Rights: fechado
Identifier DOI: 10.1007/s11538-016-0162-4
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000375419200007.pdf644.25 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.