zbMATH — the first resource for mathematics

Reconstruction of permutations distorted by reversal errors. (English) Zbl 1126.05006
Summary: The problem of reconstructing permutations on \(n\) elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group \(Sym_n\) generated by reversals. It is shown that for any \(n\geqslant 3\) an arbitrary permutation \(\pi \) is uniquely reconstructible from four distinct permutations at reversal distance at most one from \(\pi \) where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability \(p_{3}\rightarrow 1\) and from two permutations with a probability \(p_2 \sim \frac 13\) as \(n\rightarrow \infty \). A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least \(\frac{3}{2} (n-2)(n+1)\) erroneous patterns are required in order to reconstruct an arbitrary permutation.

05A05 Permutations, words, matrices
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text: DOI
[1] Banfa, V.; Pevzner, P.A., Genome rearrangements and sorting by reversals, SIAM J. comput., 25, 2, 272-289, (1996) · Zbl 0844.68123
[2] 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
[3] E. Konstantinova, Intersection of metric balls in transposition Cayley graphs, in: Proceedings of the VII International Conference on Discrete Models in Control System Theory, Moscow, March 4-6, 2006, pp. 172-178.
[4] E. Konstantinova, On reconstruction of signed permutations distorted by reversal errors, Discrete Math., accepted for publication. · Zbl 1136.05001
[5] Levenshtein, V.I., Reconstructing objects from a minimal number of distorted patterns, Dokl. acad. math., 354, 5, 593-596, (1997), (in Russian). (English translation: Dokl. Math. 55(3) (1997) 417-420) · Zbl 1008.94522
[6] Levenshtein, V.I., Efficient reconstruction of sequences, IEEE trans. inform. theory, 47, 1, 2-22, (2001) · Zbl 1029.94019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.