Selecting Clustering Algorithms for Identity-By-Descent Mapping.

Area of Science:

• Genomics and Bioinformatics
• Computational Biology
• Population Genetics

Background:

• Massive biobanks enable insights into rare traits and diseases through identical-by-descent (IBD) mapping.
• Clustering algorithms are crucial for accurately identifying IBD-sharing individuals at scale.
• Evaluating the performance of existing clustering algorithms for IBD mapping is essential.

Purpose of the Study:

• To assess the suitability of common, fast, and scalable clustering algorithms for IBD mapping.
• To compare the statistical power and runtime of different clustering methods using a realistic benchmark.
• To identify optimal algorithms for large-scale IBD cluster detection.

Main Methods:

• Developed a realistic benchmark for local IBD graphs.
• Simulated 2.3 million clusters across 850 experiments to compare algorithm statistical power.
• Applied selected algorithms to the Population Architecture using Genomics and Epidemiology (PAGE) Study dataset and UK Biobank WES data.

Main Results:

• Infomomap and Markov Clustering (MCL) demonstrated high statistical power in most scenarios.
• These methods achieved a 30% increase in statistical power with a three-orders-of-magnitude reduction in runtime compared to state-of-the-art.
• Standard metrics like modularity do not predict statistical power for IBD mapping.
• Successfully identified 39 million local IBD clusters in the PAGE study and recovered rare genetic variation signals in UK Biobank data.

Conclusions:

• Infomap and MCL are highly effective and efficient algorithms for large-scale IBD mapping.
• The study provides a validated benchmark and demonstrates the practical application of these methods on real-world genomic datasets.
• An efficient implementation is provided to facilitate scalable IBD clustering across diverse populations.