On reconstruction of signed permutations distorted by reversal errors

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 n >= 2 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 G(2n) whose vertices form a subgroup of the symmetric group Sym(2n). It is also proved that an arbitrary signed permutation is reconstructible from two distinct signed permutations with probability p2 similar to 1/3 as n --> infinity. In the case of at most two reversal errors it is shown that at least n (n + 1) distinct erroneous patterns are required in order to reconstruct an arbitrary signed permutation. (C) 2007 Elsevier B.V. All rights reserved.