Estimating Genome Reversal Distance by Genetic Algorithm

Details Estimating Genome Reversal Distance by Genetic Algorithm Estimating Genome Reversal Distance by Genetic Algorithm

2004-05-05

arxiv.org/abs/cs/0405014v1

2003 IEEE Congress on Evolutionary Computation (CEC2003), Australia, IEEE Press, ISBN 0780378040, pp. 1157-1161, 2003

Computer Science

Artificial Intelligence

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Estimating Genome Reversal Distance by Genetic Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Estimating Genome Reversal Distance by Genetic Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating Genome Reversal Distance by Genetic Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467099