Introduction to Bioinformatics and Computational Genomics

Week 8Phylogenetic trees

How to read a tree without over-reading it, why you cannot simply try every tree, and what a bootstrap value is actually measuring.

Questions this week answers

  • A branch has a bootstrap value of 95. What does that number actually measure?
  • Why do tree programs search heuristically instead of simply testing every tree?
  • What can you not conclude from a cladogram, however carefully you read it?

By the end of this week you can

  • Read a phylogram, a cladogram, and a rooted versus unrooted tree
  • Explain why exhaustive tree search is impossible
  • Interpret a bootstrap value correctly
  • Build and plot a neighbour-joining tree in R
0 of 4 done

  1. Why no computer will ever test every tree

    Set the taxa to 20 to reproduce the lecture's number. Then try to fix the problem by making the computer faster.

    945 trees is 0.0 ms at this rate, so exhaustive search is still possible here. At this speed it stays possible up to 14 taxa and not one more.

    Possible trees945(2n-3)!! for n = 6
    Time to test them all0.0 msat 1.0 x 10^9 per second
    Ages of the universewell under one
    Exhaustible in a day14 taxaat this rate
    A modest phylogeny has twenty; a gene family can have hundreds.
    A laptop manages perhaps a million. A large cluster, maybe a trillion.
    Count rooted trees
    Most methods produce unrooted trees; the root is added afterwards.
    Things to try0 of 3

    The 8.2 x 10^21 figure for 20 OTUs is from the week 8 phylogenetics lecture.

What should survive this week

  • A bootstrap value is the percentage of resampled replicates in which that branch appeared. It measures consistency of support within your data, not the probability that the branch is true.
  • There are about 8.2 x 10^21 rooted trees for 20 taxa. Exhaustive search is not slow, it is impossible.
  • Branch lengths mean nothing on a cladogram. Only a phylogram encodes how much change happened.
  • Most methods produce unrooted trees. The root is added afterwards, usually with an outgroup.