Fitch Margoliash Algorithm

Maximum Parsimony Algorithm

Neighbor Joining Algorithm

UPGMA Algorithm


Algorithms of Phylogenetic Trees Construction

All tree building algorithms in bioinformatics depend on multiple sequence alignment of the sequences. The tree construction algorithm assumes that the multiple alignments among sequences are correct; errors in the alignments can lead to a very misleading tree.

Once the alignments are optimal, there are many different methods for creating phylogenetic trees. One way to classify tree building methods is based on the input data type. Character based methods use the individual substitutions among the sequences to determine the most likely ancestral relationships, while distance based methods first calculate the overall distance between all pairs of sequences, and then calculate a tree based on those distances. The most commonly applied distance based methods include Unweighted Pair Group Method using Arithmetic average(UPGMA), Neighbor Joining (NJ) and the Fitch Margoliash (FM). The most common character based methods include Maximum Parsimony (MP) and Maximum Likelihood (ML).

Another way of dividing tree building methods is by the way they construct trees. Cluster methods follow a set of steps (an algorithm) and arrive at a tree. For example, if we have five sequences we might start with three of them and decide where to place the fourth sequence. Given the resulting tree for four sequences, we then decide where to add the fifth and last sequence to our tree. It uses distance data and produces a single tree. There are no objective functions to compare to other trees. UPGMA and NJ fall in this class. Tree building methods in the second class uses optimality criteria to choose among the set of all possible trees. The methods first define an optimality criterion, such as minimum branch lengths, least number of events, highest likelihood, and then use a specific algorithm for finding trees with the best value for the objective function. It can identify many equally optimal trees, if such exist. FM, MP and ML belong to this class.


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