基于枚举策略的二倍体单体型重建算法研究

发布时间：2017-09-16 03:25

  本文关键词：基于枚举策略的二倍体单体型重建算法研究

  更多相关文章： 单核苷酸多态性 单体型 最少错误更正 枚举 算法 重建

【摘要】：SNP(Single Nucleotide Polymorphism)分析在探究生物群体的遗传关系、分析疾病关联性等方面发挥着重要的作用,但与单个SNP相比,单体型数据包含了更加丰富的遗传信息,其在基因相关研究及医学治疗中发挥着重要的作用。然而,利用实验方法获取单体型数据的成本过于昂贵,因此利用计算方法获取单体型数据的单体型重建问题应运而生,并受到了广泛的关注。本文针对二倍体单体型重建问题展开研究,具体工作如下：针对最少错误更正模型对重建问题进行研究,提出一种基于支持度选取枚举值的重建算法EHDMS(Enumeration Haplotyping Diploid with More Support)。EHDMS算法依次重建单体型中的每个位点,对于给定位点,首先枚举该位点的两种取值情况,然后选择覆盖该位点的片段的更高支持度的取值,作为该位点的重建值。选取HapMap发布的CEPH样本中的单体型进行实验,采用CELSIM和MetaSim两种测序片段模拟生成器生成实验测试数据。通过设置不同片段覆盖率、错误率、单片段长度和单体型长度等参数,对算法EHDMS、 FAHR、Fast Hare和DGS的重建率和运行时间进行对比分析。实验结果表明,EHDMS算法在大部分情况下能获得较其它三种算法更高的重建率,并且具有较高的运行效率。针对最少错误更正模型,提出一种基于差异度选取枚举值的重建算法EHDLD (Enumeration Haplotyping Diploid with Least Difference)。当枚举出给定位点的取值时,分别计算两种取值情况下,单体型与覆盖该位点的片段的距离和,并选择对应于较小片段差异度的取值,即对应于距离和较小的取值。实验结果表明,EHDLD与EHDMS算法具有相近的问题求解性能,且其在大部分情况下能获得较FAHR、Fast Hare和DGS三种算法更高的重建率。综上所述,本文针对最少错误更正模型,提出选取枚举值的重建算法EHDMS和EHDLD。实验结果表明,这两个算法均能以较快的求解速度获得较高的重建精度,是重建二倍体单体型的有效方法。
【关键词】：单核苷酸多态性 单体型 最少错误更正 枚举 算法 重建
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：Q811.4
【目录】：

• 中文摘要3-4
• ABSTRACT4-8
• 第一章 绪论8-16
• 1.1 研究背景及意义8
• 1.2 遗传学基本概念8-12
• 1.2.1 染色体和染色体组型9
• 1.2.2 DNA分子概述和DNA测序9-11
• 1.2.3 基因的表达11-12
• 1.3 二倍体单体型重建问题12-15
• 1.3.1 问题描述12-14
• 1.3.2 国内外研究现状14-15
• 1.4 论文内容与安排15-16
• 第二章 EHDMS：一种基于支持度选取枚举值的重建算法16-26
• 2.1 MEC模型16-18
• 2.2 EHDMS算法设计及实现18-21
• 2.2.1 EHDMS算法原理18-19
• 2.2.2 算法实现与复杂性分析19-21
• 2.4 实验结果与分析21-25
• 2.4.1 实验数据21-22
• 2.4.2 性能评价22-25
• 2.5 本章小结25-26
• 第三章 EHDLD：一种基于差异度选取枚举值的重建算法26-33
• 3.1 基本概念和定义26
• 3.2 EHDLD算法设计及实现26-29
• 3.2.1 EHDLD算法原理26-27
• 3.2.2 算法实现与复杂性分析27-29
• 3.4 实验结果与分析29-32
• 3.5 本章小结32-33
• 第四章 结束语33-35
• 4.1 总结33
• 4.2 展望33-35
• 参考文献35-38
• 攻读硕士期间发表论文38-39
• 致谢39-40

【相似文献】

中国期刊全文数据库 前10条

1 王瑞省,吴凌云,张继红,章祥荪;单体型装配问题及其算法(英文)[J];高校应用数学学报A辑(中文版);2004年S1期

2 姜文锡;邱长春;程祖亨;周文郁;顾明亮;许群;方鸣武;牛文全;玛依拉;;载脂蛋白B基因单体型与中国维吾尔族自然长寿的关联研究[J];中国科学C辑:生命科学;2006年05期

3 杨英杰;;单体型装配问题的研究现状[J];铜仁学院学报;2011年02期

4 李珍萍,王勇,赵玉英,章祥荪;单体型推断问题与配对图(英文)[J];高校应用数学学报A辑(中文版);2004年S1期

5 甄建新;何柳媚;王大明;徐筠娉;邓志辉;;中国南方汉族人群KIR基因多态性的研究[J];中国输血杂志;2012年S1期

6 胡劲松,党娜娜,黄辰,宋土生;国际人类基因组单体型图计划[J];国外医学.遗传学分册;2005年03期

7 杨剑豪;刘[?;孙瑛;谢军华;郑皆炜;陆瑶;杜可明;;5186例上海汉族无关脐带血HLA基因多态性研究[J];中国输血杂志;2011年12期

8 杜胜军;惠汝太;;关联性研究中的单体型分析[J];中国分子心脏病学杂志;2006年04期

9 刘杰;张春燕;侯玲;李勇;张翅;;黑龙江地区汉族HLA-A、B、DRB1基因及单倍型的研究与应用[J];中国输血杂志;2009年03期

10 李彩霞;黎培兴;方积乾;;基于单体型重构的传递不平衡检验[J];中山大学学报(自然科学版);2007年04期

中国重要会议论文全文数据库 前10条

1 龚莎莎;张婷;郑静;吕建新;管敏鑫;;氨基糖甙类抗生素耳毒性相关的线粒体DNA继发突变[A];遗传学与社会可持续发展——2010中国青年遗传学家论坛论文摘要汇编[C];2010年

2 邓立彬;高扬;马素芳;张悦正;康健;曾长青;;应用单体型图进行疾病相关基因和基因组结构变异的定位研究[A];中国遗传学会“发育、遗传和疾病”研讨会论文汇编集[C];2007年

3 陈慧峰;林育纯;林丽娜;李文;罗洁;张树江;万建新;陈雯;林忠宁;;广东汉族人群PP2A-Aα亚基基因5'-侧翼区多态性的单体型分析[A];广东省环境诱变剂学会、广东省预防医学会卫生毒理专业委员会2010年学术会议资料汇编[C];2010年

4 徐新娟;梁晓慧;陈玉岚;珠勒皮亚;李素华;;VEGF基因单核苷酸多态性及其单体型与新疆维吾尔族长寿的关联研究[A];第十三次全国心血管病学术会议论文集[C];2011年

5 聂晶;胡扬;何子红;李燕春;衣龙燕;许春燕;王海燕;;VEGF基因单核苷酸多态性及单体型与杰出有氧运动能力的关联研究[A];第九届全国体育科学大会论文摘要汇编(2)[C];2011年

6 陈慧峰;林育纯;张树江;李晓杰;罗洁;林丽娜;李文;胡耀明;陈雯;林忠宁;;PPP2R1A基因启动子区高甲基化对其不同单体型转录功能活性影响[A];全国生化/工业与卫生毒理学学术会议论文集[C];2010年

7 林育纯;陈慧峰;方飞;林丽娜;陈雯;凌文华;Baitang Ning;Fred F Kadlubar;林忠宁;;磺酸基转移酶1A1基因启动子区SNPs位点单体型及其功能分析[A];遗传学进步与人口健康高峰论坛论文集[C];2007年

8 孙瞳;高扬;谭文;马素芳;张雪梅;王永岗;张清润;郭永丽;赵丹;曾长青;林东昕;;染色体11q22基质金属蛋白酶基因簇单体型与肺癌发生发展风险(英文)[A];第四届中国肿瘤学术大会暨第五届海峡两岸肿瘤学术会议教育集[C];2006年

9 张继红;吴凌云;王勇;李珍萍;章祥荪;;由基因型SNP数据推断相应单体型的Markov链统计方法(英文)[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

10 侯玲;刘杰;李鑫;丁镌;孙建华;赵国庆;;黑龙江地区蒙古族HLA-A、B、DRB1等位基因及单体型的研究[A];中国输血协会第五届输血大会论文专集（摘要篇）[C];2010年

中国重要报纸全文数据库 前5条

1 本报记者 李雪墨 李斌;单体型图破解人类基因组奥秘[N];医药经济报;2003年

2 ;科学家将合力绘制人类基因组遗传整合图中国卷[N];中国高新技术产业导报;2003年

3 张荔子 张清润;注释“天书”[N];健康报;2006年

4 张荔子;血样有助于破解遗传之谜[N];大众卫生报;2003年

5 本报记者　贾婧;寻找致病基因和群体遗传学研究的“金矿”[N];科技日报;2006年

中国博士学位论文全文数据库 前8条

1 汪颖;单体型和基因型问题的优化模型和算法[D];大连理工大学;2007年

2 王涛;中国人苯丙氨酸羟化酶基因突变的研究[D];中国协和医科大学;1994年

3 张永彪;中国6个民族群体HLA区域内TNF基因簇的核苷酸变异和单体型多态性[D];中国协和医科大学;2008年

4 武金才;肿瘤转移抑制基因HTPAP单体型与肝癌转移潜能的关系[D];复旦大学;2008年

5 梁晓慧;TERT、VEGF基因单核苷酸多态性及其单体型与新疆维吾尔族长寿的关联研究[D];新疆医科大学;2010年

6 余志杰;Tim-3基因多态性与湖北汉族人群AML的关联分析研究[D];华中科技大学;2014年

7 张强锋;单体分型和单体型频率估计[D];中国科学技术大学;2006年

8 谢民主;单体型组装问题参数化建模及算法研究[D];中南大学;2008年

中国硕士学位论文全文数据库 前10条

1 汤栩宁;基于单体型的致病基因区域发现算法研究[D];吉林大学;2008年

2 王彦坤;高通量测序检测榕小蜂COI基因异质性及其对分子鉴定的影响[D];河北大学;2015年

3 解惠坚;PPARα/δ/γ单核苷酸多态性及交互作用与脂蛋白(a)的关联研究[D];苏州大学;2015年

4 海波;过氧化物酶体增殖物激活受体α/γ单核苷酸多态性与TG/HDL-C比值、LDL-C/HDL-C比值的相关性研究[D];苏州大学;2015年

5 赵明晓;基于分割策略的生物单体型数据推导算法研究[D];大连海事大学;2015年

6 张路宁;酪氨酸蛋白激酶-2基因多态性与汉族人群肥胖易感性的关系[D];郑州大学;2016年

7 杨镨捚;多倍体单体型重建算法的研究[D];湖南师范大学;2016年

8 牛红;利用单体型进行中国西门塔尔牛全基因组选择的初步研究[D];中国农业科学院;2016年

9 陈茜茜;基于枚举策略的二倍体单体型重建算法研究[D];广西师范大学;2016年

10 王兆灿;K单体型重建算法的研究[D];广西师范大学;2014年

，

本文编号：860606