Estimating Genome Reversal Distance by Genetic Algorithm
  Sorting by reversals is an important problem in inferring the evolutionary
relationship between two genomes. The problem of sorting unsigned permutation
has been proven to be NP-hard. The best guaranteed error bounded is the 3/2-
approximation algorithm. However, the problem of sorting signed permutation can
be solved easily. Fast algorithms have been developed both for finding the
sorting sequence and finding the reversal distance of signed permutation. In
this paper, we present a way to view the problem of sorting unsigned
permutation as signed permutation. And the problem can then be seen as
searching an optimal signed permutation in all n2 corresponding signed
permutations. We use genetic algorithm to conduct the search. Our experimental
result shows that the proposed method outperform the 3/2-approximation
algorithm.
