Genome rearrangement analysis has attracted a lot of attention in phylogenetic computation and comparative genomics. Solving the median problems has been a focus as it provides the building block for maximum parsimony analysis of phylogeny and ancestral genomes. However, the Reversal Median Prob-lem(RMP) has been proved to be NP-hard and although there are several algorithms available, they all have great difficulty to compute when the genomes are distant. In this paper, we present a new heuristic algorithm that combines genetic algorithm (GA) with genomic sortings which can solve RMP in a limited time and space, especially in large scale and distant datasets. Our experimental results show that the new GA-based method can find optimal and near optimal results of problems range from easy to very difficult. Compared to existing parsimony methods which may severely underestimate the true number of evolutionary events, the inferred ancestral genomes are indeed closer to the true ancestors.
展开▼
