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

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]	柴旭清, 乔一航, 范黎林, . 一种基于随机森林分类器构建高性能应用程序性能分析模型的方法[J]. 计算机工程与科学, 2024, 46(07): 1218-1228.
[2]	宋鑫海, 韩京宇, 郎杭, 毛毅. 滑动窗口投票策略的QRS波群形态识别[J]. 计算机工程与科学, 2024, 46(02): 272-281.
[3]	钟卓辉, 陈黎飞, . 基于模型的非凸聚类算法[J]. 计算机工程与科学, 2024, 46(02): 292-302.
[4]	肖振国, 陈林书, 孙少杰, 梅本霞, 柳媛慧, 赵磊. 基于代数粒的聚类方法[J]. 计算机工程与科学, 2024, 46(01): 150-158.
[5]	吴超, 卫谦, 周俊伟, 李会民, 孙广中. 基于异构计算平台的背景噪声预处理并行算法[J]. 计算机工程与科学, 2023, 45(10): 1711-1719.
[6]	王鑫, 彭健. 基于HYB格式SpMV在新一代申威架构上的实现与优化[J]. 计算机工程与科学, 2023, 45(10): 1754-1762.
[7]	王若宾, 耿芳东, 张永梅, 宋威, 王伟锋, 徐琳. 基于改进自适应DBSCAN的混合式MOOC视频观看模式挖掘[J]. 计算机工程与科学, 2023, 45(09): 1670-1678.
[8]	刘屹成, 刘晓燕, 严馨. 并行平衡级联支持向量机[J]. 计算机工程与科学, 2023, 45(07): 1170-1177.
[9]	臧照虎, 李晨, 王耀华, 陈小文, 郭阳. 面向众核系统的层次化栅栏同步机制[J]. 计算机工程与科学, 2022, 44(11): 1901-1908.
[10]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[11]	李帅, 常锦才, 李吕牧之, 蔡昆杰, . 基于差分隐私保护的Stacking集成聚类算法研究[J]. 计算机工程与科学, 2022, 44(08): 1402-1408.
[12]	李兰, 刘杰, 张洁. 基于YOLOv4改进算法的复杂行人检测模型研究[J]. 计算机工程与科学, 2022, 44(08): 1449-1456.
[13]	陈奉贤. 基于NR-Transformer的集群作业运行时间预测[J]. 计算机工程与科学, 2022, 44(07): 1181-1190.
[14]	庞兴龙, 朱国胜, 杨少龙, 李修远. 一种基于聚类与噪声的网络流量分类方法[J]. 计算机工程与科学, 2022, 44(07): 1207-1215.
[15]	黄志强, 李军, 张世义. 基于轻量级神经网络的目标检测研究[J]. 计算机工程与科学, 2022, 44(07): 1265-1272.