单体型装配问题的启发式算法研究

《单体型装配问题的启发式算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、单体型装配问题的启发式算法研究摘要：单体型装配问题是生物信息学的一个研究重点，针对的是染色体上的大量SNP数据，通过适当的方法，将其装配成一对单体型。文章介绍了求解单体型装配问题的三种主要的启发式算法，分别是基于遗传算法的启发式算法，基于粒子群算法的启发式算法和基于前馈神经网络算法的启发式算法。中国8/vie　　关键词：单体型；单体型装配；SNP　　中图分类号：R394文献标识码：A：1007-9416（2017）01-0124-01　　生物信息学是一个新兴学科。它以计算机为工具对生物信息进行存储，检索和分析，探究生命的奥秘。我们知道，每个人都是独立的个体。

2、没有完全相同的两个人。但是从基因序列的角度来看，不同的个体有很高的相似度，因为碱基对有99%是相同的。换句话说，仅有1%的碱基对的不同决定了遗传上的人与人的不同。例如，不同个体之间头发，鼻子，眼睛的不同等等。　　每个生物都具有基因组，绝大部分的基因组都是由DNA组成，当然个别基因组也可由RNA组成。DNA和RNA是有核苷酸组成的多聚分子。每个核苷酸包含一个单糖，一个磷酸基团，和一个碱基。碱基共四总，A，G，C，T，碱基配对原则A与T配对，G与C配对。一个基因是位于某条染色体的某个位置上的核苷酸序列，其中蕴含着某种特定的功能产物（如蛋白质）的编码。基因不仅可以

3、通过复制把遗传信息�鞯莞�下一代，还可以使遗传信息得到表达。染色体中基因组序列中单个碱基的差异称为单核苷酸多态性（SNP），单核苷酸多态性是人类基因突变中最常见的一种。双倍体生物的两条同源染色体几乎完全相同，每一条染色体上或染色体的某一区域上的所有SNP位点对应的等位基因构成的碱基序列构成一条单体型。那么装配单体型，对于分析SNP在人群中的分布和规律，发现与疾病相关的基因与多态位点就显得尤为重要了。　　1单体型装配问题[1]　　单体型装配问题针对的是染色体上的大量SNP数据，通过适当的方法，将其装配成一对单体型。由于染色体都的成对出现的。那么，如何将SNP片

4、段分成适当的两个集合，并且从每个集合按照一定的原则装配出一条单体型就是一个难点。另外，我们通过实验得到的小的SNP片段存在一些瑕疵，例如某些点数据的缺失，某些点通过实验得到的数据是错误的等等。因此，这些未知的因素使得我们装配单体型的难度变大了。单体型装配问题目前主要有三类：最少错误纠正（MEC）模型，最少片段去除模型，最少SNP去除模型。针对以上三种模型求解的主要方法，目前研究比较多的是启发式算法，这类算法优点是运用时间少，可以较快的找到问题的最优解。缺点就是找到的是最优解，不一定是准确解。由于得到的数据本身就有一定的瑕疵，因此由数据求解出的准确解也不一定是

5、最初问题的准确解。因此，我们一般认为在求解大规模计算中求出问题的最优解就是可以接受的了，事实证明，最优解和准确解误差不大，可以接受。　　2启发式算法研究　　2.1基于遗传算法的启发式算法[2]　　遗传算法是Goldberg在1989年提出的，是一个非常有用的启发式算法，已经在很多领域包括计算生物学如蛋白质结构预测，启动子序列识别，多序列比对等问题中成功应用。2005年王瑞省博士将遗传算法引入单体型重构问题，针对的是最少错误模型（MEC模型）。通过构造个体空间，设计适应度函数，选择算子，设计基于遗传算法的启发式算法，为了验证算法的有效性，通过ACE（血管紧缩转

6、移酶）基因数据集，DALY数据集进行验证，结果显示，设计的遗传算法适合解决规格较大的问题。但是针对SNP错误率较高的时候，重构率效果不是很好。　　2.2基于粒子群算法的启发式算法[3]　　粒子群算法（PSO）最早是由心理学研究学者Kennedy博士和从事计算智能研究的Eberhart博士于1995年提出来的一种智能算法。两位学者通过观察鸟类捕食的过程，从中受到启发，进而提出的一种算法。后来逐渐应用到优化问题当中，像车间调度，路由选择，以及整数规划问题，并且取得较好的效果。2006年钱伟懿将粒子群算法引入单体型重构问题。针对MEC模型，提出了基于改进粒子群算法

7、的启发式算法。它在原始粒子群算法中增加了记忆功能，提高了搜索速度。并将其应用到ACE基因数据集进行验证算法的有效性。同时与王瑞省的遗传算法进行了比较，表明算法的优越性，尤其是在SNP错误率较高的时候，基于粒子群算法的启发式算法重构率更高。　　2.3基于前馈神经网络的启发式算法[4]　　前馈神经网络，简称前馈网络，是人工神经网络的一种。1986年，Rumelhart，Hinton和EC/GI）模型，提出了基于前馈神经网络的启发式算法。对于MEC/GI问题由三层神经元组成。对于m个SNP片段，n个SNP位点的例子，网络有m个输入神经元，两个隐含神经元和一个输出神

8、经元。为了验证算法的有效性，对ACE基因数据和DAL