| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Scylla Bioinformat, Campinas, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | Bulletin of Mathematical Biology; v. 78, n. 4, p. 786-814, APR 2016. |
| Web of Science Citations: | 3 |
| 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. (AU) | |
| FAPESP's process: | 12/14104-0 - Genome Rearrangement Problems Viewed Through Permutations, Matrices and Other Algebraic Concepts |
| Grantee: | Priscila Do Nascimento Biller |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 12/13865-7 - Algebraic Model for Genome Rearrangements |
| Grantee: | João Paulo Pereira Zanetti |
| Support Opportunities: | Scholarships in Brazil - Doctorate |