LSD

LSD estimates divergence times and substitution rates by applying least-squares molecular dating to phylogenetic trees for temporal reconstruction of evolutionary histories.

Key Features:

• Fast Dating Algorithms: Employs a Gaussian model closely related to the Langley–Fitch molecular-clock model and is robust to uncorrelated violations of the molecular clock.
• Handling Large Datasets: Processes very large input trees with more than 10,000 taxa.
• Serial Data Application: Works with serially sampled tips and estimates both the substitution rate and dates of all ancestral nodes.
• Root Position Estimation: Estimates the root position for unrooted trees as an alternative to midpoint rooting.
• Computational Efficiency: For rooted trees, the unconstrained setting is solved using linear algebra in linear time and the constrained setting uses an active-set method running in nearly linear time, while computations for unrooted trees are (nearly) quadratic.
• Comparison with Standard Methods: Achieves estimation accuracy similar to root-to-tip analysis, r8s (Langley–Fitch), and BEAST on simulated data while substantially reducing computation time.

Scientific Applications:

• Dating Ancestral Events: Dates ancestral events and produces time-scaled phylogenies for large evolutionary datasets comprising thousands of taxa.
• Viral Evolution Studies: Applied to viral datasets including human immunodeficiency virus (HIV) and influenza viruses to infer rates and timing of evolutionary change.
• Influenza pdm09 H1N1 Analysis: Validated on a dataset of 1,194 Influenza pdm09 H1N1 human pandemic strains, demonstrating fast and accurate dating performance.

Methodology:

Uses a Gaussian model related to the Langley–Fitch molecular-clock model, exploits the recursive structure of phylogenetic trees and relationships between least-squares and linear algebra to solve the unconstrained problem with linear-algebra methods, and applies an active-set method for the constrained problem; root estimation is performed for unrooted trees.