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

《面向长序列数据的单体分型算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中圈斜誊艘求犬誊硕士学位论又面向长序列数据的单体分型算法研究作者姓名：学科专业：导师姓名：完成时间：潘玮华计算机软件与理论徐云教授二。一四年四月二十日UniVerSityOfSCienCeandTeChnolOgyOfChinaAdiSSertatiOnfOrmaSter’SdegreeReSearChOnhapIOtypephaSingaIgOrithmf6rIOng■’■，’■，—■，SeqUenCeSAuthor’sName：WeihuaPanspecial时：ComputerSof研areand

2、Theo巧Supervisor：Pro￡YunXuFillishedtime：Apirl20册，2014中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：盎垄芊签字日期：型丝L—j2中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分

3、使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。与缀开口保密(——年)作者签名：盎雏举聊签名：始签字日期：!呈!竺z』。兰里签字日期：抄l毕。S．弓矿摘要摘要单体型序列是生物遗传分析中的一类重要信息。由于实验方法获取单体型序列具有价格过高、速度慢等缺点，

4、使用计算手段从易于获取的基因型序列得到单体型序列成为人们的首选，并发展为基因组学里一个基础的计算问题，称为单体分型问题。随着基因组学的发展，研究所需的单体型序列越来越长，有的甚至达到上百万个位点，这给单体分型问题提出了新的挑战。目前几乎所有的大规模单体分型算法在个人计算机上都只能处理长度小于十万的序列，因此迫切需要能处理长序列数据的单体分型算法。本文主要研究在内存有限的个人计算机上，分型长度十万位点以上的长序列数据集的快速单体分型算法，具体工作如下：1．面向长序列数据集的WinHAP2．0单体分型算法改

5、进及并行化Wi址队P2．0算法是近年来我们研究小组提出的一个长序列单体分型算法，本文对WinHAP2．0算法从两方面进行了改进，一是使用投票策略改进了段合并方法，二是进行了并行化。实验结果表明改进后的WinHAP2．0算法相比于原算法在段合并处的位点的交换错误率下降了20％．30％左右。相比于其他算法，改进后的算法计算精度与最好的算法相似，而计算时间和空间消耗低数倍到数十倍。该算法能够在个人计算机上使用12．8MB的内存分型500条长度一百万个位点的序列，而其他算法均无法完成这一任务。算法的并行化获得了

6、几乎线性的加速比。2．面向大规模长序列数据集的单体分型算法由于WinHAP2．O算法存在当序列条数很多时计算时间过长的缺陷，本项工作进行了进一步的改进，引入了序列聚类思想，提出了CbWnHAP算法。CbWinHAP算法首先将比较相似的序列聚成一类，再分别进行推导，由于聚类提高了相似序列的作用从而精度得到提高。而序列条数的减少又使得计算时间和空间得到降低。实验结果表明CbWjnHAP算法在保证计算精度相比于原WinHAP算法和MnHAP2．0算法不下降的情况下，计算时间和空间均降低了数倍。为了进一步提高计

7、算速度，我们也为CbWiI皿”算法进行了并行化。实验表明并行后的算法获得了接近于线性的加速比。关键词：大规模计算SNP位点单体型基因型单体分型长序列摘要I工垒!堕垒堕一一——————————————————————————一ABSTRACTThehaplo咖eisanimport觚tclaSsofi幽mationinbiologicalgeIletics·SmcetheeXperiInentalmethodshavetheshortcomillgsof11i曲。coStandslow，1tnaSbeco

8、methefirStchoiceofresercherstoobtainmehaplo帅es舶mche印genotypesbvcomputationalmethods．T11iscor叩utationalproblemcalledh印10typmghasbeena胁d锄entalproblemingenomics．Ⅵ恤medeVelopmentofgenomlcs，longeraIldlongerh印lotypesequencesarene