Sorting permutations by block-interchanges. (English) Zbl 0900.68232
Summary: 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. 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.
Online Encyclopedia of Integer Sequences:
a(n) = 1 + (6 + (11 + (6 + n)*n)*n)*n/24.Triangle read by rows: Hultman numbers: a(n,k) is the number of permutations of n elements whose cycle graph (as defined by Bafna and Pevzner) contains k cycles for n >= 0 and 1 <= k <= n+1.
The number of permutations of length n sortable by 2 block interchanges.
The number of permutations of length n sortable by 3 block interchanges.
a(n) is the number of permutations p of {1,..,n} such that the minimum number of block interchanges required to sort the permutation p to the identity permutation is maximized.
References:
| [1] | Aigner, M.; West, D. B., Sorting by insertion of leading elements, J. Combin. Theory Ser. A, 45, 306-309 (1987) · Zbl 0633.68060 |
| [2] | Bafna, V.; Pevzner, P. A., Sorting by transpositions, (Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (1995)), 614-623 · Zbl 0846.92007 |
| [3] | Bafna, V.; Pevzner, P. A., Genome rearrangements and sorting by reversals, SIAM J. Comput., 25, 272-289 (1996) · Zbl 0844.68123 |
| [4] | Caprara, A., Sorting by reversals is difficult (April 1996) |
| [5] | Even, S.; Goldreich, O., The minimum-length generator sequence problem is NP-hard, J. Algorithms, 2, 311-313 (1981) · Zbl 0467.68046 |
| [6] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062 |
| [7] | Hannenhalli, S., Polynomial algorithm for computing translocation distance, (Proc. 6th Ann. Symp. on Combinatorial Pattern Matching (CPM’95). Proc. 6th Ann. Symp. on Combinatorial Pattern Matching (CPM’95), Lecture Notes in Computer Science, 937 (1995), Springer: Springer Berlin), 162-176 |
| [8] | Jerrum, M. R., The complexity of finding minimum-length generator sequences, Theoret. Comput. Sci., 36, 265-289 (1985) · Zbl 0564.68031 |
| [9] | Kececioglu, J.; Sankoff, D., Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica, 13, 180-210 (1995) · Zbl 0831.92014 |
| [10] | Kececioglu, J. D.; Ravi, R., Of mice and men: Algorithms for evolutionary distances between genomes with translocation, (Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (1995)), 604-613 · Zbl 0846.92019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
