Sorting by Short Block-Moves |
| |
Authors: | L S Heath J P C Vergara |
| |
Affiliation: | (1) Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061-0106, USA. heath@cs.vt.edu., US;(2) Department of Information Systems and Computer Science, Ateneo De Manila University, Manila 0917, Philippines. jpv@admu.edu.ph., PH |
| |
Abstract: | Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications
in the study of genome rearrangements and in the design of interconnection networks. A short block-move is an operation on
a permutation that moves an element at most two positions away from its original position. This paper investigates the problem
of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3 -approximation algorithm
for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorithm for this class
of permutations is devised that employs graph matching techniques. A linear-time maximum matching algorithm for a special
class of grid graphs improves the time complexity of the algorithm for woven double-strip permutations.
Received June 1, 1997; revised July 25, 1998. |
| |
Keywords: | , Computational biology, Genome rearrangement, Approximation algorithms, Maximum matching, Permutations, |
本文献已被 SpringerLink 等数据库收录! |
|