面向长序列数据的单体分型算法研究

作     者：潘玮华 

作者单位：中国科学技术大学 

学位级别：硕士

导师姓名：徐云

授予年度：2014年

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

主      题：大规模计算 SNP位点 单体型 基因型 单体分型 长序列 

摘      要：单体型序列是生物遗传分析中的一类重要信息。由于实验方法获取单体型序列具有价格过高、速度慢等缺点,使用计算手段从易于获取的基因型序列得到单体型序列成为人们的首选,并发展为基因组学里一个基础的计算问题,称为单体分型问题。随着基因组学的发展,研究所需的单体型序列越来越长,有的甚至达到上百万个位点,这给单体分型问题提出了新的挑战。目前几乎所有的大规模单体分型算法在个人计算机上都只能处理长度小于十万的序列,因此迫切需要能处理长序列数据的单体分型算法。本文主要研究在内存有限的个人计算机上,分型长度十万位点以上的长序列数据集的快速单体分型算法,具体工作如下： 1.面向长序列数据集的WinHAP2.0单体分型算法改进及并行化 WinHAP2.0算法是近年来我们研究小组提出的一个长序列单体分型算法,本文对WinHAP2.0算法从两方面进行了改进,一是使用投票策略改进了段合并方法,二是进行了并行化。实验结果表明改进后的WinHAP2.0算法相比于原算法在段合并处的位点的交换错误率下降了20%-30%左右。相比于其他算法,改进后的算法计算精度与最好的算法相似,而计算时间和空间消耗低数倍到数十倍。该算法能够在个人计算机上使用12.8MB的内存分型500条长度一百万个位点的序列,而其他算法均无法完成这一任务。算法的并行化获得了几乎线性的加速比。2.面向大规模长序列数据集的单体分型算法 由于WinHAP2.0算法存在当序列条数很多时计算时间过长的缺陷,本项工作进行了进一步的改进,引入了序列聚类思想,提出了CbWinHAP算法。CbWinHAP算法首先将比较相似的序列聚成一类,再分别进行推导,由于聚类提高了相似序列的作用从而精度得到提高。而序列条数的减少又使得计算时间和空间得到降低。实验结果表明CbWinHAP算法在保证计算精度相比于原WinHAP算法和WinHAP2.0算法不下降的情况下,计算时间和空间均降低了数倍。为了进一步提高计算速度,我们也为CbWinHAP算法进行了并行化。实验表明并行后的算法获得了接近于线性的加速比。