On reconstruction of signed permutations distorted by reversal errors Original Research Article

The problem of reconstructing signed permutations on n elements from their erroneous patterns distorted by reversal errors is considered in this paper. A reversal is the operation of taking a segment of the signed permutation, reversing it, and flipping the signs of its elements. The reversal metric is defined as the least number of reversals transforming one signed permutation into another. It is proved that for any image an arbitrary signed permutation is uniquely reconstructible from three distinct signed permutations at reversal distance at most one from the signed permutation. The proposed approach is based on the investigation of structural properties of a Cayley graph image whose vertices form a subgroup of the symmetric group image. It is also proved that an arbitrary signed permutation is reconstructible from two distinct signed permutations with probability image as image. In the case of at most two reversal errors it is shown that at least image distinct erroneous patterns are required in order to reconstruct an arbitrary signed permutation.