A 1.75-approximation algorithm for unsigned translocation distance

作者：

Highlights：

•

摘要

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].

论文关键词：Unsigned translocation distance,Approximation algorithm

论文评审过程：Received 20 August 2005, Revised 11 April 2006, Available online 14 March 2007.

论文官网地址：https://doi.org/10.1016/j.jcss.2007.03.009