A parallel algorithm for N-way interval set intersection.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Genome interval set comparison is crucial for understanding genomic feature relationships.
• Current methods for intersecting multiple interval sets are inefficient for large datasets.
• Advances in sequencing generate massive, multi-dimensional genomic data requiring efficient analysis.

Purpose of the Study:

• To develop a novel, efficient algorithm for identifying intersections among many sets of genomic intervals.
• To address the computational challenges posed by large-scale genomic data analysis.
• To improve the speed and parallelization capabilities for multi-set interval intersection.

Main Methods:

• A new "slice-then-sweep" algorithm was developed for intersecting N sets of genomic intervals.
• The algorithm efficiently identifies intervals common to all N sets.
• Performance was evaluated against existing algorithms in terms of speed and parallelization.

Main Results:

• The "slice-then-sweep" algorithm demonstrates superior efficiency for sequential interval set intersection.
• The algorithm exhibits significantly higher parallelization capacity, achieving a 19x speedup over existing methods.
• This method effectively handles the identification of common genomic regions across numerous datasets.

Conclusions:

• The "slice-then-sweep" algorithm provides a computationally efficient solution for multi-set genome interval intersection.
• This advancement is vital for extracting biological insights from large, complex genomic datasets.
• The algorithm's enhanced speed and parallelization capabilities support modern genome research demands.