Fast simulation of identity-by-descent segments

Area of Science:

• Genetics
• Computational Biology
• Bioinformatics

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 for analyses involving thousands of individuals.

Purpose of the Study:

• To develop efficient algorithms for simulating IBD segments.
• To reduce the computational time required for IBD segment simulation.

Main Methods:

• Proposed two novel techniques motivated by coalescent and recombination processes.
• Developed a simulation algorithm with mathematically proven efficiency gains over naive implementations.

Main Results:

• Achieved average compute times scaling linearly with sample size, taking seconds for <10,000 diploid individuals.
• Demonstrated significant speedup compared to existing IBD simulation methods.

Conclusions:

• The efficient simulation algorithm makes large-scale genetic analyses, such as studying recent positive selection and parametric bootstrapping in biobanks, computationally feasible.
• Enables previously intractable statistical inferences in population genetics and genomics.