On Reversal and Transposition Medians

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.

Authors:

• Martin Bader

Keywords:

• Comparative genomics
• genome rearrangements
• me-dian
• reversals
• transpositions.

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.