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

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

单位：中国科学技术大学计算机科学与技术学院 安徽合肥230027 安徽省高性能计算重点实验室 安徽合肥230027