Optimality Criteria and Parsimony

• Phylogenetic reconstruction
  • Given a set of characters and character states, you can reconstruct a phylogeny
  • If all characters agree with each other, making a tree is easy -- find the tree that fits all the characters
• Informative vs.uninformative characters in parismony
• Synapomorphy
• Autapomorphy
• Character conflict
  • Homoplasy - apparent similarity that is not the result of common descent
  • Molecular data are inherently prone to homoplasy
  • Finding a tree that corresponds to the data involves a series of compromises.
• The text describes:
  • Algorithmic methods - a set of rules used to build a tree
  • Optimality methods - use a criterion to choose among alternative trees
    • Compare trees and find the best one
    • Branch swapping generates trees to be compared

Algorithms

• Algorithm - Any mechanical or recursive computational procedure (American Heritage Dictionary of the English Language. 1981. W. Morris, ed. Houghton Mifflin Co., Boston).
• All modern phylogenetic methods rely on algorithms to evaluate trees, but algorithmic methods differ from optimality methods in that they define the "best" tree as that which is found by the algorithm. By contrast, optimality methods can calculate a score based on some optimality criterion for any tree. When several candidate trees are compared, the tree that has the better score under the optimality criterion in use is considered to be the best tree. Thus with optimality methods the "best" tree is independent of the algorithm used to find the tree.

Optimality Criteria

• Parsimony
• Distance
• Maximum Likelihood

Maximum Parsimony

• Optimality criterion used by cladistic methods
• Between two trees, the one that requires the smallest number of changes is the best
• We have access only to the data at the tips of the tree
• Want to reconstruct the events that gave rise to the observed data
• Postulate
  • Dichotomously branching tree, and
  • Changes in the sequences over time
• Wagner parsimony - ordered characters; used in first example in book
• Fitch Parsimony - allows unordered multistate characters
• Example

1 10 20 |........|.........|.... Aster GTCATACCTGTGACATAGGTAATT Barnadesia ATCATACCTGTGACATAGGTAATT Cornus ATCTTCCCTGTGACATAGGTAATT Dioscorea ATCTTACCGGTTACTTACGCCATT Ephedra ATCTTCCCGGTTACTCTGGTAAGG

L = 14

One character shows homoplasy.

Determining the length of a tree

• Minimum number of steps for a given character can be determined in one pass
• We will look at a simple case with unordered characters
• See textbook p. 417 for ordered character example, as well as this example

1. Assign a state to each terminal node
2. (2) Visit first internal node
   1. is the intersection of states non-empty?
      1. Yes: set internal state to this.
      2. Else:
         1. set the state to the smallest set containing the states of the daughter nodes
         2. increase the tree length by 1.
3. Are you at the root of the tree?
   1. No: go to 2.
   2. Yes: go to 4.
4. (4) Is the state at this node the same as the outgroup state?
   1. Yes: Proceed to the next character
   2. Else: Add one to the length of the tree; proceed to next character

• This tells you the tree length, but does not map the characters onto the tree
• Determining a most parsimonious reconstruction requires another pass
• This reconstruction will not necessarily be unique!

Reconstructing character state changes

• Work up from root of tree
• Assign ancestral state from set of possibilities defined during tree length calculation
  • If the ancestral state is among the possibilities for the node, assign this
  • If not, arbitrarily pick one of the possibilities (will have to add assumptions)
• Rules for picking among alternatives
  • Accelerated transformation (ACCTRAN)
  • Delayed transformation (DELTRAN)
  • Minimized F-statistic (MINF)
• This method will tolerate ambiguity