A 1.75-approximation algorithm for unsigned translocation distance
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 1045-1059 |
| Journal / Publication | Journal of Computer and System Sciences |
| Volume | 73 |
| Issue number | 7 |
| Publication status | Published - Nov 2007 |
Link(s)
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
Citation Format(s)
A 1.75-approximation algorithm for unsigned translocation distance. / Cui, Yun; Wang, Lusheng; Zhu, Daming.
In: Journal of Computer and System Sciences, Vol. 73, No. 7, 11.2007, p. 1045-1059.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
