• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Pu, L. (Pu, L..) [1] | Zhu, D. (Zhu, D..) [2] | Jiang, H. (Jiang, H..) [3]

Indexed by:

Scopus

Abstract:

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. © 2020 Elsevier Inc.

Keyword:

Approximation algorithm; Complexity; Genome rearrangement; Translocation

Community:

  • [ 1 ] [Pu, L.]College of Mathematics & Computer Science, Fuzhou University, Fuzhou, China
  • [ 2 ] [Pu, L.]School of Computer Science and Technology, Shandong University, Jinan, China
  • [ 3 ] [Zhu, D.]School of Computer Science and Technology, Shandong University, Jinan, China
  • [ 4 ] [Jiang, H.]School of Computer Science and Technology, Shandong University, Jinan, China

Reprint 's Address:

  • [Zhu, D.]School of Computer Science and Technology, Shandong UniversityChina

Show more details

Related Keywords:

Related Article:

Source :

Journal of Computer and System Sciences

ISSN: 0022-0000

Year: 2020

Volume: 113

Page: 163-178

1 . 0 2 3

JCR@2020

1 . 1 0 0

JCR@2023

ESI HC Threshold:149

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:52/10058058
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1