Research On Phylogenetic Tree Reconstruction Algorithm

Phylogenetic tree is a kind of typological structure for describing the sequence and relationship of species revolution. A reliable phylogenetic inference will manifest the sequence of evolution, and facilitate our understanding of the history and mechanism of species evolution.Constructing an evolutionary tree is a typical NP-complete problem, Therefore it is of great significance to construct an algorithm capable of getting optimal approximate solutions. There are three frequently used method: distance method, maximum parsimony method, and maximum likelihood method.Three amendments are made to neighbor-joining method: First, a more precise evolution model is used to calculate the distance between sequences; second, sequences are used to generate multiple typological structures, and hence compensate the shortcoming of neighbor-joining method, which can generate only one typological structure; third, back mechanism is introduces to avoid the negative branch length in distance method and get a more accurate tree .The idea of genetic algorithm is brought in for maximum parsimony method, and a new method, i.e. genetic parsimony method is proposed, which, using the parsimonious tree length as fitness, randomly generates several early trees, and, through several times of selection, crossover, and mutation, will gradually converge to the wanted solution, i.e. the maximum parsimony tree.A new heuristic search method is devised for maximum likelihood method, which first constructs a starting tree, and then through branch swapping searches for trees best resembling the present optimal tree and locates a better tree. Repeat this process, till no more better trees are generated or the upper iteration limit is arrived and the program ends.The three adapted algorithms are tested with the most popular method of computer simulation to evaluate tree constructing algorithms. The results show that the accuracy of the improved algorithms is greatly improved.