PAUP - Phylogenetic Analysis Using Parsimony
introduction - exercise instructions - instructor hintsIntroduction
Our phylogenetic tree that we constructed last week (Wagner trees) had only four taxa and was very simple. With 4 taxa, however, there are only three possible trees (what are they?) and it is possible to construct the trees by hand. Systematists, however, are often interested in determining the relationships of many species and the calculations necessary to construct such large trees are enormous. The number of distinct trees for T terminal taxa can be computed with the following equation:
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
computers.
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 mtDNA.
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.
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 http://paup.csit.fsu.edu/downl.html
BACK TO TOP
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 mtDNA.
Exercise Instructions
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.
Describing trees
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?
Instructor Hints
PAUP versions are available for download at http://paup.csit.fsu.edu/downl.html
BACK TO TOP