Algorithms of Phylogenetic Trees Construction
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
Start with a star tree with N nodes
dkm = 0.5 * (dim + djm - dij)                            for all m in N
dik = 0.5 * (dij + ri - rj) djk = 0.5 * (dij + rj - ri)
Terminate when N contains the last two nodes i and j, add the remaining edge between i and j with length dij
Send comments and suggestions about PTC to khuri@cs.sjsu.edu or cherryyang@yahoo.com