title: A (1.5 + epsilon)-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 + epsilon)-approximation algorithm for computing unsigned translocation distance which improves upon the best known 1.75-ratio. The running time of our algorithm is O(n2 + (4/epsilon)1.5 square root log(4/epsilon )2(4/epsilon), where n is the total number of genes in the genome.
authors.affiliation: Shangdong University, Ji'nan, P.R. China.
authors.forename: Yun
authors.initials: Y
authors.lastname: Cui
authors.forename: Lusheng
authors.initials: L
authors.lastname: Wang
authors.forename: Daming
authors.initials: D
authors.lastname: Zhu
authors.forename: Xiaowen
authors.initials: X
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D002875:Chromosomes / Q000235:genetics*; D019295:Computational Biology / Q000379:methods; D016678:Genome / Q000235:genetics; D008957:Models, Genetic; D014178:Translocation, Genetic