Novel approach for parallelizing pairwise comparison problems as applied to detecting segments identical by decent in...

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Pairwise comparison problems are common in scientific research.
• Genomic datasets are rapidly expanding, making pairwise comparisons computationally intensive.
• Existing methods struggle with the scale of modern genomic data.

Purpose of the Study:

• To develop a generic algorithm for efficiently solving large-scale pairwise comparison problems.
• To reduce the computational complexity from O(n^2) to O(n) for pairwise tasks.
• To enable massive parallelization for handling large datasets.

Main Methods:

• A novel algorithm that decomposes large pairwise comparison problems into smaller, manageable subproblems.
• Implementation focuses on enabling massive parallelization for distributed computing environments.
• The algorithm is designed to be general and applicable to various pairwise comparison tasks.

Main Results:

• Demonstrated high efficiency in calling identical by descent (IBD) segments between all individuals in the UK Biobank dataset.
• Achieved a 250-fold reduction in computation time and a 750-fold reduction in memory usage compared to standard methods.
• The approach shows potential for significant performance gains in other IBD calling methods and general genomic pairwise comparisons.

Conclusions:

• The proposed algorithm offers a scalable and efficient solution for computationally demanding pairwise comparison problems in genomics.
• This method significantly enhances the feasibility of analyzing large-scale genomic datasets.
• The approach has broad applicability beyond IBD calling to other pairwise comparison tasks across scientific domains.