一种基于聚类的大规模单体分型算法  

Clustering-based large-scale haplotype phasing algorithm

作　　者：潘玮华[1,2] 陈波[1,2] 徐云[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,安徽合肥230027 [2]安徽省高性能计算重点实验室,安徽合肥230027

出　　处：《计算机工程与科学》2013年第11期27-33,共7页Computer Engineering & Science

基　　金：国家自然科学基金面上项目(60970085);国家自然科学基金资助项目(61033009)

摘　　要：大规模单体分型问题是生物遗传分析领域一个重要的基础性问题。针对现有算法求解大规模单体分型问题时存在的缺陷,在原有WinHAP算法的基础上引入聚类思想,提出一种基于聚类的WinHAP算法。该算法在保证原算法精度不下降的前提下,大大提高了算法的计算速度,降低了空间消耗,并具有空间需求与序列条数无关这一优良特性,因此特别适合处理超大规模的数据集。在SIMD共享存储模型下对算法进行了并行化,并设计了基于贪心的线程任务分配策略,获得了接近线性的加速比。Large-scale haplotype phasing is an important fundamental problem in genetic analysis. To overcome the weakness of existing algorithms, we introduce the concept of clustering into original Win- HAP algorithm and propose the Clutering based WinHAP algorithm. This algorithm improves original WinHAP in computing speed and memory without decreasing the precision, and its memory has nothing to do with the number of sequences. Thus, it is suited to very large datasets. The algorithm is parallel- ized under SIMD shared memory model and greedy task designing strategy is devised. The experiment reveals a near-linear speedup with respect to the sequential algorithm.

关 键 词：单体分型 聚类 大规模计算 并行计算 生物信息学 

分 类 号：TP38[自动化与计算机技术—计算机系统结构] Q344[自动化与计算机技术—计算机科学与技术]