A Parallel Algorithm for <i>N</i>-Way Interval Set Intersection

作     者：Layer, Ryan M. Quinlan, Aaron R. 

作者机构：Univ Utah Dept Human Genet Salt Lake City UT 84112 USA Univ Utah Human Genet & Biomed Informat Salt Lake City UT 84112 USA 

出 版 物：《PROCEEDINGS OF THE IEEE》 (电气与电子工程师学会会报)

年 卷 期：2017年第105卷第3期

页      面：542-551页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

基　　金：National Human Genome Research Institute (NHGRI) [NIH 1R01HG006693-01] 

主　　题：Bioinformatics computational biology genome analysis genomic interval intersection parallel algorithm 

摘      要：The comparison of sets of genome intervals (e.g., genes, repeats, ChIP-seq peaks) is essential to genome research, especially as modern sequencing technologies enable ever larger and more complex experiments. Relationships between genomic features are commonly identified by their intersection: that is, if feature sets contain overlapping intervals then it is inferred that they share a common biological function or origin. Using this technique, researchers identify genomic regions that are common among multiple (or unique to individuals) data sets. While there have been recent advances in algorithms for pairwise intersections between two sets of genomic intervals, few advances have been made to the intersection of many sets of genomic intervals. Identifying intersections among many interval sets is particularly important when attempting to distill biological insights from the massive, multidimensional data sets that are common to modern genome research. For such analyses, speed and efficiency are crucial, given the size and sheer number of data sets involved. To solve this problem, we present a novel ``slice-then-sweep algorithm that, given N interval sets, efficiently reveals the subset of intervals that are common to all N sets. We demonstrate that our algorithm is more efficient in the sequential case and has a vastly higher capacity for parallelization with a 19x speedup over the existing algorithm.