Evolutionary Trees

The problem:

PPT Slide

PPT Slide

Terminology

PPT Slide

PPT Slide

Biological Assumptions

Character Homology

Bifurcating descent

PPT Slide

Estimation Principles

Distance relationships

PPT Slide

PPT Slide

PPT Slide

Nested character-states

PPT Slide

PPT Slide

PPT Slide

Likelihood

Suppose we see “AAAT”, what is the probability of drawing a base “A”?

Markov chain model of character evolution

Transition probability is specified from node to node

The character evolution model is determined by the form of the constraints on the transition matrix

The model is specified by the branching order of the tree, the initial state at the common ancestor, and a transition matrix for each branch

Given the model, the probability of any character pattern at the tips of the tree can be computed

For t number of taxa and n-state characters there are nt number of character patterns at the tips of the tree

PPT Slide

Algorithmic Structure

Optimization

Combinatorial Optimization

PPT Slide

Number of possible unrooted binary trees with n-taxa

PPT Slide

PPT Slide

PPT Slide

Solutions

Exhaustive search

Branch-and-bound search

PPT Slide

Divide-and-conquer

PPT Slide

Dynamic Programming

PPT Slide

PPT Slide

Heuristics

Greedy search

Stochastic search

Simulated annealing

Super-duper clever search

Heuristic solutions are dependent on ...

PPT Slide

Neighbor relations of trees

NNI configuration

TBR Configuration

PPT Slide

Statistical Properties

PPT Slide

Accuracy is some measurement of the dispersal of the estimator distribution around the “true” value

“?????”???We need a way of measuring deviation between trees

Partition metric

Consensus

Majority-rule consensus

Consensus tree can be used to define a deviation measure

Tree neighbor relations can be used to define deviation

PPT Slide

Power and Error

Power, Error, and Accuracy are not necessarily related to each other

Confidence Limits

PPT Slide

PPT Slide

Bootstrap resampling as a means of generating replicate samples (step 2)

Majority-rule consensus trees can be used to select confidence sets (step 4)

Misc. confidence limites