Fast simulation of identity-by-descent segments.

Area of Science:

• Population Genetics
• Computational Biology
• Statistical Genetics

Background:

• Simulating haplotype segments identical by descent (IBD) is computationally intensive, with worst-case runtime complexity quadratic in sample size.
• Existing methods struggle with large sample sizes, taking hours to compute IBD segments for a few thousand individuals.

Purpose of the Study:

• To develop computationally efficient algorithms for simulating IBD segments.
• To enable large-scale genetic analyses, such as studying recent positive selection in biobanks.

Main Methods:

• Proposed two novel techniques motivated by coalescent and recombination processes to reduce simulation compute time.
• Developed a simulation algorithm with mathematical backing for high-probability outperformance over naive implementations.

Main Results:

• Observed average compute times for simulating detectable IBD segments scale approximately linearly with sample size.
• Achieved simulation times of a few seconds for sample sizes under 10,000 diploid individuals.
• Demonstrated significant speedup compared to existing methods, which take minutes to hours for similar sample sizes.

Conclusions:

• The efficient simulation algorithm makes intractable statistical inferences, such as parametric bootstrapping in large biobank analyses, feasible.
• This advancement facilitates the study of recent positive selection around genetic loci using IBD segments.