Reconstruction of permutations distorted by reversal errors Original Research Article

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 image generated by reversals. It is shown that for any image an arbitrary permutation image is uniquely reconstructible from four distinct permutations at reversal distance at most one from image 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 image and from two permutations with a probability image as image. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least image erroneous patterns are required in order to reconstruct an arbitrary permutation.