Algorithms of Phylogenetic Trees Construction
Generation Description
Fitch Margolish (FM) algorithm tries to optimize an objective function that quantifies the degree of distortion between the final tree path length and the observed distances. The Sum of Squares is defined as:
where Dij is the observed distance between species i and j, dij is the expected distance, computed as the sum of the lengths of the segments of the constructed tree from species i to species j.
Algorithm
________X________ i | --------| | |_______Y_________ j | | |______________Z__________ kUsing the additivity principle, the distances X, Y and Z can be computed as:
X = 0.5 * ( Dij + Dik - Djk )
Y = 0.5 * ( Dij + Djk - Dik )
Z = 0.5 * ( Dik + Djk - Dij )
Assign each sequence to its own OTU
When there are three OTUs left, join them together and calculate the branch lengths.
Start with all other possible sequence pairs, and repeat the process.
Calculate the sum of squares of each tree to find the trees that best fit the original data.
Send comments and suggestions about PTC to khuri@cs.sjsu.edu or cherryyang@yahoo.com