Algorithms of Phylogenetic Trees Construction

Fitch Margoliash Algorithm

Maximum Parsimony Algorithm

UPGMA Algorithm


Neighbor Joining Algorithm

Generation Description

Neighbor Joining(NJ) is a heuristic greedy algorithm. Unlike UPGMA, which chooses the neighbors with the minimum distances, Neighbor-Joining chooses the neighbors, which minimize the sum of branch length at each stage.

The tree is constructed by linking the pair of nodes, which give the smallest sum of branch length. When two nodes are linked, their common ancestral node is added to the tree and the terminal nodes with their respective branches are removed from the tree. This process converts the newly added common ancestor into a terminal node on a tree of reduced size. At each stage in the process, two terminal nodes are replaced by one new node. The process is completed when two nodes remain, separated by a single branch.

Let:

	            1       ___
            ri = ---------  \	   dik
                   N - 2    /__

We compute the new distance between node i and j:

            Dij = dij - (ri + rj)

Algorithm


Send comments and suggestions about PTC to khuri@cs.sjsu.edu or cherryyang@yahoo.com