Improvement And Application Of Neighbor-Joining Method For Phylogenetic Tree Reconstruction

Molecular phylogenetic analysis is one of the most important fields of Bioinformatics, he main task of which is to reconstruct a phylogenetic tree from a group of homologous DNA or protein sequences, by calculating the evolutionary distances between them, to show their evolutionary relationship. Usually, a phylogenetic tree is a binary tree, in which the leaf nodes stand for the species or the organisms, the tree topology indicates the phylogenetic relationship, and the length of branches figure out the evolutionary distance. There are three main types of methods to reconstruct phylogenetic trees: distance matrix method, parsimony method and likelihood method.Distance matrix methods have wide applications because of its simplicity and solid theory, but some of them may produce multiple phylogenetic trees ("tied trees") given a single set of homologous sequences in certain cases. One of such methods commonly used is Neighbor-Joining (NJ), which may also have the problem of"tied trees"although designed to produce a single phylogenetic tree unrelated to input orders of sequences. For the problem of"tied trees"in NJ, most popular softwares for phylogenetic analysis just output a topology of phylogenetic trees depending on its specific implementation, without handling the problem itself properly.The thesis gives a detailed analysis to the reasons for the"tied trees"problem in NJ, and then presents an Improved Neighbor-Joining algorithm (INJ). INJ is an extension to NJ, and NJ is s special case of INJ. During the iterative computation, NJ always generates a new taxonomic unit by merging an arbitrary pair of sequences or species with the minimum rate-corrected distance. But INJ can merge a multiple (less than three at present) of sequences or species with the same minimum distance, so it may produce a multifurcating phylogenetic tree. In the case that NJ trees are not unique, the corresponding INJ trees are usually single multifurcating trees. But otherwise, the corresponding INJ trees are always unique and the same as the NJ trees. Therefore, INJ gives a good solution to the problem of"tied trees"in NJ.In addition, the thesis implements a new molecular phylogenetic analysis system– Multi-Tree, which integrates both INJ and NJ. The system is a rich client application based on Microsoft .Net framework 2.0, including a lot of functions such as multiple sequences alignment and edit, distance matrix computation, several phylogenetic tree-building methods and viewing modes. The Multi-Tree system can be easily extended and maintained in the plug-in structure that can load multi-language user interface and business logic components at runtime.