Maximum likelihood estimation for tree construction

Question

Could someone direct me to a resource (textbook chapter, lecture notes, online video, etc.) that demonstrates, in a mathematically or computationally rigorous way, how to use maximum likelihood estimation to generate a phylogenetic tree, given a set of aligned sequences?

I've found several resources which describe the procedure for maximum likelihood estimation, such as:

1. giving the formula and the parameters that need to be determined (which I already know);
2. how to use it for aligned sequences (I already know this), I am seeking a worked-out example.

Alternatively, if someone is willing to work out a small example, how would you use maximum likelihood estimation to generate a tree for the following three sequences?

organism_1 ATCG
organism_2 ATCC
organism_3 ATTT

Answer 1

@DataScienceNovice ... here's a rough explanation. Just to note a tree with three taxa doesn't really work as a tree - you need 4 taxa.

1. If we have tree 1 ((A,B),(C,D)) the probability of the tree is expressed as the summed log likelihood for each position 1, 2, 3 .... in the alignment. The probability is derived from a mutation matrix, thus certain mutations e.g. transitions A<->G; C<->T are more probable (high likelihood), e.g. transversions A<->C; A<->T; G<->C; G<->T are less probable in accordance with the matrix. This hypothetical matrix (most matrices) is scoring transitions as much more probable than transversions.

2. The 'total probability' expressed log likelihood for each column, i.e. each alignment position is added together leveraging an interesting property of logs (see final sentence of this paragraph). That becomes the 'score' or 'likelihood' for that tree. Note in the example you provided you have 4 alignment positions, so 4 probabilities of the log-likelihood will be added. Note, the probabilities are actually multiplied but log-likelihoods added is the same thing.

3. We will now rearrange the tree lets try tree 2 ((C,D),(B,G)), again the hypothetical matrix scores transition/transversions, thus essentially if this tree has higher transitions than the tree in point 1. that will provide a higher likelihood. The tree that maximises the transitions as sister groups will maximise the likelihood. Equally maximising transversions as the most divergent groups will maximise the likelihood of that tree.

4. Re-arrange the tree again tree 3 ... ((C,B),(D,A)) ... which tree has the highest transitions vs transversions? ...

5. In this example Tree 2 has the highest likelihood. Thus that is the maximum likelihood. Simple?

In the example you have the outcome will depend on the matrix. Alignment position 3 comprises a transition, whilst position 4 comprises a transition and a transversion. Generally transversions are 1:2 to 1:4 less likely even though there are twice as many. So the example you gave the 'tree' (you can't really have a tree with 3 taxa) would be ((organism2,organism3),organism1). This is against the total number of mutations because organism2 and organism3 has two mutations whilst organism2 and organism1 only have one, but the mutation types are different (also see point 3 below). In other words the occurrence of a transversion between organism1 against organism2,organism3, mean organism2 and organism3 are more likely sister groups even though they comprise 2 mutations (transitions) against the single mutation between organism1 and organism2.

A good maximum likelihood program for phylogenetics is RAxML.

---

1. The reality is it's not that simple because the mutation matrix is a function of the tree, which is a function of the mutation matrix and in technical tree building the matrix is also calculated alongside the total probability of the tree via maximum likelihood. Just to be clear it can be calculated as a separate maximum likelihood calculation and then fixed for the tree calculation, but it's not a good idea because of non-linear interactions.

2. In addition, mutation rate (heterogeneity) is also calculated via maximum likelihood.

3. The final thing to note is back-mutations are also calculated and that refers to past posts on this site, which I will link if I find them.

Complexity If the parameters are calculated via maximum likelihood simultaneous to the tree the parameter space becomes EXTREMELY large and the calculation is searching the tree landscape against the parameter landscape which becomes a multi-dimensional calculation.

Reality In reality much of a maximum likelihood calculation becomes about the search strategy because its impossible to traverse all of the parameter space so a heuristic estimate needs to be performed and the calculation can get stuck on lower plateaus of probability and fail to identify the tree maximum likelihood. This is the nuts and bolts of real world tree building.

Note However if you fix the matrix and the rate, which a lot of people do, then points 1 to 5 describe the maximum likelihood tree.