导读:本文包含了单体型组装论文开题报告文献综述及选题提纲参考文献，主要关键词:MEC模型,多倍体单体型组装,置信度,最高可翻转次数
单体型组装论文文献综述
喻昕[1]（2019）在《多倍体单体型组装算法研究》一文中研究指出人类已知的疾病都与基因有着直接或者间接的联系,研究不同个体间基因序列的差异对于了解人类的遗传,以及预防疾病等方面都有着重要的作用。SNP是单核苷酸多态性,主要是指在基因组水平上由单个核苷酸的变异所引起的DNA序列多态性。一个区域中倾向于以整体遗传给后代的SNP序列被称作是单体型。但受到测序技术的限制,直接通过测序得到完整的单体型序列十分困难,因此如何将测序得到的片段组装成单体型起来成为了一个新的难点。现有的单体型组装问题根据其优化原则大致有MSR,MFR,MEC等几类,这些问题绝大多数是NP-难的,多倍体单体型的组装由于其复杂的分型情况,缺乏有效的实用算法。由于新一代测序技术成本的降低和片段长度的增加,从测序片段重建多倍体基因组的多个单体型变得可行。本文提出了两个在新一代测序技术下的多倍体单体型组装算法Qhap和QChap算法。这两个算法都是基于MEC算法的改进。Qhap算法通过限制SNP矩阵中每一列的最大翻转数,大大降低了时间复杂度;同时引入了置信度分析,使得得到的单体型更加符合真实情况。对于从k-倍体基因组测序得到的片段,该算法试图将片段划分成k组,使得翻转位点的置信度分数总和最低。QChap算法是在Qhap算法的基础上,每列最大翻转个数由固定值改进为随着测序错误率和每列覆盖度变化情况而动态调整的值。在模拟和真实数据上的大量实验测试结果表明,Qhap和QChap算法可以有效地解决多倍体单体型组装问题,并且比近期的多倍体单倍型组装算法更快,更准确。(本文来源于《湖南师范大学》期刊2019-03-01）
黄雾[2]（2018）在《杂合二倍体马铃薯基因组单体型组装与分析》一文中研究指出马铃薯是世界上最重要的根茎类粮食作物。马铃薯的野生种质资源多为二倍体和四倍体,在遗传育种方面应用广泛。目前,马铃薯双单倍体参考基因组DM已经发表,且在功能基因克隆等研究方面发挥了很大作用。但是由于多马铃薯基因组杂合度较高,单体型之间的差异较大(>1%),双单倍体参考基因组能提供的信息有限,不能满足二倍体马铃薯育种和基因组功能研究的需求。由于二倍体马铃薯基因组高度杂合,组装难度较大,国际马铃薯团队曾尝试对二倍体马铃薯RH进行测序组装,但是没有成功。本课题利用10X genomics(10XG)建库和高通量测序手段,结合自己开发的基因组组装和单体型分型流程,成功对RH进行了基因组组装、分型和注释。并利用自交后代群体从头构建了遗传图谱,将组装所得的序列进行了染色体锚定。在区分了单体型基础上,对单体型多态性进行了分析,解析了杂合基因组等位基因之间差异的特征。该方法可以作为杂合物种基因组组装的借鉴。本课题主要结果有:(1)结合10XG长片段文库构建和高通量测序,从头组装了杂合二倍体马铃薯RH的基因组。该组装长度一共1.7 Gb,scaffold N50为308 Kb,完整性达到93.3%。通过对基因组进行基因注释,识别出71561个蛋白编码基因。(2)开发了一套从头构建遗传图谱的方法。将约90%的组装序列锚定到24个连锁群上,对应RH的12对染色体。(3)通过单体型共线性分析,共找出844个共线性区域,覆盖55.5%的基因组区域,包含36,297个基因,占基因组总基因数比例为50.67%。分析比较共线性区域单体型之间的多态性,共找出5.23 M的SNPs以及552 K个InDels,单体型差异大于1%。(4)结合RH自交群体的等位基因分离情况,对基因组上严重偏分离区域进行分析,初步解释12号染色体上一个严重偏分离区域内,单体型上的基因结构和表达差异。(本文来源于《中国农业科学院》期刊2018-04-01）
张倩[3]（2017）在《叁倍体个体单体型组装问题的研究》一文中研究指出SNP的研究对探索叁倍体物种的遗传特性和表型差异等方面发挥着重要的作用,而单体型数据比单个SNP位点携带更多的遗传信息,其在生物个体的表型差异、基因表达和疾病预测等方面发挥的作用更大。由于目前的实验技术水平有限,直接通过生物学手段来测定一个个体的单体型的时间和金钱成本过高,因此通过计算方法来获取个体单体型成为生物学关注的热点问题。本文主要研究叁倍体个体单体型组装问题,具体工作如下:针对带基因型信息的最少错误更正模型对组装问题进行研究,提出一种基于支持度的重建算法 HTMS(Haplotyping a Triploid individual with Most Support)。HTMS 算法依次重建叁条单体型上的每一个SNP位点取值,对于给定位点,首先根据其基因型取值枚举该位点的叁种单体型取值情况,然后选择获片段支持度最高的取值作为该位点的重建值。实验测试数据由CELSIM和MetaSim两种测序片段模拟生成器生成,在片段覆盖率、错误率、单片段长度、单体型长度和单体型海明距离等参数的不同设置下,比较分析算法HTMS、T-HC、GTIHR、W-GA和Q-PSO的重建率和运行时间。实验结果显示,算法HTMS在不同的参数设置下,都能用最快的运行速度获得最高的重建率。针对带基因型信息的最少错误更正模型,提出一种基于差异度的重建算法HTLD(Haplotyping a Triploid individual with Least Difference)。HTLD 算法采取一种新的计算方法度量片段和单体型间的距离。当由基因型枚举出待重建位点的叁种取值时,分别计算叁种取值下,单体型与覆盖该位点的片段之间的距离和,选择对应最小片段差异度的取值,即对应距离和最小的取值。实验结果表明,在不同的参数取值下,算法HTLD和HTMS具有相近的问题求解性能,且都比算法T-HC、GTIHR、W-GA和Q-PSO的重建精度更高,运行时间更短。综上所述,本文基于带基因型信息的最少错误更正模型,提出两种重建算法HTMS和HTLD。大量的实验结果显示,HTMS和HTLD算法都能以更快的求解速度获得精度更高的单体型,是解决叁倍体个体单体型组装问题的实用方法,具有很强的应用价值。(本文来源于《广西师范大学》期刊2017-04-01）
杨洋[4]（2014）在《单体型组装问题枚举算法研究》一文中研究指出分析和识别单体型对复杂疾病致病基因的精确定位有重要作用。单体型组装问题是利用个体DNA测序片段数据推出该个体一对单体型的计算问题。根据不同的优化准则,单体型组装问题有最少SNP(Single Nucleotide Polymorphisms)位点删除模型(Minimum SNP Removal, MSR),最少片段删除模型(Minimum Fragment Removal,MFR)和最少错误更正模型(Minimum Error Correction, MEC)等计算模型,这些模型旨在得到问题的一个最优解,即两条单体型。对生物学家来说,一个解对于复杂的生物问题往往是不够的。基于上述目的,本文为MSR、MFR和MEC设计了能给出多个最优解的模型和相应的参数化枚举算法。MSR模型是试图删除最少SNP位点来确定个体的单体型的计算问题。在此基础上,我们定义MSR的k枚举模型(k-Minimum SNP Removal Enumeration, K_MSR):对于给定的一个SNP矩阵M,一个小正整数k,为MSR模型枚举最多k个解,即得到一个元素个数为k的最优解的集合。我们设计求解K MSR的算法的时间复杂度为O(nk1k2+nkk1+mlogm+mk1),空间复杂度为O(nkk1),其中m为片段数,n为SNP位点数,k1为单个片段覆盖的最大SNP位点数,k2为覆盖任意SNP位点的最大片段数。MFR模型是试图删除最少片段来确定个体单体型的计算问题,在MFR模型的定义的基础上我们提出K_MFR (k-Minimum FragmentRemoval Enumeration)模型：给定一个SNP矩阵M和一个小正整数k,为MFR模型枚举最多k个最优解。我们设计求解该模型算法的时间复杂度为O(mkk22+mkk1k2+mlogm+nk2),空间复杂度为O(mk1+mkk22)。在MEC模型定义的基础上,我们提出MEC的k枚举模型(k-Minimum Error Correction Enumeration,K_MEC),并设计了时间复杂度为O(nk22k2+mlogm+mk1)、空间复杂度为O(mkk12k2+nk2)的算法。大量实验表明上述几种算法可有效提供多个解,可提供较高重建率的单体型,得到的多个解能为为生物学家提供更多选择,对于复杂问题的研究有很大实际意义。(本文来源于《湖南师范大学》期刊2014-05-01）
谢民主,罗锋,唐烽[5]（2014）在《单体型组装最大片段割参数化精确算法》一文中研究指出单体型能提高复杂疾病全基因组关联分析的能力,可直接用生物实验测定单体型费用太高.随着DNA测序技术的发展,计算机算法被广泛用于从个体基因组测序片段上构建单体型,即单体型组装.最大片段割是最近提出的一个单体型组装优化模型,是NP-难的,目前没有实用精确算法.最近参数计算理论利用实际计算中的小参数特征为NP-难问题求解提供了一条新思路.本文根据实际测序数据覆盖了两个或多个杂合单核苷酸多态性位点(SNP)的片段的测序深度较小的特点,对跨一个具体SNP位点的所有片段划分进行枚举,提出一个参数化的动态规划算法求解其精确解.大量测试结果表明该算法比已有的启发式算法有更高的单体型重建精度.(本文来源于《小型微型计算机系统》期刊2014年02期）
谢民主,刘新求[6]（2010）在《枚举单体型组装问题多个最优解的遗传算法设计》一文中研究指出单体型组装问题就是根据个体基因组测序获得的DNA序列数据重构出该个体的一对单体型。目前单体型组装问题的各种优化计算模型已有相关的启发式算法和参数化精确算法,但是这些算法只能得出一个最优解,即一对单体型。可是生物问题的最优解往往不是唯一的,或者真实解可能只是接近最优的。该文设计了一个新的能枚举出最优的多个解的遗传算法。实验结果表明该算法具有较高的单体型重建精度,并为生物学家根据领域知识在算法获得的多个解的基础进一步选择提供了可能。(本文来源于《计算机工程与应用》期刊2010年11期）
姚雄武,郑金华,李晶,文诗华[7]（2010）在《遗传算法和单体型组装加权最小字符翻转问题》一文中研究指出单体型组装加权最小字符翻转(WMLF)问题指定个体联配的加权DNA片断数据,翻转权值和最小的SNP位点以推测出该个体的一对单体型。该问题是NP-难的,至今尚无实用的搜索寻优算法。根据DNA测序片段数据的特点提出了一种遗传算法。对于实际的生物实验数据,即使数据很大,该算法也可以在较短的时间得到WMLF问题的满意解,具有良好的可扩展性和较高的实用价值。(本文来源于《计算机工程与应用》期刊2010年08期）
陈姝伊[8]（2010）在《个体单体型组装问题MEC模型的算法研究与比较》一文中研究指出分析和识别单体型对复杂疾病致病基因的精确定位有重要作用,但是在当前的实验技术下直接测定个体单体型所需的时间和金钱上的花费过于昂贵,因此利用计算机技术来确定个体的单体型有其重要的现实意义。单体型组装问题是利用个体DNA测序片段数据推出该个体一对单体型的计算问题。单体型组装问题的大部分计算模型都被证明是NP难的,缺乏实用的算法。在单体型组装问题的众多模型中,MEC (Minimum Error Correction)模型是最符合实际且信息丢失最少的模型。基于MEC模型,本文在详细研究了MCMC算法如何使用一条由单体型组成的马尔科夫链来解决该组装问题的基础上,借鉴其建立位点结构图的新颖思想,结合遗传算法,提出GAMEC算法,并针对问题设计适应度函数和启发式算子对由单体型构成的种群进行选择、交叉和变异。研制了计算机程序,使用模拟数据和19号染色体上的真实数据对两种算法分别进行实验。实验结果表明,两种算法均能够准确进行单体型估计,并且组装出具有较高精确度和重构率的单体型,GAMEC算法计算速度优于MCMC算法,而MCMC算法具有更好的适应性。这两种算法描述的是单体型组装的一般框架,均能够被应用于各种测序技术产生的序列数据。(本文来源于《西安电子科技大学》期刊2010-01-01）
周伟,王建新,谢民主,陈建二[9]（2008）在《单体型组装问题计算模型的比较与分析》一文中研究指出单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。单体型组装问题指如何利用个体的基因测序片断数据,根据不同的优化准则确定该个体单体型的计算问题。对MSR,MFR,MEC,WMLF,MEC/GI等单体型组装模型做了详细的分析比较,得出了如下结论:在没有引入测序误差情况下,上述模型的重构精度基本一致。随着测序误差的增加,MEC/GI模型的容错性最好,重构精度最高;MSR模型受测序误差的影响最大,只适用于测序误差极小的情形。(本文来源于《计算机科学》期刊2008年11期）
谢民主[10]（2008）在《单体型组装问题参数化建模及算法研究》一文中研究指出分析和识别单体型对复杂疾病致病基因的精确定位有重要作用。单体型组装问题是利用个体DNA测序片段数据推出该个体一对单体型的计算问题。根据不同的优化准则,单体型组装问题有MSR、MFR、MEC和MEC/GI等计算模型。单体型组装问题的绝大部分计算模型都被证明是NP-难的,缺乏实用的精确算法。在实际DNA片段数据中,一个片段所覆盖的最大SNP位点数k_1通常小于10,覆盖一个SNP位点的最大片段数k_2通常不大于19。基于以上事实,本文对MSR和MFR进行参数化建模。在此基础上,为求解无空隙的MSR和MFR,本文设计了时间复杂度分别为O(nk_1k_2+mlogm+mk_1)和O(mk_2~2+mk_1k_2+mlogm+nk_2)的精确算法P_MSR和P_MFR,其中m为片段数,n为单体型的SNP位点数;为求解有空隙的MSR和MFR,本文设计了时间复杂度分别为O(2~knk_1k_2+mlogm+nk_2+mk_1)和O(2~kmk_1k_2+2~(3k)mk_2~2+mlogm+nk_2+mk_1)的精确算法PG_MSR和PG_MFR,其中k为片段中最大洞数。大量实验结果表明,在Bafna等的对应算法基础上,上述参数化算法的效率显着提高,适用于全基因组规模上的单体型组装。针对长的mate-pair中洞的个数较多的情况,本文提出了求解MSR和MFR时间复杂度分别为O(nk_1k_22~(2h)+k_12~h+nk_2+mk_1)和O(nk_23~(k_2)+mlogm+nk_2+mk_1)的参数化精确算法PM_MSR和PM_MFR,其中h为覆盖同一SNP位点且在该位点取空值的片段的最大数。在实际的DNA测序数据中,k_2通常不大于19,而h不大于17,理论分析和实验结果均表明PM_MSR和PM_MFR算法所需的时间与片段中洞的个数的最大值k没有直接的关系,在片段数据中存在长mate-pair的情况下仍然能有效计算。根据实际DNA测序片段数据的特点,本文对MEC和MEC/GI进行参数化建模,进而设计出求解这两个模型时间复杂度均为O(nk_22~(k_2)+mlogm+mk_1)的精确算法P_MEC和P_MEC/GI。实验结果表明,在片段数达到100,Wang等提出的分支限界算法已无法运行的情况下,P_MEC、P_MEC/GI和Wang等提出的遗传算法一样,仍然能快速运行。而作为精确算法,P_MEC和P_MEC/GI在单体型重构精度上比Wang等对应的遗传算法有明显优势。为了提高单体型的重构精度,本文提出了一个基于加权片段数据和有误差基因型的单体型组装问题计算模型WMEC/GS,然后证明了即使片段中无空隙其也是NP-难的。进而根据片段数据的特点,提出了求解该模型的时间复杂度为O(nk_22~(k_2)+mlogm+mk_1)的参数化算法P_WMEC/GS。对MEC/GI、WMLF和WMEC/GS叁模型的大量实验表明WMEC/GS模型具有最高的单体型重构精度。(本文来源于《中南大学》期刊2008-05-01）
单体型组装论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
马铃薯是世界上最重要的根茎类粮食作物。马铃薯的野生种质资源多为二倍体和四倍体,在遗传育种方面应用广泛。目前,马铃薯双单倍体参考基因组DM已经发表,且在功能基因克隆等研究方面发挥了很大作用。但是由于多马铃薯基因组杂合度较高,单体型之间的差异较大(>1%),双单倍体参考基因组能提供的信息有限,不能满足二倍体马铃薯育种和基因组功能研究的需求。由于二倍体马铃薯基因组高度杂合,组装难度较大,国际马铃薯团队曾尝试对二倍体马铃薯RH进行测序组装,但是没有成功。本课题利用10X genomics(10XG)建库和高通量测序手段,结合自己开发的基因组组装和单体型分型流程,成功对RH进行了基因组组装、分型和注释。并利用自交后代群体从头构建了遗传图谱,将组装所得的序列进行了染色体锚定。在区分了单体型基础上,对单体型多态性进行了分析,解析了杂合基因组等位基因之间差异的特征。该方法可以作为杂合物种基因组组装的借鉴。本课题主要结果有:(1)结合10XG长片段文库构建和高通量测序,从头组装了杂合二倍体马铃薯RH的基因组。该组装长度一共1.7 Gb,scaffold N50为308 Kb,完整性达到93.3%。通过对基因组进行基因注释,识别出71561个蛋白编码基因。(2)开发了一套从头构建遗传图谱的方法。将约90%的组装序列锚定到24个连锁群上,对应RH的12对染色体。(3)通过单体型共线性分析,共找出844个共线性区域,覆盖55.5%的基因组区域,包含36,297个基因,占基因组总基因数比例为50.67%。分析比较共线性区域单体型之间的多态性,共找出5.23 M的SNPs以及552 K个InDels,单体型差异大于1%。(4)结合RH自交群体的等位基因分离情况,对基因组上严重偏分离区域进行分析,初步解释12号染色体上一个严重偏分离区域内,单体型上的基因结构和表达差异。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
单体型组装论文参考文献
[1].喻昕.多倍体单体型组装算法研究[D].湖南师范大学.2019
[2].黄雾.杂合二倍体马铃薯基因组单体型组装与分析[D].中国农业科学院.2018
[3].张倩.叁倍体个体单体型组装问题的研究[D].广西师范大学.2017
[4].杨洋.单体型组装问题枚举算法研究[D].湖南师范大学.2014
[5].谢民主,罗锋,唐烽.单体型组装最大片段割参数化精确算法[J].小型微型计算机系统.2014
[6].谢民主,刘新求.枚举单体型组装问题多个最优解的遗传算法设计[J].计算机工程与应用.2010
[7].姚雄武,郑金华,李晶,文诗华.遗传算法和单体型组装加权最小字符翻转问题[J].计算机工程与应用.2010
[8].陈姝伊.个体单体型组装问题MEC模型的算法研究与比较[D].西安电子科技大学.2010
[9].周伟,王建新,谢民主,陈建二.单体型组装问题计算模型的比较与分析[J].计算机科学.2008
[10].谢民主.单体型组装问题参数化建模及算法研究[D].中南大学.2008