.png){kind=icon}
.png){kind=icon}
Return
A 14/11-approximation algorithm for sorting by short block-moves
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-010-4131-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Block-move is one of the popular operations for genome rearrangement. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. Heath and Vergara investigated the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation and devised a 4/3-approximation algorithm. In this paper, we present a new 14/11-approximation algorithm for this problem. Firstly, we devise an exact polynomial time algorithm for sorting a special kind of sub-permutations called umbrella; then we split the permutation into a series of related umbrellas and sort them greedily. We obtain a new lower bound of the short block-move distance by exploiting the properties of five kinds of sub-permutations. After some complicated analysis, we prove that the approximation ratio of the new algorithm is at most 14/11.
Keywords:
short block-move
approximation
algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K