Mathematical and Computational BiologyOpen Access

ON TWO VARIATIONS OF THE REVERSAL MEDIAN PROBLEM

ZHONG ZHOU

Department of Computer Science, National University of Singapore, 13 Computing Drive, 117417, Singapore

Search for more papers by this author

MELVIN ZHANG

Department of Computer Science, National University of Singapore, 13 Computing Drive, 117417, Singapore

Search for more papers by this author

FANCHANG HAO

Department of Information Science and Technology, Shandong University of Political Science and Law, Jinan, China

Search for more papers by this author

, and

HON WAI LEONG

Department of Computer Science, National University of Singapore, 13 Computing Drive, 117417, Singapore

Search for more papers by this author

https://doi.org/10.1142/S2010194512005338Cited by:0 (Source: Crossref)

Abstract

We have developed an exact algorithm that solves certain instances of the Reversal Median Problem (RMP) when provided with additional input – the optimal sorting sequences between every pair of genomes. Our algorithm is able to provide an exact solution (the median genome) or determine that it is not able to do so for every instance of the problem. We have also proven the correctness of the algorithm in a theorem. RMP is the problem of finding an ancestral genome (the median) given the gene orders of three genomes. It is commonly encountered when constructing phylogeny, and is NP-hard. Two variations of the RMP were considered. In the first variation, we are given one sorting sequence for each pair of genomes. And in the second variation, we make use of a compact representation of all possible optimal sorting sequences for each pair of genomes that was developed by Braga et al.

Keywords:

References

A. Caprara, "The Reversal Median Problem", Research Report OR/01/12 DEIS, 2001 . Google Scholar
A. Caprara, R. Rizzi, "Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals", to appear in Journal of Combinatorial Optimization . Google Scholar
B. M. E. Moret , J. Tang and T. Warnow , Mathematics of Evolution and Phylogeny 321-352 , ed. O. Gascuel ( Oxford Univ. Press , 2005 ) . Google Scholar
D. Sankoff and J. Nadeau (eds.), Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics (World Scientific Pub., 2001) pp. 583–594. Google Scholar
I Pe'er and R. Shamir. "The Median Problems for Breakpoints are NP=Complete", ECCC Report Non. 71 (1998). University of Trier, 1998 . Google Scholar
I Pe'er and R. Shamir. "Approximation Algorithms for the Median Problem in the Break-point Model", in [8], 225-241 . Google Scholar
M. D. V. Braga, BaobabLUNA: The solution space of sorting by reversals (2010) . Google Scholar
M. E. Cosneret al., Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families (Kluwer Academic Pub., 2000) pp. 99–121. Crossref, Google Scholar
V. Rajanet al., BMC Bioinformatics 11, (2010). Google Scholar
Z. Zhou. On the Two Variations of Reversal Median Problem. Independent Project Report. National University of Singapore. 2010 . Google Scholar

Vol. 09

Metrics

Downloaded 108 times

History

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

ON TWO VARIATIONS OF THE REVERSAL MEDIAN PROBLEM

Abstract

Recommended