skip to main content
article

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

Published: 01 January 2008 Publication History

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]
A. Bergeron, "A Very Elementary Presentation of the Hannenhalli-Pevzner Theory," Discrete Applied Math., vol. 146, no. 2, pp. 134- 145, 2005.
[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]
S. Hannenhalli and P. Pevzner, "Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals," Proc. 27th Ann. ACM Symp. Theory of Computing (STOC '95), pp. 178-189, 1995.
[7]
J. Kececioglu and R. Ravi, "Of Mice and Men: Algorithms for Evolutionary Distances between Genomes with Translocation," Proc. Sixth Ann. ACM-SIAM Symp. Discrete Algorithms (SODA '95), K. Clarkson, ed., pp. 604-613, 1995.
[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]
L. Wang, D. Zhu, X. Liu, and S. Ma, "An O(n 2) Algorithm for Signed Translocation," J. Computer and System Sciences, vol. 70, pp. 284-299, 2005.
[11]
D. Zhu and L. Wang, "On the Complexity of Unsigned Translocation Distance," Theoretical Computer Science, vol. 352, no. 1, pp. 322-328, 2006.

Cited By

View all
  • (2021)Parallel memetic genetic algorithms for sorting unsigned genomes by translocations2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7743794(185-192)Online publication date: 11-Mar-2021
  • (2015)A factor-(1.408+ε) approximation for sorting unsigned genomes by reciprocal translocationsTheoretical Computer Science10.1016/j.tcs.2015.04.036607:P2(166-180)Online publication date: 23-Nov-2015

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 5, Issue 1
January 2008
159 pages

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2008
Published in TCBB Volume 5, Issue 1

Author Tags

  1. Genome rearrangement
  2. and approximation algorithms.
  3. unsigned translocation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Parallel memetic genetic algorithms for sorting unsigned genomes by translocations2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7743794(185-192)Online publication date: 11-Mar-2021
  • (2015)A factor-(1.408+ε) approximation for sorting unsigned genomes by reciprocal translocationsTheoretical Computer Science10.1016/j.tcs.2015.04.036607:P2(166-180)Online publication date: 23-Nov-2015

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media