Fast Computing Method For Unsigned Sorting By Reversals

Dobzhansky and Sturtevant began to study genome rearrangement in 1938.They published a milestone paper giving the proof that the genomes of two different drosophila can be rearranged from one to the other by 17 reversal operations. And the following researches prove that genome rearrangement is an important mode of evolution in microorganisms, plants and animals.A chromosome is a sequence of genes, and a genome is a set of chromosomes. Genome rearrangement is the process of changing the sequences of genes in genome. There are several basic operations: reversal, translocation and transposition. Only one or two of the operations are used in discussion of the genome rearrangement generally. Given two genomes A, B and the set of available rearrangement operations, computing the distance between A and B is equivalent to finding the shortest operation sequence that changes A to B. The problem of computing the distance between sequences of genes is genome sorting.This paper mainly studies the sorting by reversals. Caprara has proved that sorting by reversals is NP-hard. However Bafna and Pevzner have described a polynomial-time 7/4-approximation algorithm for the problem. Before the 7/4-approximation algorithm was known, Kececioglu and Sankoff had found a simple 2-approximation algorithm for the problem .The well known algorithm is found by Christie (1998), which had approximation ratio 3/2 and the time complexity of this algorithm is O(n~4) . In this paper we present an O(n~2) algorithm which has approximation ratio 3/2 by making an improvement to Christie's method of cycle decomposition and using the algorithm for signed sorting by reversals. We also design a GA for the unsigned sorting by reversals. The results of experiments tell us that our O(n~2) algorithm and GA are all better than the old 3/2-approximation algorithm.This paper, 1) give out a definition of Select-Graph and present a heuristic algorithm for getting the maximal independent set of Select-Graph, which simplify the method of cycle decomposition; 2) present an O(n~2) algorithm which has approximation ratio 3/2 by making an improvement to Christie's method of cycle decomposition and the method of finding sequence of reversals; 3) present a Genetic Algorithm for the unsigned sorting by reversals problem; 4) implement the 0{n~2) algorithm and GA in java . The results of experiments tell us that our algorithms are better than the old 3/2-approximation algorithm.The results and experiments have a significant meaning for the real works.