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

author:

Pu, Lianrong (Pu, Lianrong.) [1] | Zhu, Daming (Zhu, Daming.) [2] | Jiang, Haitao (Jiang, Haitao.) [3]

Indexed by:

EI Scopus SCIE

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. (C) 2020 Elsevier Inc. All rights reserved.

Keyword:

Approximation algorithm Complexity Genome rearrangement Translocation

Community:

  • [ 1 ] [Pu, Lianrong]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China
  • [ 2 ] [Pu, Lianrong]Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China
  • [ 3 ] [Zhu, Daming]Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China
  • [ 4 ] [Jiang, Haitao]Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China

Reprint 's Address:

  • [Zhu, Daming]Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China

Show more details

Version:

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 Discipline: COMPUTER SCIENCE;

ESI HC Threshold:149

JCR Journal Grade:3

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 2

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 3

Online/Total:136/10050884
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