基于图的单倍体组装算法研究.pdf

大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明:本论文是在导师的指导下,独立进行研究工作所取得的成果, 撰写成博/硕士学位论文:基王图笪皇鱼签组苤篡选婴塞==。除论文中已经注明引用的内容外,对论文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体己经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名:色l硇丝: 学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定,即:大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版,允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据库》(中国科学技术信息研究所)等数据库中,并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于: 保密口/在——年解密后适用本授权书。不保密创(请在以上方框内打“√”) :&.12江.;钙L 日期:Ⅻl歹年}月r El 万方数据中文摘要摘要通过序列数据重建基因组,或者进行单倍体组装,面临着巨大的挑战。复杂’的真核生物,特别是人类基因的数量巨大,而且样本增长迅速,所以人们不得不采用高通量测序技术进行基因测序工作,并通过先进的计算机技术来提高其精确度和计算效率。基因测序能够获取染色体中包含单核苷酸多态位点的一段连续的 DNA片段,通过将读取的DNA序列映射到参考序列上,便可以知道该片段所属的染色体源点。当读取的片段包含两个或者更多的单核苷酸多态时,就能够提供有用的相位信息。单倍体组装的任务就是对于给定的一些染色体上读取的片段变异信息,计算每条染色体的单体型序列。本文研究了单倍体组装的图模型理论,提出一种基于冲突圈消融的算法(Resolving Conflict Graph Algorithm),该算法通过片段与SNP位点的关系生成一个有权无向图,即包含SNP冲突圈的图模型。该图中的节点是由单核苷酸多态(single nucleotide polymorphism,SNP)位点组成,边为支持两个SNP位点的片段, 边的权重为支持SNP位点的染色体片段值的总和。本文所研究的算法能够判断出图中因测序错误而形成的冲突圈,通过消融冲突圈,达到修正位点的目的,最终输出单倍体序列。通过与其他三种模型下的算法进行比较,我们的算法在降低片段错误率上具有一定优势。关键词:单倍体组装;单核苷酸多态;最大生成树;冲突圈;并查集万方数据英文摘要 ABSTRACT Genome-wide haplotype reconstruction fromsequence data orhaplotype assembly fac, rrnous challenges inmolecular biology and eukary- otis__,garI=is-ms likehumans,the genome is vast andthepopulation samples are grow- ing SOrapidly thatpeople have to use high—throughput sequencing technology forgene sequencing,the accuracy putational efficiency thuscould beensured with the help genome sequencing workflows produce contiguous DNA segments thatcontaining asingle nucleotide polymorphisms(SNP) spot ofan unknown chromosomal mapping thesequencing reads totheref- erence sequence,the origin can reads are valuable when they contain two ormore SNP haplotype assembly problem aims pute thehaplotype sequences for eachgiven chromoso