Least squares inference in phylogeny

Key takeaways

Least squares inference in phylogeny belongs to biology; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Least squares inference in phylogeny to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Least squares inference in phylogeny from memory before moving on to harder problems.

Reference excerpt

Least squares inference in phylogeny generates a phylogenetic tree based on an observed matrix of pairwise genetic distances and optionally a weight matrix. The goal is to find a tree which satisfies the distance constraints as best as possible.

Ordinary and weighted least squares The discrepancy between the observed pairwise distances D i j {\displaystyle D_{ij}}

and the distances T i j {\displaystyle T_{ij}} over a phylogenetic tree (i.e. the sum of the branch lengths in the path from leaf i {\displaystyle i} to leaf

j {\displaystyle j} ) is measured by

S = ∑ i j w i j ( D i j − T i j ) 2 {\displaystyle S=\sum _{ij}w_{ij}(D_{ij}-T_{ij})^{2}}

where the weights w i j {\displaystyle w_{ij}} depend on the least squares method used. Least squares distance tree construction aims to find the tree (topology and branch lengths) with minimal S. This is a non-trivial problem. It involves searching the discrete space of unrooted binary tree topologies whose size is exponential in the number of leaves. For n leaves there are 1 • 3 • 5 • ... • (2n-3) different topologies. Enumerating them is not feasible already for a small number of leaves. Heuristic search methods are used to find a reasonably good topology. The evaluation of S for a given topology (which includes the computation of the branch lengths) is a linear least squares problem. There are several ways to weight the squared errors

( D i j − T i j ) 2 {\displaystyle (D_{ij}-T_{ij})^{2}} , depending on the knowledge and assumptions about the variances of the observed distances. When nothing is known about the errors, or if they are assumed to be independently distributed and equal for all observed distances, then all the weights w i j {\displaystyle w_{ij}} are set to one. This leads to an ordinary least squares estimate. In the weighted least squares case the errors are assumed to be independent (or their correlations are not known). Given independent errors, a particular weight should ideally be set to the inverse of the variance of the corresponding distance estimate. Sometimes the variances may not be known, but they can be modeled as a function of the distance estimates. In the Fitch and Margoliash method

for instance it is assumed that the variances are proportional to the squared distances.

Generalized least squares The ordinary and weighted least squares methods described above assume independent distance estimates. If the distances are derived from genomic data their estimates covary, because evolutionary events on internal branches (of the true tree) can push several distances up or down at the same time. The resulting covariances can be taken into account using the method of generalized least squares, i.e. minimizing the following quantity

∑ i j , k l w i j , k l ( D i j − T i j ) ( D k l − T k l ) {\displaystyle \sum _{ij,kl}w_{ij,kl}(D_{ij}-T_{ij})(D_{kl}-T_{kl})}

where w i j , k l {\displaystyle w_{ij,kl}} are the entries of the inverse of the covariance matrix of the distance estimates.

Computational Complexity Finding the tree and branch lengths minimizing the least squares residual is an NP-complete problem. However, for a given tree, the optimal branch lengths can be determined in O ( n 2 ) {\displaystyle O(n^{2})} time for ordinary least squares, O ( n 3 ) {\displaystyle O(n^{3})} time for weighted least squares, and O ( n 4 ) {\displaystyle O(n^{4})} time for generalised least squares (given the inverse of the covariance matrix).

External links PHYLIP, a freely distributed phylogenetic analysis package containing an implementation of the weighted least squares method PAUP, a similar package available for purchase Darwin, a programming environment with a library of functions for statistics, numerics, sequence and phylogenetic analysis

References

Worked examples

Example 1 — a first encounter with Least squares inference in phylogeny

Start with the simplest possible case. Write down what Least squares inference in phylogeny claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In biology, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Least squares inference in phylogeny before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Least squares inference in phylogeny ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Least squares inference in phylogeny

In research: Least squares inference in phylogeny appears in biology research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Least squares inference in phylogeny in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Least squares inference in phylogeny is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational phylogenetics, so understanding it makes those chapters shorter.
In everyday life: Look for Least squares inference in phylogeny outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Least squares inference in phylogeny in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Least squares inference in phylogeny means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Least squares inference in phylogeny out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Least squares inference in phylogeny in simple terms?

Least squares inference in phylogeny generates a phylogenetic tree based on an observed matrix of pairwise genetic distances and optionally a weight matrix. The goal is to find a tree which satisfies the distance constraints as best as possible.

Why does Least squares inference in phylogeny matter?

Because it connects several biology ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Least squares inference in phylogeny?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Least squares inference in phylogeny.