Parallel Algorithm to Enumerate Sorting Reversals for Signed Permutation

The arrangement distance between singlechromosomegenomes can be estimated as the minimumnumber of inversions required to transform the geneordering observed in one into that observed in theother. This measure, known as “inversion distance,”can be computed as the reversal distance betweensigned permutations. During the past decade, muchprogress has been made both on the problem ofcomputing reversal distance and on the relatedproblem of finding a minimum-length sequence ofreversals, which is known as “sorting by reversals.” Incomparative genomics, algorithms that sortpermutations by reversals are often used to proposeevolutionary scenarios of large-scale genomicmutations between species. One of the main problemsof such methods is that they give one solution while thenumber of optimal solutions is huge, with no criteria todiscriminate among them. Bergeron et al. started togive some structure to the set of optimal solutions, inorder to be able to deliver more presentable resultsthan only one solution or a complete list of allsolutions. This paper presents parallel algorithms toenumerate total sorting sequence of two signedpermutations. These algorithms are based onHannenhalli and Pevzner’s theory and composed offour key steps: Construct break point graph, computethe optimal distance, find the possible next reversalsequence and finally enumerate the total possiblesorting sequences.