单体分型的快速算法及补缺问题研究.pdf

《单体分型的快速算法及补缺问题研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国科学技术大学硕士学位论又；单体分型的快速算法及补缺问题研究。⋯。：r’一⋯⋯r～⋯。，j～⋯一∥m。⋯^⋯～

2、

3、Ⅲ一一作者姓名：姚晓辉学科专业：计算机软件与理论!导师姓名：徐云副教授完成时间：二。一二年四月十八日

4、lIIIIIU]11IIII111[I111111IY2125459UniversityofScienceandTechnologyofChinaAdissertationformaster’Sdegree{Researchonfastalgorithmfor}；haplotypeinferenceandimputationA

5、uthor’SName：XiaohuiYaospeciality：ComputerSoftwareandTheorySupervisor：Assoc．Prof．YunXujFinishedtime：Apirl18眦，2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：蚴签字日期：Wlyt岁。冶中国科学技术大学学位论文授权使用声明作

6、为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。叼公开口保密(——年)作者签名：j塑L蜱导师签名：签字日期：阳mr、谚．缒签字日期：一塑{兰：茎!堕摘要单体型问题是分子生物学的一项重要研究课题，单体型信息在遗传性

7、疾病、药物反应检测等方便起着重要作用。由于人类和许多生物实体都是双倍体结构，实验手段只能得到基因型序列而非单体型，其中还存在大量的数据缺失，而重测序意味着更大的时间与成本消耗。同时，新一代测序技术甜extGenerationSequencingtechnology，NGS)得到的生物序列更为庞大，迫切需要既快速又高精度的计算方法对基因型进行分型和补缺。本文就单体分型和补缺两个问题的快速算法进行了深入研究，主要研究内容和贡献如下：1．基于均匀分块的单体分型算法组合优化方法是单体分型的一种重要方法，主要是基于合理的生物学假设来寻找精确解，其中最

8、大节约模型是一种简单而有效的分型模型。由于分型问题的难解性，当数据规模较大时，基于该模型的算法难以在可接受的时间内得到最优解，于是便产生了基于分块策略的快速方法研究。此前的分块方法主要是基于位点之间的连锁不平衡特性，将较高关联度的位点划分到同一块内，合理的分块尽管能够提高分型的准确度，但计算位点之间的关联度和块间合并会有较高的时间开销。为此，本文提出了一种带有重叠位点的均匀分块单体分型快速算法FHBPGL，该算法采用均匀分块且在块内使用最大节约模型进行分型，均匀分块减少了分块时间；利用块间的重叠位点进行贪心合并，提高了结果的准确度。真实数据

9、与模拟数据上的实验结果表明，FHBPGL算法运行时间显著减少，优于已有的算法，在结果准确度上与这些算法相当。2．基于连锁不平衡的自参考补缺算法实验测得的基因型或推导得到的单体型大多存在缺失位点，而重新测序代价过高，因此需要利用计算手段进行补缺。当前的补缺算法大多是利用已有数据库作为参考，对缺失序列进行补缺；然而，对于新物种以及缺乏足够参考数据的序列，这类算法并不适用。本文提出了一个基于自参考的补缺算法，将缺失数据序列进行分块，之后利用块内完整数据作为参考进行补缺。该补缺算法的设计思想有如下三点：第一是分块后块内序列长度变短，块内完整序列比例

10、大大增加，可以作为参考数据对剩余不完整序列进行补缺；第二，块内位点之间具有较强的关联度，因此序列模式数量相对有限，缺失序列与完整序列相匹配的概率大为增加；第三，分块策略同时也减少了算法的处理时间。通过真实数据与模拟数据上的实验，我们的算法与其他自参考补缺算法相比取得了更好的精度；与带参考算法相比的准确度相当，而平均运行时间仅为9s，远远小于其他算法(大于lh)。摘要关键词：生物信息学基因型单体型单体分型连锁不平衡分块补缺ⅡAbstractABSTRACTHaplotyperesearchisoneimportantresearchtopic

11、inthestudiesofmolecularbiology．Itplaysasignificantroleingeneticdiseaseanalysis，drugrespon