Rooting MADness

Rooting of phylogenetic trees is an important task, not only in evolutionary biology, but also in historical linguistics. So far, however, different rooting methods have not yet been sufficiently tested on linguistics data. Given that a new method for the automatic rooting of phylogenetic trees has been presented recently in biology, it seemed to be a good occasion to test in detail how well this new method works in comparison with alternative methods.

A few months ago, Mattis List pointed my attention to a (relatively) novel method for rooting phylogenetic trees with branch lengths: Minimal Ancestor Deviation rooting (Kümmel Tria et al. 2017). I will not go into the details of that algorithm here; the interested reader is referred to the mentioned article. Suffice it to give two quotations:

“The MAD method operates on binary unrooted trees and assumes that branch lengths are additive and that OTUs are contemporaneous.” (Kümmel Tria et al. 2017:1)

and

Branch ancestor deviations quantify the departure from strict clock-like behaviour, reflecting the level of rate heterogeneity among lineages. Wrong positioning of the root will lead to ­erroneous iden- tification of ancestor nodes, and apparent deviations will tend to be larger. We therefore infer the MAD root as the branch and position that minimizes the ancestor deviation […]. (Kümmel Tria et al. 2017: 2)

Several standard algorithms for phylogenetic infernce (e.g., Neighbor Joining, most off-the-shelf implementations of Maximum Likelihood) produce unrooted trees with branch lengths, and one needs to perform rooting as a separate step. So if this new kid in town is better than standard techniques such as midpoint rooting or outgroup rooting, this might come in handy.

Mattis and me were interested in how well this method performs in comparison to other rooting methods when applied to language trees derived from word lists. So I did a little experiment.

In Jäger (2018), I describe a method to apply automatic cognate detection to the data from the ASJP project (Wichmann et al. 2016), to extract character matrices and to apply Maximum Likelihood (ML) phylogenetic inference (Data and code are available at https://osf.io/cufv7/). In the meantime I have updated my database to ASJP v. 18. I used those data to infer ML trees for all Glottolog families for which ASJP contains at least 10 contemporaneous doculects, using the Glottolog classification as constraint tree. This gave me 64 unrooted trees. (To my dismay, I noticed along the way that the Glottolog classification that is shipped with ASJP is incomplete, so I extracted the Glottolog classification from the Glottolog website.)

I will use Ndu (a language family spoken in Papua New Guinea; traditionally considered as part of the Sepik family) as my running example. The Glottolog classification looks like this:

My ML-tree (obtained using the great software RAxML) is here:

The task is to find the correct root of the unrooted tree. However, the goldstandard does not identify a unique root, as Glottolog identifies three subgroups (Boikin, Ngala, and Nuclear Ndu).

Consider, e.g., the midpoint-rooted version of the ML tree:

This looks pretty bad, but can we quantify how bad it is?

One way to do it is to harness the triplet distance (Sand et al. 2014) between the rooted tree and the Glottolog goldstandard.

To see what this is about, consider the triplet (Yengoru, Yelogu, Wosera). In the goldstandard tree, it is grouped as (Yengoru, (Yelogu, Wosera)).

In the midpoint rooted tree, the grouping is (Wosera, (Yelogu, Yengoru)).

So this triplet is mis-classified by midpoint rooting. This evaluation is performed for each triplet of doculects. We disregard triplets like (Ngala, Boikin, Nyaura), which remain unresolved in the goldstandard. I call the number of misclassified triplets, divided by the number of goldstandard-resolved triplets, the Generalized Triplet Distance (GTD) between the rooted binary-branching tree and the goldstandard tree. (This is inspired by the Generalized Quartet Distance from Pompei et al. 2011).

I compared four rooting methods:

  1. MAD rooting.
  2. Midpoint rooting.
  3. Outgroup rooting. For this I created an artificial outgroup, with a character vector consisting entirely of 0s.
  4. Yule rooting. This method is derived from (Steel and McKenzie 2001). They give a formula to compute the likelihood of a rooted tree topology under the assumption that it was generated by a Yule process. The tree is rooted by calculating this likelihood for each possible root location and picking the one with the maximal likelihood. If there was a tie between different branches, I picked one at random.

Here is the MAD rooted tree for Ndu (which happens to be identical to the midpoint rooted version here):

The outgroup-rooted tree:

And the Yule-rooted version:

Outgroup rooting is the only method here that produces a tree consistent with the goldstandard. The GTDs are

  1. MAD: 0.61
  2. midpoint: 061
  3. outgroup: 0.00
  4. Yule: 0.21

It seems that both MAD and midpoint rooting are thrown off-stride here by the extra-long branch extending to Hanga Hundi.

When we perform this comparison over all 64 families, we get a different picture though:

mean GTD
MAD 0.0704
midpoint 0.0941
outgroup 0.1437
Yule 0.1771

These numbers indicate quite clearly that MAD and midpoint rooting are superior to both outgroup and Yule rooting. The difference between MAD and midpoint rooting seems to be small, but closer examination reveals that MAD is in fact substantially better than midpoint rooting.

  • MAD rooting achieved a GTD of 0.0 (meaning: finds a root fully consistent with the goldstandard) for 42 families (66%), but midpoint rooting only for 35 families (55%).
  • Both MAD and midpoints rooting have a median of 0, but the 75th quantile for MAD is at 0.10, and for midpoint at 0.16).

The difference is also clearly visible in the boxplots:

To conclude, Minimal Ancestor Deviation rooting seems to be better suited to root language phylogenies than more established methods. The usual disclaimers apply – we cannot be sure how much of these results depend on the particular data and phylogenetic inference method I used here. Different data might produce different results. Still, MAD rooting deserves to be included into the standard toolbox of phylogenetic linguistics.

Code and data, including all trees and the complete evaluation results, are available at https://github.com/gerhardJaeger/competititiveRooting.git.

References

Jäger, G. (2018): Global-scale phylogenetic linguistic inference from lexical resources, Scientific Data 5, 180189. URL: https://doi.org/10.1038/sdata.2018.189

Kümmel Tria, F. D., Landan, G., and T. Dagan (2017): Phylogenetic rooting using minimal ancestor deviation. Nature Ecology and Evolution. URL: http://dx.doi.org/10.1038/s41559-017-0193

Pompei, S., Loreto, V., & Kümmel Tria, F. D. (2011): On the accuracy of language trees. PloS one, 6(6), e20109.

Steel, M., & McKenzie, A. (2001): Properties of phylogenetic trees generated by Yule-type speciation models. Mathematical biosciences, 170(1), 91-112.

Sand et al. (2014): tqDist: a library for computing the quartet and triplet distances between binary or general trees, Bioinformatics, 30.14, 2079–2080.

Wichmann, Søren, Eric W. Holman, and Cecil H. Brown, eds., 2016. The ASJP Database, version 17. URL: https://asjp.clld.org

 

Cite this article as: gerhardjaeger, "Rooting MADness," in Computer-Assisted Language Comparison in Practice, 22/05/2019, https://calc.hypotheses.org/1899.

 

 

 


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.