Reconstruction of permutations distorted by reversal errors

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 SymnSymn generated by reversals. It is shown that for any n⩾3n⩾3 an arbitrary permutation ππ is uniquely reconstructible from four distinct permutations at reversal distance at most one from ππ 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 p3→1p3→1 and from two permutations with a probability p2∼13 as n→∞n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least 32(n-2)(n+1) erroneous patterns are required in order to reconstruct an arbitrary permutation.