Faster algorithms for sorting by transpositions and sorting by block interchanges

ABSTRACT

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O(n^3/2 &sqrt;logn). By means of the permutation tree, we can improve this algorithm to achieve time complexity O(nlogn). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from O(n²) down to O(nlogn).

REFERENCES

• 1: Bader, D. A., Moret, B. M. E., and Yan, M. 2001. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J. Comput. Biol. 8, 5, 483--491.
• 2: Vineet Bafna , Pavel A. Pevzner, Sorting by Transpositions, SIAM Journal on Discrete Mathematics, v.11 n.2, p.224-240, May 1998 [doi>10.1137/S089548019528280X]
• 3: Vineet Bafna , Pavel A. Pevzner, Genome Rearrangements and Sorting by Reversals, SIAM Journal on Computing, v.25 n.2, p.272-289, February 1996 [doi>10.1137/S0097539793250627]
• 4: Anne Bergeron, A very elementary presentation of the Hannenhalli-Pevzner theory, Discrete Applied Mathematics, v.146 n.2, p.134-145, 1 March 2005 [doi>10.1016/j.dam.2004.04.010]
• 5: Piotr Berman , Sridhar Hannenhalli , Marek Karpinski, 1.375-Approximation Algorithm for Sorting by Reversals, Proceedings of the 10th Annual European Symposium on Algorithms, p.200-210, September 17-21, 2002
• 6: Alberto Caprara, Sorting Permutations by Reversals and Eulerian Cycle Decompositions, SIAM Journal on Discrete Mathematics, v.12 n.1, p.91-110, Jan. 1999 [doi>10.1137/S089548019731994X]
• 7: Christie, D. A. 1999. Genome rearrangement problems. Ph.D. thesis, University of Glasgow.
• 8: David A. Christie, A 3/2-approximation algorithm for sorting by reversals, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.244-252, January 25-27, 1998, San Francisco, California, United States
• 9: David A. Christie, Sorting permutations by block-interchanges, Information Processing Letters, v.60 n.4, p.165-169, Nov. 25, 1996 [doi>10.1016/S0020-0190(96)00155-X]
• 10: Isaac Elias , Tzvika Hartman, A 1.375-Approximation Algorithm for Sorting by Transpositions, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.4, p.369-379, October 2006 [doi>10.1109/TCBB.2006.44]
• 11: Niklas Eriksen, (1 + ɛ)-Approximation of sorting by reversals and transpositions, Theoretical Computer Science, v.289 n.1, p.517-529, 23 October 2002 [doi>10.1016/S0304-3975(01)00338-3]
• 12: Sorting a bridge hand, Discrete Mathematics, v.241 n.1-3, p.289-300, October 28, 2001 [doi>10.1016/S0012-365X(01)00150-9]
• 13: Qian-Ping Gu , Shietung Peng , Hal Sudborough, A 2-approximation algorithm for genome rearrangements by reversals and transpositions, Theoretical Computer Science, v.210 n.2, p.327-339, Jan. 17, 1999 [doi>10.1016/S0304-3975(98)00092-9]
• 14: Sridhar Hannenhalli , Pavel A. Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Journal of the ACM (JACM), v.46 n.1, p.1-27, Jan. 1999 [doi>10.1145/300515.300516]
• 15: Tzvika Hartman , Ron Shamir, A simpler and faster 1.5-approximation algorithm for sorting by transpositions, Information and Computation, v.204 n.2, p.275-290, February 2006 [doi>10.1016/j.ic.2005.09.002]
• 16: Hartman, T., and Shamir, R. 2003. A simpler 1.5-approximation algorithm for sorting by transpositions. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching (Morelia, Michoacn, Mexico). Lecture Notes in Computer Science, vol. 2676. Springer, 156--169.
• 17: Hoot, S. B., and Palmer, J. D. 1994. Structural rearrangements, including parallel inversions, within the chloroplast genome of anemone and related genera. J. Molecular Evolution 38, 3, 274--281.
• 18: Kaplan, H., and Verbin, E. 2003. Efficient data structures and a new randomized approach for sorting signed permutatins by reversals. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching (Morelia, Michoacn, Mexico). Lecture Notes in Computer Science, vol. 2676. Springer, 170--185.
• 19: Guo-Hui Lin , Guoliang Xue, Signed genome rearrangement by reversals and transpositions: models and approximations, Theoretical Computer Science, v.259 n.1-2, p.513-531, May 28, 2001 [doi>10.1016/S0304-3975(00)00038-4]
• 20: Lin, Y., Lu, C., Chang, H., and Tang, C. 2005. An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species. J. Comput. Biol. 12, 1, 102--112.
• 21: Palmer, J. D., and Herbon, L. A. 1986. Tricircular mitochondrial genomes of brassica and raphanus: Reversal of repeat configurations by inversion. Nucleic Acids Res. 14, 24, 9755--9765.
• 22: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 23: Walter, M. E. T., Curado, L. R. A. F., and Oliveira, A. G. 2003. Working on the problem of sorting by transpositions on genome rearrangements. In Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching (Morelia, Michoacn, Mexico). Lecture Notes in Computer Science, vol. 2676. Springer, 372--383.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory

Keywords:
Block interchange, genome, permutation, time complexity, transposition, tree