Approach To Computation Of Genome Distance Based On Gene Order

Since the 90's in the 20th century, there is a great breakthrough in the progress of life science research. With the beginning of the Human Genome Project and the development of modern biotechnology, people accumulate a lot of data about biological information, which provide foundation for exploring the life secrety.So the research objection of Bioinformatics not only have sequences and genes but also have more and more whole genomes.Studing the phylogeny relations between organisms based on gene-order is an important research field in bioinformatics. Studing the phylogeny relations,finally,is to build a phylogeny tree.The key of building phylogeny tree is to present a effective algorithm to compute the distance between two genomes.People has presented some approximate algorithms.However,along with the expansion of the data scale and the complexity of the breakpoint graph based on genome,the error of these algorithms in computing the distance between genomes is not adapted.So,studing more effective algorithms for computing the distance between genomes has become an important region in building phylogeny tree based on genome rearrangement and attracted more and more attentions in the world.A new algorithm is presented in this paper, for computing the distance between genomes with the same content but different orders. Given a set of genomes with the same content but different orders, we construct a complete graph, and then produce a new genome called median genome that will minimize the sum of the distances from it to the others, which can be changed into a TSP problem. First, we apply Kruskal algorithm to find the median genome; second, we construct the breakpoint graph; finally, we compute the distance between the median genome and every genome.