Indexed by:
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:
Reprint 's Address:
Email:
Version:
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
Affiliated Colleges: