A 1.75-approximation algorithm for unsigned translocation distance

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1045-1059
Journal / PublicationJournal of Computer and System Sciences
Volume73
Issue number7
Publication statusPublished - Nov 2007

Abstract

The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a 1.75-approximation algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [J. Kececioglu, R. Ravi, Of mice and men: Algorithms for evolutionary distances between genomes with translocation, in: 6th ACM-SIAM Symposium on Discrete Algorithms, 1995, pp. 604-613]. © 2007 Elsevier Inc. All rights reserved.

Research Area(s)

  • Approximation algorithm, Unsigned translocation distance