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

J4 ›› 2013, Vol. 35 ›› Issue (11): 27-33.

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

潘玮华，陈波，徐云

(1.中国科学技术大学计算机科学与技术学院，安徽合肥 230027；2.安徽省高性能计算重点实验室，安徽合肥 230027)

收稿日期:2013-08-12 修回日期:2013-10-11 出版日期:2013-11-25 发布日期:2013-11-25
基金资助:
国家自然科学基金面上项目(60970085)；国家自然科学基金资助项目(61033009)

Clusteringbased largescale haplotype phasing algorithm

PAN Weihua,CHEN Bo,XU Yun

(1.School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027；
2.Key Laboratory of High Performance Computing,Hefei 230027,China)

Received:2013-08-12 Revised:2013-10-11 Online:2013-11-25 Published:2013-11-25

摘要/Abstract

摘要：

大规模单体分型问题是生物遗传分析领域一个重要的基础性问题。针对现有算法求解大规模单体分型问题时存在的缺陷，在原有WinHAP算法的基础上引入聚类思想，提出一种基于聚类的WinHAP算法。该算法在保证原算法精度不下降的前提下，大大提高了算法的计算速度，降低了空间消耗，并具有空间需求与序列条数无关这一优良特性，因此特别适合处理超大规模的数据集。在SIMD共享存储模型下对算法进行了并行化，并设计了基于贪心的线程任务分配策略，获得了接近线性的加速比。

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

Abstract:

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 WinHAP 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 parallelized 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.

Key words: haplotype phasing;clustering;largescale computing;parallel computing;bioinformatics

潘玮华，陈波，徐云. 一种基于聚类的大规模单体分型算法[J]. J4, 2013, 35(11): 27-33.

PAN Weihua,CHEN Bo,XU Yun. Clusteringbased largescale haplotype phasing algorithm [J]. J4, 2013, 35(11): 27-33.

[1]	廉凯成, 杨晨, 朱佳伟, 柴志雷, . 基于Floyd-Steinberg误差扩散的数字半调高效计算[J]. 计算机工程与科学, 2025, 47(05): 875-884.
[2]	李世杰, 刘阳, 唐晋韬, 郄航. 基于孤立集分区的并行Louvain社区发掘算法[J]. 计算机工程与科学, 2025, 47(04): 621-633.
[3]	谢斌, 李燕伟, 杨舒敏, 徐燕, 王冠超. 结合图像分解和自稀疏模糊聚类的情感颜色迁移[J]. 计算机工程与科学, 2025, 47(03): 513-523.
[4]	张元胤, 肖敏广, 刘志勇, 翁灵玲, 陈志广, 卢宇彤. 基于国产异构众核处理器的等值线与等值面提取算法优化[J]. 计算机工程与科学, 2025, 47(02): 200-209.
[5]	卢建云, 邵俊明. 基于多层次密度中心图的聚类算法[J]. 计算机工程与科学, 2025, 47(02): 327-335.
[6]	蔡发鹏, 冯骥, 杨德刚, 陈仲尚. 基于自然邻域图划分的层次聚类算法[J]. 计算机工程与科学, 2025, 47(02): 370-380.
[7]	刘合兵, 孔玉杰, 席磊, 尚俊平. 融合注意力机制的解耦对比聚类[J]. 计算机工程与科学, 2024, 46(12): 2261-2270.
[8]	李猛, 刘姿邑, 宋宇航. 基于双重自表达与最大熵原理的深度子空间聚类算法[J]. 计算机工程与科学, 2024, 46(09): 1685-1692.
[9]	李沛桢, 张洋, 陈文波. 基于DPCT的序列比对软件迁移与性能评估[J]. 计算机工程与科学, 2024, 46(08): 1372-1380.
[10]	柴旭清, 乔一航, 范黎林, . 一种基于随机森林分类器构建高性能应用程序性能分析模型的方法[J]. 计算机工程与科学, 2024, 46(07): 1218-1228.
[11]	宋鑫海, 韩京宇, 郎杭, 毛毅. 滑动窗口投票策略的QRS波群形态识别[J]. 计算机工程与科学, 2024, 46(02): 272-281.
[12]	钟卓辉, 陈黎飞, . 基于模型的非凸聚类算法[J]. 计算机工程与科学, 2024, 46(02): 292-302.
[13]	肖振国, 陈林书, 孙少杰, 梅本霞, 柳媛慧, 赵磊. 基于代数粒的聚类方法[J]. 计算机工程与科学, 2024, 46(01): 150-158.
[14]	吴超, 卫谦, 周俊伟, 李会民, 孙广中. 基于异构计算平台的背景噪声预处理并行算法[J]. 计算机工程与科学, 2023, 45(10): 1711-1719.
[15]	王鑫, 彭健. 基于HYB格式SpMV在新一代申威架构上的实现与优化[J]. 计算机工程与科学, 2023, 45(10): 1754-1762.