Exact and efficient phylodynamic simulation from arbitrarily large populations.

Area of Science:

• Phylodynamics
• Computational Biology
• Evolutionary Genetics

Background:

• Biological studies often infer evolutionary history from sampled individuals, resulting in ascertained trees that are subsets of complete population trees.
• Ascertained trees can be distorted by sampling biases, necessitating models that account for both population dynamics and ascertainment processes.
• Simulating these trees is vital for phylodynamic modeling and benchmarking inference methods, but computationally expensive due to large population sizes.

Purpose of the Study:

• To develop a computationally efficient algorithm for simulating ascertained evolutionary trees.
• To overcome the prohibitive computational costs associated with simulating large population trees in phylodynamics.
• To enable simulations from extremely large populations essential for advancing inference methods.

Main Methods:

• Proved the existence of an equivalent process with complete sampling and no death for partially ascertained processes.
• Leveraged this theoretical finding to develop a novel, highly efficient tree simulation algorithm.
• The algorithm's computational cost scales linearly with the size of the final simulated tree, independent of population size.

Main Results:

• Developed an algorithm that significantly reduces the computational burden of simulating evolutionary trees.
• Enabled simulations from population sizes previously computationally intractable.
• The algorithm's efficiency is independent of the underlying population size.

Conclusions:

• The new algorithm offers an unprecedented speedup for tree simulations in phylodynamics.
• This advancement will facilitate the development of novel inference methods requiring extensive simulation data.
• The method is applicable to general multi-type birth-death-mutation-sampling models.