A (1.5 + ε)-Approximation Algorithm for Unsigned Translocation Distance

ABSTRACT

Genome rearrangement is an important area in computational biology and bioinformatics. The translocation operation is one of the popular operations for genome rearrangement. It was proved that computing the unsigned translocation distance is NP-hard. In this paper, we present a (1.5 + ε)- approximation algorithm for computing unsigned translocation distance which improves upon the best known 1.75-ratio. The running time of our algorithm is O(n^2 + ( 4/ε )^1.5 √log( 4/ε )2 4^ε), where n is the total number of genes in the genome.

REFERENCES

• 1: A. Bergeron, J. Mixtacki, and J. Stoye, "On Sorting by Translocation," J. Computational Biology, vol. 13, no. 2, pp. 567-578, 2006.
• 2: A. Bergeron, S. Heber, and J. Stoye, "Common Intervals and Sorting by Reversals: A Marriage of Necessity," Bioinformatics, vol. 18, no. Suppl. 2, pp. S54-S63, 2002.
• 3: 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]
• 4: Y. Cui, L. Wang, and D. Zhu, "A 1.75-Approximation Algorithm for Unsigned Translocation Distance," Proc. 16th Int'l Symp. Algorithms and Computation (ISAAC '05), X. Deng and D.-Z. Du, eds., pp. 392-401, 2005. Full version is accepted for publication in J. Computer and System Sciences.
• 5: S. Hannenhalli, "Polynomial-Time Algorithm for Computing Translocation Distance between Genomes," Proc. Sixth Ann. Symp. Combinatorial Pattern Matching (CPM '95), Z. Galil and E. Ukkonen, eds., pp. 162-176, 1995.
• 6: Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
• 7: John D. Kececioglu , R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.604-613, January 22-24, 1995, San Francisco, California, United States
• 8: L. Lovász and M.D. Plummer, "Matching Theory," Annals of Discrete Math., vol. 29, 1986.
• 9: M. Ozery-Flato and R. Shamir, "An O(n^3/2¿log(n)) Algorithm for Sorting by Reciprocal Translocations," Proc. 17th Ann. Symp. Combinatorial Pattern Matching (CPM '06), M. Lewenstein and G. Valiente, eds., pp. 258-269, 2006.
• 10: Lusheng Wang , Daming Zhu , Xiaowen Liu , Shaohan Ma, An O(n²) algorithm for signed translocation, Journal of Computer and System Sciences, v.70 n.3, p.284-299, May 2005 [doi>10.1016/j.jcss.2004.12.005]
• 11: Daming Zhu , Lusheng Wang, On the complexity of unsigned translocation distance, Theoretical Computer Science, v.352 n.1, p.322-328, 7 March 2006 [doi>10.1016/j.tcs.2005.09.078]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

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

General Terms:
Algorithms, Design, Theory

Keywords:
Genome rearrangement, unsigned translocation, and approximation algorithms.