A 1.75-approximation algorithm for unsigned translocation distance

Yun Cui; Lusheng Wang; Daming Zhu

doi:10.1016/j.jcss.2007.03.009

A 1.75-approximation algorithm for unsigned translocation distance

Yun Cui
, Lusheng Wang
, Daming Zhu

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

10 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1045-1059
Journal	Journal of Computer and System Sciences
Volume	73
Issue number	7
DOIs	https://doi.org/10.1016/j.jcss.2007.03.009
Publication status	Published - Nov 2007

Research Keywords

Approximation algorithm
Unsigned translocation distance

Access Output

10.1016/j.jcss.2007.03.009Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{f892508254f149acb77c0f1debfe2f67,

title = "A 1.75-approximation algorithm for unsigned translocation distance",

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]. {\textcopyright} 2007 Elsevier Inc. All rights reserved.",

keywords = "Approximation algorithm, Unsigned translocation distance",

author = "Yun Cui and Lusheng Wang and Daming Zhu",

year = "2007",

month = nov,

doi = "10.1016/j.jcss.2007.03.009",

language = "English",

volume = "73",

pages = "1045--1059",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "7",

}

TY - JOUR

T1 - A 1.75-approximation algorithm for unsigned translocation distance

AU - Cui, Yun

AU - Wang, Lusheng

AU - Zhu, Daming

PY - 2007/11

Y1 - 2007/11

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

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

KW - Approximation algorithm

KW - Unsigned translocation distance

UR - https://www.scopus.com/pages/publications/34547096293

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-34547096293&origin=recordpage

U2 - 10.1016/j.jcss.2007.03.009

DO - 10.1016/j.jcss.2007.03.009

M3 - RGC 21 - Publication in refereed journal

SN - 0022-0000

VL - 73

SP - 1045

EP - 1059

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 7

ER -

A 1.75-approximation algorithm for unsigned translocation distance

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this