多倍体单体型重建算法的研究

《多倍体单体型重建算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文多倍体单体型重建算法的研究学科专业计算机软件与理论学位类型√□科学学位□专业学位研究生姓名杨镨鋆导师姓名、职称谢民主教授论文编号S1601809湖南师范大学学位评定委员会办公室二零一六年五月分类号TP301.6密级公开学校代码10542学号201302110912多倍体单体型重建算法的研究Researchonalgorithmsofpolyploidhaplotypereconstruction研究生姓名杨镨鋆指导教师姓名、职称谢民主教授学科专业计算机软件与理论研究方向生物信息学湖南师范大学学位评定委

2、员会办公室二零一六年五月摘要单体型不但应用于生物体表型特征的研究，更是广泛应用于生物群体或个体在疾病易感性和对环境因子的反应差异的研究，有着重大的实用价值和现实意义。由于直接通过生物学实验直接测定个体单体型所用的代价和成本十分巨大，目前主要是在测序获得的个体DNA片段数据的基础上利用计算机算法重建整个个体的单体型，这就是个体单体型重建问题。这个问题一直以二倍体生物为研究重心，随着研究进一步发展，对多倍体生物的研究慢慢变为新的热点。多倍体单体型重建问题，其数据相对于二倍体更复杂，需要有针对性的新方法来解决这个问题。

3、本文首先介绍了多倍体单体型重建问题的相关背景以及研究意义，并对目前研究现状和研究进展进行介绍。然后，本文针对多倍体单体型重建问题的遗传算法进行研究。本文利用二进制数的特征，采用新的编码把遗传算法的适用范围扩充到有k条染色体的多倍体单体型重建问题。本文对已有多倍体单体型重建遗传算法进行研究时，发现了其中所存在的一些局限和特点：编码重复、由染色体分类片段时出现片段聚集、由片段生成新染色体时出现的编码越界以及染色体编码组分段交错排列出现局部收敛。针对于以上这些局限和特点，本文加以分析和利用，对片段聚集问题利用随机思想使

4、用新的分配策略，在编码生成的过程中改进编码；而对编码越界问题，本文增加了针对越界的编码序列的变异机率或直接改进编码；对局部收敛的问I题，本文提出了新的矫正算子，对局部收敛的解进行矫正。大量模拟测试表明，改进后的算法与已有的单体型重建遗传算法相比可以大大提高单体型重建精度。关键词：多倍体，单体型组装，遗传算法，算法设计IIAbstractHaplotypesarenotonlyappliedtothestudyofphenotypiccharacteristics,butalsowidelyusedintheres

5、earchofdifferencesinthesusceptibilitiestodiseasesandtheresponsestoenvironmentalfactorsofindividualsofapopulation.Therefore,therearegreatpracticalvaluesandrealisticsignificancesonit.Duetothefactitisverycostlytodetermineindividualhaplotypesjustbythebiologyexper

6、iments,itismainlyusingcomputeralgorithmstorebuildthewholeindividualhaplotypesfromtheDNAsequencingfragmentsinnowdays,whichistheindividualhaplotypereconstructionproblem.Moststudieshavefocusedonthehaplotypereconstructionofdiploidorganisms.Recently,thestudyofthep

7、olyploidhaplotypereconstructionproblemisdrawingmoreandmoreattentions.Thepolyploidhaplotypereconstructionproblemismorecomplexthanthediploidoneandneedsnewmethodstosolveit.Thispaperfirstintroducesthebackgroundandthesignificanceaboutthepolyploidhaplotypereconstru

8、ctionproblem,andalso,introducesthecurrentresearchstatusandprogressonit.Then,basedontheexistinggeneticalgorithmstothepolyploidhaplotypereconstructionproblem,thispaperimprovestheoldprocesse