On Reversal and Transposition Medians

Authors: Martin Bader

Abstract:

During the last years, the genomes of more and more species have been sequenced, providing data for phylogenetic recon- struction based on genome rearrangement measures. A main task in all phylogenetic reconstruction algorithms is to solve the median of three problem. Although this problem is NP-hard even for the sim- plest distance measures, there are exact algorithms for the breakpoint median and the reversal median that are fast enough for practical use. In this paper, this approach is extended to the transposition median as well as to the weighted reversal and transposition median. Although there is no exact polynomial algorithm known even for the pairwise distances, we will show that it is in most cases possible to solve these problems exactly within reasonable time by using a branch and bound algorithm.

Keywords: Comparative genomics, genome rearrangements, me-dian, reversals, transpositions.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333446

References:

[1] Z. Adam and D. Sankoff. The ABCs of MGR with DCJ. Evolutionary Bioinformatics, 4:69-74, 2008.
[2] D. Bader, B. Moret, and M. Yan. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology, 8:483-491, 2001.
[3] M. Bader, M. Abouelhoda, and E. Ohlebusch. A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions. BMC Bioinformatics, 9:516, 2008.
[4] M. Bader and E. Ohlebusch. Sorting by weighted reversals, transposi- tions, and inverted transpositions. Journal of Computational Biology, 14(5):615-636, 2007.
[5] V. Bafna and P. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25(2):272-289, 1996.
[6] V. Bafna and P. Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics, 11(2):224-240, 1998.
[7] M. Bernt, D. Merkle, and M. Middendorf. Using median sets for inferring phylogenetic trees. Bioinformatics, 23:e129-e135, 2007.
[8] B. Bourque and P. Pevzner. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Research, 12(1):26-36, 2002.
[9] A. Caprara. The reversal median problem. INFORMS Journal on Computing, 15(1):93-113, 2003.
[10] D. Christie. Genome Rearrangement Problems. PhD thesis, University of Glasgow, 1998.
[11] I. Elias and T. Hartman. A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):369-379, 2006.
[12] B. Moret, S. Wyman, D. Bader, T. Warnow, and M. Yan. A new implementation and detailed study of breakpoint analysis. In Proc. 6th Pacific Symposium on Biocomputing, pages 583-594, 2001.
[13] I. Pe-er and R. Shamir. The median problems for breakpoints are NP- complete. Electronic Colloquium on Computational Complexity, 5(71), 1998.
[14] A. Siepel and B. Moret. Finding an optimal inversion median: Experi- mental results. In Proc. 1st Workshop on Algorithms, volume 2149 of Lecture Notes in Computer Science, pages 189-203. Springer-Verlag, 2001.
[15] E. Tannier, C. Zheng, and D. Sankoff. Multichromosomal genome median and halving problems. In Proc. 8th Workshop on Algorithms in Bioinformatics, volume 5251 of Lecture Notes in Computer Science, pages 1-13. Springer-Verlag, 2008.
[16] A. Xu. A fast and exact algorithm for the median of three problem - a graph decomposition approach. In Proc. 6th Annual RECOMB Satellite Workshop on Comparative Genomics, volume 5267 of Lecture Notes in Bioinformatics, pages 184-197. Springer-Verlag, 2008.
[17] S. Yancopoulos, O. Attie, and R. Friedberg. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21(16):3340-3346, 2005.
[18] F. Yue, M. Zhang, and J. Tang. Phylogenetic reconstruction from transpositions. BMC Genomics, 9(Suppl 2):S15, 2008.
[19] M. Zhang, W. Arndt, and J. Tang. An exact solver for the DCJ median problem. In Proc. 14th Pacific Symposium on Biocomputing, pages 138- 149. World Scientific, 2009.