So, with 5 taxa there are 15 possible trees, with 10 taxa
there are 2 x 10 6
possible trees, and with 50 taxa there are 3
x 10 74
possible trees! When systematists have very large data
sets it is difficult to construct evolutionary trees even when using the fastest
Today we will look at PAUP, one of the computer programs designed for finding
the most parsimonious trees. This program does not use an algorithm such as
we did with the Wagner Trees assignment. It actually searches through all
possible trees and finds the tree which has the fewest number of steps. Because
there are often an impossibly large number of possible trees to calculate,
searching algorithms have been developed to find trees.
Today we will use the simplest algorithm, a Heuristic search, to find the
most parsimonious tree for the evolution of primates. This search will create
an initial tree and seek to improve the tree by rearranging it in a way that
reduces its length. When the program can find no other way to improve on the
tree, it stops. The problem with this type of search is that we do not know
whether the computer has arrived at a global optimum or merely a local optimum.
The benefit of the heuristic search is that it is much quicker than the global
searching methods (called Branch and Bound and Exhaustive) .
Our characters will be base-pair positions along a section of the primate
Accessing PAUP and heuristic searching.
Access PAUP by clicking on the PAUP icon. You will be able to choose between
several example data sets. Choose the Primate mtDNA data set. After the data
has been processed, at the menu bar choose search and heuristic.
To look at the topology of the tree(s) select Trees from the menu
bar and Describe Trees. If there is more than one tree select All and Compress
vertically. To view the topology click on Describe. For the primate
mtDNA data set you will get two trees. How are they similar? How are they
different? A systematist would be interested in doing further analysis to
determine which tree is correct.
Simple data analysis
As a researcher you may feel that some types of trees of characters are
more appropriate or your analysis than others. You can include or exclude
different types of characters (why might you want to do this?) by selecting
Data from the menu bar and Include-Exclude Characters. Try excluding 3rd
position base pairs. Re-run the Heuristic Search. Is there still more than
one most parsimonious tree?
PAUP versions are available for download at
BACK TO TOP