Sorting permutations by block-interchanges

被引:102
作者
Christie, DA
机构
[1] Department of Computing Science, University of Glasgow
基金
英国工程与自然科学研究理事会;
关键词
algorithms; combinatorial problems; sorting; string comparison; permutations;
D O I
10.1016/S0020-0190(96)00155-X
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Various global rearrangements of permutations, such as reversals and transpositions have recently become of interest because of their applications in genome analysis. The study of such rearrangements leads to computational problems that are of interest in their own right. In this paper we introduce an operation, called block-interchange, in which two substrings, or blocks, swap positions in the permutation. We demonstrate a polynomial-time algorithm for calculating the block-interchange distance of a permutation (i.e. the minimum number of block-interchanges required to transform the permutation to the identity). We also determine the block-interchange diameter of the symmetric group.
引用
收藏
页码:165 / 169
页数:5
相关论文
共 10 条
[1]   SORTING BY INSERTION OF LEADING ELEMENTS [J].
AIGNER, M ;
WEST, DB .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1987, 45 (02) :306-309
[2]   Genome rearrangements and sorting by reversals [J].
Bafna, V ;
Pevzner, PA .
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :272-289
[3]  
CAPRARA A, 1996, SORTING REVERSALS DI
[4]   THE MINIMUM-LENGTH GENERATOR SEQUENCE PROBLEM IS NP-HARD [J].
EVEN, S ;
GOLDREICH, O .
JOURNAL OF ALGORITHMS, 1981, 2 (03) :311-313
[5]   BOUNDS FOR SORTING BY PREFIX REVERSAL [J].
GATES, WH ;
PAPADIMITRIOU, CH .
DISCRETE MATHEMATICS, 1979, 27 (01) :47-57
[6]  
HANNENHALLI S, 1995, LECT NOTES COMPUT SC, V937, P162
[7]   THE COMPLEXITY OF FINDING MINIMUM-LENGTH GENERATOR SEQUENCES [J].
JERRUM, MR .
THEORETICAL COMPUTER SCIENCE, 1985, 36 (2-3) :265-289
[8]   EXACT AND APPROXIMATION ALGORITHMS FOR SORTING BY REVERSALS, WITH APPLICATION TO GENOME REARRANGEMENT [J].
KECECIOGLU, J ;
SANKOFF, D .
ALGORITHMICA, 1995, 13 (1-2) :180-210
[9]  
[No title captured]
[10]  
[No title captured]