| Genome rearrangement is an important area in computational biology. It is significant in molecular biology. It has been proved that the genomes of two different species Drosophilia pseudoobscura and Miranda can be rearranged from one to the other by 17 reversal operations, in the milestone paper of Dobzhansky and Sturtevant more than 60 years ago.Genome is a set of chromosomes that is a sequence of genes. Genome rearrangement is an important mode of evolution in micro organisms, plants and animals. Although genome rearrangement is a complicated process, there are several basic operations. The 3 primary operations in the process of mutation are reversal, translocation and transposition. Translocation is one of the basic arrangement operations in the process of mammalian evolution. Tranlocation is the operation of severing two sequences of genes in the middle, connecting the subsequences belonging to two different sequences of genes and generating two new sequences of genes. Genome rearrangement is to find out the shortest sequence that changes one genome into another.This paper is about the algorithms of translocation and the implementations. Kececioglu and Ravi firstly gave a 2-approximation polynomial time algorithm for translocation. They also gave a 3/2-approximation polynomial time algorithm for computation of rearrangement distance for both reversal and translocation. Hannenhalli gave an O(n~3) polynomial time algorithm for translocation in 1996. ZHU Darning and MA Shaohan improved the time complexity of the algorithm to O(n~2logn) in 2001. In 2005, WANG LuSheng and ZHU Daming improved the time complexity of this algoritm to O(n~2). It is so far the fatest.It is illustrated that there are errors in their algorithms with grey edges leading to even-isolation. A new algorithm is given out for the problem. With the new algorithm,the detailed data structure and implemention are given out for the O(n~3) , O(n~2logn) and O(n~2) algorithms. There are comparison between the impletation... |
PDF Full Text Request