The Ameliorative Algorithms Of Neighbor-Joining Method For Reconstructing Phylogenetic Trees

Reconstructing Phylogenetic Trees Problem(RPTP) is to reconstruct systematical evolutional relation and show it in form of the tree, on the basis of inferring biological evolutional history from the information of homologous nucleotide sequences. A node of the tree denotes each sequence and a branch show the evolutional distance.RPTP is a typical NP complete problem. In the practical computing, for the instances with large scale, no algorithm can get the accurate solutions within the acceptable time. Therefore, it is important to construct the algorithm to get the optimum tree in the acceptable time. In this thesis, two ameliorative algorithms was given , by analyzing Neighbor Joining method which is one of distance matrix method.First, we find that the accuracy of the distance exerts a tremendous influence on the efficiency of the algorithms, and it depends on the choice of evolutional models. There are the Jukes-Cautor single parameter model and Kimura two parameters model. Not considering the different probability of between transition and transversion, the Jukes-Cautor single parameter model is more coarse. But it is used in NJ algorithm. Then we use Kimura two parameters model and new rate-corrected distance in the first ameliorative algorithm, so the efficiency of the ameliorative algorithm is more than that of NJ algorithm.Then we consider another shortage of NJ algorithm. During the computational process the distances between new nodes and others have to calculate. In this way, it will bring the error when the distances are not accumulative. So we propose the second ameliorative algorithm. During the computational process of ameliorative algorithm, we use original as known conditions each time. Therefore it does not bring the error. Then calculating the sum of branches, we add all ones each time, including the branches that connect with worked nodes.Using computer simulation we study the efficiency of three algorithms——the count of obtaining the correct topology. From the result of the simulation, we find that the efficiency of ameliorative algorithms are much better than that of NJ. .