Parallel strategy for exploring the solution space of sorting by reversals

The problem of sorting a signed permutation by reversals is inspired and motivated by comparative genomics. In comparative genomics, algorithms that sort a signed permutation by reversals are often used to propose evolutionary scenarios of large-scale genomic mutations between species. Following the first polynomial time solution of this problem, several improvements has been published on the subject. In 2008, Braga et al. proposed an algorithm to perform the enumeration of traces that sort a signed permutation by reversals. This algorithm has exponential complexity in both time and space. In this paper, we propose a parallel approach to address this problem.