Algorithms of Phylogenetic Trees Construction
Generation Description
The concept of parsimony in science maintains that simpler hypotheses should be preferred to more complex ones. Under the criterion of parsimony in phylogenetics, attributes shared between OTUs are assumed to have been inherited from a common ancestor rather than having evolved independently. In general, parsimony methods in phylogenetics operate by choosing the tree with the minimum number of character state changes.
The principle of maximum parsimony is to search for a tree that requires the smallest number of evolutionary changes to explain the differences observed among the OTUs under study. An evolutionary change is the transformation from one character state to another. For example:
The methods involve all possible tree topologies. A multiple sequence alignment is produced first to predict which sequence positions are likely to correspond. For each position, phylogenetic trees that require the smallest number of evolutionary changes are identified. This analysis is continued for every position in the sequences. Finally, the trees that produce the smallest changes overall for all positions are identified as parsimony trees. Often more than one tree with the same minimum number of changes is found, so that no unique tree can be inferred.
Informative Sites
In the parsimony method, only informative sites need to be analyzed. A site is phylogenetically informative only when there are at least two different kinds of characters, each represented at least two times. In other words, informative sites provide information that distinguishes between different topologies.
The procedure for inferring a maximum parsimony tree can be summarized as follows:
Algorithm
Set C = 0 and k = 2 * n - 1
Obtain the set of Rk
if k is leaf node
Minimum cost of tree = C
Send comments and suggestions about PTC to khuri@cs.sjsu.edu or cherryyang@yahoo.com