闫 磊,马 健,董 辉,高 梦

(亳州职业技术学院 信息工程系,安徽 亳州 236800)

基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究

闫 磊,马 健,董 辉,高 梦

(亳州职业技术学院 信息工程系,安徽 亳州 236800)

序列比对是将蛋白质中的基因或氨基酸进行对齐的动作,目的是要找出两序列的相似程度,而多重序列比对则是同时比对多个DNA或蛋白质序列,找出此序列群组中最佳的比对结果.本研究结合遗传算法及模拟退火算法,先利用遗传算法优化种群的概念,随着世代演进逐渐产生近似最佳解,再利用模拟退火算法进行小区块内的比对修正.实验结果显示,利用遗传算法与模拟退火算法的结合,使得遗传算法在跳脱局部最佳解的时候能有更大空间移动,而且也让模拟退火算法能有效解决经由遗传算法初步比对之后所产生的不良区域.两种算法结合的序列比对结果比任何单一算法的结果好,因此可以提升整体比对效果,将来能够为生物学家在判断未知序列功能时提供适当的帮助.

序列比对;多重序列比对;遗传算法;模拟退火算法

0 引言

对生物学家而言,探索蛋白质的序列对于细胞功能的影响、推测未知蛋白序列的功能、或比较不同的两个生物中的相似基因之间的差异时,序列的比对都成为不可或缺的一项重要技术.因此近年来在生物学中,序列比对成为一项重要的技术之一,对于蛋白质序列的比对、蛋白质结构的预测、DNA及MRNA的比对以及利用蛋白质序列搜寻DNA序列等方面都具有广泛的应用.而由序列比对所拓展的多重序列比对,对于生物学家而言更是一项困难且具挑战性的任务,因为多重序列比对其计所需的时间复杂度将随着序列数量的增加而呈指数性的成长,所以现在有许多算法应用在此领域.

对于只有两条序列的比对,利用动态程序规划可以达到最好的结果.然而利用动态程序规划算法虽然能够得到较好的结果,但在序列数量以及长度都增加的同时,对于计算机的计算资源会急剧的提高[1].此外,过去的研究也有利用遗传算法结合动态程序规划的方式进行比对,但仍有许多算法在处理这种问题上具有其优点,如模拟退火算法在处理解空间较小的问题上具有良好的表现.本研究使用没传算法及模拟退火算法所结合的算法来进行比对,并且对遗传算法以及模拟退火算法分别进行比对结果来比较,最后将模拟退火算法的概念引入遗传算法中进行比对,使得遗传算法在脱良局部最佳解的时候能有更大空间的移动,因此达到对比分数更高的序列比对[2].

本研究利用了遗传算法及模拟退火算法,先进行两者应用于多重序列比对的结果,再利用遗传算法输出的结果作为模拟退火算法所需序列的基础输入序列进行比对的调整,经过两种算法的运算之后,希望能够与过去专家所提出的研究能够达到相近的结果,并且与动态程序规划进行比对的结果能够相近.

1 序列比对

图1 未插入间隔于插入间隔序列比对的比较

生物序列比对是一种比较两个或多个DNA、RNA或蛋白质序列,并尝试找出序列中的一连串或单一的对应字符的方法.最常见是将两条序列并排成两行,将序列中相同或相似的区段置于相同的字段,而无法比对的字符则在各自的序列中利用插入间隔或产生错误.在最佳比对的情况下,插入间隔(gap)“-”可以让序列具有更好的比对结果,而间隔的出现就表示在序列演化的过程中发生了删除或插入的情况[3].如图1(a)所示,两个DNA序列的比对在还没插入“-”之前,序列A与序列B具有许多的比对错误的部分,在图1(b)的部分即由插入了“-”而使得整组序列达到比较好的比对结果.

1.1 全局比对

全局比对是尝试比对在序列中的每一个元素,即其比对是从序列的最前端到序列的最末端,目的是要找出两序列的相似程度.Needleman和Wunsch于1970年所提出的动态程序规划是一种序列全局比对的算法,且是首次将动态程序规划应用于序列比对领域上所开发出的一种方法,如图2(a)为全局比对[4].

1.2 区域比对

区域比对是寻找两序列中最相似的子序列或能够达到最高比对分数的序列片断,其目的是找出特定的基因片段或功能序列,Smith和Waterman于1981年所提出的动态程序规划便是一种序列区域比对的算法,如图2(b)为区域比对.

(a)全局序列比对 (b)区域序列比对

2 算法

2.1 遗传算法

遗传算法(genetic algorithm)最早在1960年由Holland 所提出,直到1975年Holland所著作的“Adaptation in Natural and Artificial System”奠定了遗传算法的基础.主要是利用模仿自然界中生物的演化过程作为求解问题的一种方法,通过基因的选择、母代与子代的筛选,以及使用适应函数来仿真达尔文进化论中物竞天择的部分.简单来说,遗传算法可说是一种不断尝试错误、淘汰不良母代以及选择优良后代的一种过程.

对于过去研究人员利用遗传算法来进行序列比对的处理的方式,由于单纯使用遗传算法在序列比对问题常常会产生次最佳解,因此通常都结合了多种方法,如表1所示.利用遗传算法解决序列比对问题的步骤包括:初始化序列、产生母群体并且进行竞争式选择、进行交配、进行突变、删除间隔字段、取代族群中的个体与结束演化等方面.

表1 应用遗传算法于序列比对的研究

2.2 模拟退火算法

模拟退火算法的概念是从物理学中所延伸出来,主要是指模拟固体加热至高温之后,其组成的结构会变成液态结构,并且此时结构分子的活动力较强,分子可以随机跳动的距离也较大.随着温度的下降,组成的结构分子也逐渐稳定下来,此时可以跳动的距离也逐渐缩小,形成这个阶段的热平衡,然后重复进行降温、结晶的动作并排列成固体状态,而最后稳定的状态也就是最佳解[5].此方法中最重要的部分即为温度的调控,若温度下降过快则可能会导致产生区域最佳解.尽管模拟退火算法对于优化问题求解的过程较缓慢,过去仍有许多研究已经应用于多重序列比对的领域,利用模拟退火算法解决序列比对问题的步骤包括:初始化序列、适应成本的计算、温度及降温的参数设定、间隔跳动.

2.3 遗传算法与模拟退火算法结合

图3 遗传算法与模拟退火算法结合流程图

由于遗传算法的求解过程中需要产生挑选可用的母代族群,且族群数量也是进行遗传算法时必须的参数,而模拟退火算法则是比较更新前与更新后彼此状态的成本差异,就产出的解数量来说,遗传算法的族群中每个染色体都代表着一个解,而模拟退火算法每次针对一个解进行修正.因此在结合这两种算法时,本研究先利用遗传算法产出模拟退火算法所需的初始序列,接着进行模拟退火算法中的移动方法来寻找是否有表现更好的解存在[6].图3为结合两种算法之后的比对流程.

3 实验结果与分析

3.1 实验资料来源

本研究采用某生物信息中心的部分数据,在收集的数据资料中选取8个数据集,为了整理出与过去文献中所提到不同的间隔插入方式,先进行序列之间彼此差异程度的计算,方法是计算数据集中各个序列中四种字符的总数以及最大差距,并且利用最长与最短序列的差距来计算出所需插入间隔的数量,各个数据集的差距如表3.利用表2中的序列资料及表3的序列内容分析,可以发现部分的数据集中如S3、S7,各个序列之间字符的彼此差距数量并无非常明显,且数据集中最长序列减去最短序列的差距也相差不多,因此本研究在实验设计中加入了由此两项数值所计算出的间隔插入数量.

表2 DNA序列原始数据

表3 各个序列的字符差距最大数目与平均差距

续表3

注:表3中A,T,G,C表示碱基

3.2 参数设置

进行遗传算法以及模拟退火算法时,其中的参数设定将会影响到多重序列比对的结果.因此在此阶段先将各个算法所需的参数做分组配置,作为实验的分组依据,同时并参考了过去的文献作为参数设定的依据.表4为遗传算法所需各种参数如族群大小、交配率、各个突变操作数的突变率及矩阵延伸长度的设定,其中Max代表序列群组中长度最长的序列,Min代表序列群组中长度最短之序列, extension代表整个序列群组中四种字元最大最小值的差异,利用表3中的数据计算所得.表5为模拟退火算法中接受率、初始温度、凝固温度以及降温参数的设定.

表4 遗传算法数设定

表5 模拟退火算法参数设定

3.3 实验结果与分析

(1)遗传算法与动态规划算法预测结果分析

通过上面算法的分析,本文先使用遗传算法与动态规划算法组合对DNA多重序列进行比对.首先设置遗传算法参数,利用交叉操作产生实验数据,再利用动态规划算法对遗传算法进行优化,在较小范围随机产生组态,并对每一组进行优化,提高对DNA序列比对的效率,如表6所示.

表6 遗传算法与动态规划算法DNA序列预测结果

(2)遗传模拟退火算法对DNA序列比对分析

本研究首先使用遗传算法进行多重序列比对,利用表4中的参数设定,各个组态分别利用交叉参数设置产生实验组别,共产生 27个实验组态,并选取S2对每个组别各进行五次之后得出最佳的参数设置.利用此参数进行8次实验且比较之后所得出的最佳配对分数、平均配对分数以及平均比对时间,具体如表7所示.而由此结果得到在本研究的流程中,对于遗传算法最佳参数设计分别是:交配率为80%、突变率为20%、族群大小为20条、世代数量为15,000代以及矩阵延伸长度为Max×1.

表7 遗传算法的多重序列比对结果

接着第二阶段进行本研究所使用的模拟退火算法进行多重序列比对,利用表5的参数设定,各个组态分别采取交叉参数设置产生实验组别,并利用数据集S1进行8次实验后得出的最佳参数设置,且用此参数对各数据集进行五次实验之后所得出的最佳配对分数、平均配对分数以及比对时间，具体如表8所示.由此表得到的模拟退火算法最佳参数设计分别是初始温度为100℃,降温参数为 3℃,接受率为80%.

表8 模拟退火算法的多重序列比对结果

两种算法演算完之后,接着进行第三阶段的流程.利用遗传算法进行比对所得到的解序列作为下一个模拟退火算法流程中所需的初始序列,并改变第二阶段模拟退火算法中间隔跳动操作数作用的位置与范围,而其参数设定分别采用遗传算法以及模拟退火算法的最佳参数设置,其整体的比对结果如表9所示.

表9 遗传算法结合模拟退火算法的多重序列比对结果

总之,通过两种算法对DNA序列比对的实验结果表明,本研究利用遗传算法与模拟退火算法结合在多重序列比对上能够达到不错的修正结果,在数据集S1与S5中甚至能够达到相当的比对结果.在遗传算法中所必须被设定的各项信息,如间隔插入数量、突变率以及交配率等,都与产出的结果相关,若能够加强在遗传算法中各个操作数的使用方法以及执行程序,对于近似最佳解的收敛将具有相当程度的改善.

4 结 语

本研究利用遗传算法的物竞天择的概念,随着世代演进所逐渐产生的近似最佳解,接着再利用模拟退火算法进行小区块内的比对修正.实验结果表明,利用遗传算法与模拟退火算法的结合,其比对结果都比任何单一算法的结果好,通过结合也可让模拟退火算法有效的解决经由遗传算法初步比对之后所产生的不良区域,进而修正且更进一步提升整体比对的效果.

[1]朱彦廷.用遗传算法求最小生成树[J].琼州学院学报,2012,19(2):32-35.

[2]马健.决策树算法对电子商务交易信任机制的应用研究[J].河北北方学院学报,2015,31(5):36-39.

[3]张冰龙,徐建敏,江浩.基于模拟退火的DNA遗传优化小波多模盲均衡算法[J].电子技术应用,2016, 42(2):88- 91.

[4]李志亮,罗芳.基于初始值优化的灰色马尔科夫链预测模型研究[J].海南热带海洋学院学报,2016,23(5):55 -59.

[5]崔光照,李小广,张勋才,等.基于改进的粒子群遗传算法的DNA编码序列优化[J].计算机学报, 2010, 33(2):311-316.

[6]王哲河,林越,张侨.Dijkstra算法在三亚旅游线路规划中的应用[J].琼州学院学报,2015,22(5):98-102.

(编校：曾福庚)

Application of Genetic Algorithm and SimulatedAnnealing Algorithm in Multiple DNA Sequences

YAN Lei, MA Jian, DONG Hui, GAO Meng

(Department of Information Engineering, Bozhou Vocational and Technical College, Bozhou Anhui 236800, China)

The goal of sequence alignment—the alignment of genes or amino acids in proteins—is to uncover the similarity of two sequences.However, multiple sequence alignment is the comparison between multiple DNA sequences or protein sequences in order to discover the optimal comparing between the sequences groups.In the current study, genetic algorithm and simulated annealing methods were used to optimize the population concept by genetic algorithm.With the generation evolution, the approximate optimal solution was gradually generated.The experimental results show that the combination of genetic algorithm and simulated annealing methods enables the genetic algorithm to have more space to move when the local optimal solution is obtained, and the simulated annealing method can effectively solve the genetic algorithm for the bad regions.The combination of the two algorithms is better than the results of any single algorithm, so it can improve the overall alignment effect and will provide the biologist with appropriate help in judging the unknown sequence function in the future.

sequence alignment; multiple sequence alignment; genetic algorithm; simulated annealing method

格式：闫磊,马健,董辉,等.基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究[J].海南热带海洋学院学报,2017，24(2)：64-69.

2017-02-15

安徽省教育厅自然科学研究重点课题(KJ2016A493);安徽省亳州市产业创新团队科研项目(亳组[2015]20号-2);亳州职业技术学院院级课题 (BYK1511)

闫磊(1984-),男,回族,安徽亳州人,亳州职业技术学院信息工程系助教,研究方向为数据挖掘、人工智能方向.

TP18

A

2096-3122(2017) 02-0064-06

10.13307/j.issn.2096-3122.2017.02.13