Study On The Distance-based Phylogenetic Tree Construction Algorithm And Platform Implementation

Phylogenetic tree is a tree structure that describes the evolutionary relationship between biological species,which can divided into rooted phylogenetic tree and non-rooted phylogenetic tree.The rooted phylogenetic tree reflects the evolutionary order of species,while the non-rooted phylogenetic tree reflects the distance between species.The methods based on distances are the most important methods for construction of phylogenetic trees,while NJ is most effective one.This thesis researchs NJ and its improved algorithms,including:Neighbor-Joining Method(shorts for NJ),FastJoin,RapidNJ,Clearcut and RandomNJ.The RandomNJ algorithm,which is an improving NJ is proposed in this thesis.When there are several minimums,it randomly chooses one of them.It has same time complexity with NJ.Some experiments about the above algorithms have been analyzed.The first experimental inputs are additive distance matrices,which have proved that NJ,RapidNJ and RandomNJ have the same accuracy,while Clearcut and FastJoin are lower accuracy.The second experimental inputs are non-additive distance matrices.As the number of leaf nodes increases,the distance between the initial phylogenetic tree and the generated phylogenetic tree increases.There is less difference between the trees constructed by Clearcut and those constructed by Fast Join.This thesis designs and implements the installable application software and application platform INJ for constructing the phylogenetic tree based on NJ and its improved algorithms.