A (1.5 + ε)-approximation algorithm for unsigned translocation distance

Yun Cui; Lusheng Wang; Darning Zhu; Xiaowen Liu

doi:10.1109/TCBB.2007.70216

A (1.5 + ε)-approximation algorithm for unsigned translocation distance

Yun Cui
, Lusheng Wang
, Darning Zhu
, Xiaowen Liu

Department of Computer Science

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

14 Citations (Scopus)

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 the unsigned translocation distance that improves upon the best known 1.75-ratio. The runtime of our algorithm is O(n² + (4/5)^1.5 √log(4/ε)2^4/ε), where n is the total number of genes in the genome. © 2008 IEEE.

Original language	English
Pages (from-to)	56-66
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	5
Issue number	1
DOIs	https://doi.org/10.1109/TCBB.2007.70216
Publication status	Published - Jan 2008

Research Keywords

Approximation algorithms
Genome rearrangement
Unsigned translocation

Access Output

10.1109/TCBB.2007.70216

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{88f31fb2f2974c07a19c2af3ca941bb9,

title = "A (1.5 + ε)-approximation algorithm for unsigned translocation distance",

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 the unsigned translocation distance that improves upon the best known 1.75-ratio. The runtime of our algorithm is O(n2 + (4/5)1.5 √log(4/ε)24/ε), where n is the total number of genes in the genome. {\textcopyright} 2008 IEEE.",

keywords = "Approximation algorithms, Genome rearrangement, Unsigned translocation",

author = "Yun Cui and Lusheng Wang and Darning Zhu and Xiaowen Liu",

year = "2008",

month = jan,

doi = "10.1109/TCBB.2007.70216",

language = "English",

volume = "5",

pages = "56--66",

journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",

issn = "1545-5963",

publisher = "IEEE",

number = "1",

}

TY - JOUR

T1 - A (1.5 + ε)-approximation algorithm for unsigned translocation distance

AU - Cui, Yun

AU - Wang, Lusheng

AU - Zhu, Darning

AU - Liu, Xiaowen

PY - 2008/1

Y1 - 2008/1

N2 - 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 the unsigned translocation distance that improves upon the best known 1.75-ratio. The runtime of our algorithm is O(n2 + (4/5)1.5 √log(4/ε)24/ε), where n is the total number of genes in the genome. © 2008 IEEE.

AB - 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 the unsigned translocation distance that improves upon the best known 1.75-ratio. The runtime of our algorithm is O(n2 + (4/5)1.5 √log(4/ε)24/ε), where n is the total number of genes in the genome. © 2008 IEEE.

KW - Approximation algorithms

KW - Genome rearrangement

KW - Unsigned translocation

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

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

U2 - 10.1109/TCBB.2007.70216

DO - 10.1109/TCBB.2007.70216

M3 - RGC 21 - Publication in refereed journal

C2 - 18245875

SN - 1545-5963

VL - 5

SP - 56

EP - 66

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

IS - 1

ER -

A (1.5 + ε)-approximation algorithm for unsigned translocation distance

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this