刘清雪 罗宇航

摘 要：针对现有比对方法速度和准确率不高问题，采用混沌遗传算法快速搜索最优解，Spark云计算进行并行化比对，大幅降低比对执行时间以及提高比对准确度，为解密生物遗传密码提供有效工具。

关键词：Spark云计算;混沌遗传;基因序列比对

中图分类号：TP391 文献标识码：A DOI：10.3969/j.issn.1003-6970.2021.03.011

本文著录格式：刘清雪，罗宇航.基于Spark云计算及混沌遗传的基因序列比对研究与实现[J].软件，2021，42（03）：040-042

Research and Implementation of Gene Sequence Alignment Based on Spark Cloud Computing and Chaotic Inheritance

LIU Qingxue， LUO Yuhang

（Jilin University of Architecture and Technology， Changchun  Jilin  130114）

【Abstract】：In view of the low speed and accuracy of existing comparison methods， chaotic genetic algorithm is used to quickly search for the optimal solution， and Spark cloud computing is used for parallel comparison， which greatly reduces the comparison execution time and improves the accuracy of the comparison， for decryption The biological genetic code provides an effective tool.

【Key words】：spark cloud computing;chaotic inheritance;gene sequence alignment

生物信息学是一门新兴的领哉，是一门利用计算机技术研究生物系统之规律的学科，序列比对是生物信后序研究内容如进化树、蛋白质结构预测、药物设计等工作的基础。在序列比对研究中通过查找到相似的基因序列，相似度推测及进化关系分析等来追溯序列的进化关系。生物序列比对是非常活跃的领域，国内外对其进行了广泛的研究并提出了许多方法。第一种方法是渐进对齐方法，通过动态规划（DP）算法，Needleman-wunsch 或Smith-waterman，可以找到最高的得分一致性。然而，为了适应海量数据，大多的多重序列比对采用了启发式算法。如T-coffee算法，该法速度快、直接，但易早熟。第二种方法是精确的多序列比对方法，它比渐进法结果更优，但计算量过于集中，因此待比序列数量受限。第三种方法是基于迭代的方法，如模拟退火、遗传算法和进化编程等。遗传算法通过自然选择过程的类比，通过设计编码方式、遗传与变遗算子、设计目标函数、演化出一批候选解决方案。虽然遗传算法易于并行化，能降低时间成本，但其自身存在局部优化、收敛速度慢等缺陷，为此引入混沌算法来实现种群多样化以及快速收敛。随着测序数据的增长，传统的并行处理方法已经无法有效进行数据的存储、分析和处理。而Spark云计算中对输入数据在内存中采用的缓存的机制，数据只被加载一次，极大地节省了反复读取的时间，极大的提高了运算效率[2]。

本文设计了一种基于混沌遗传算法快速搜索算法，通过混沌计算提高比对速度和准确度。采用Spark云计算进一步提高基因序列并行比对速度，以及Hadoop HDFS的可扩展基因序列增量存储系统提高存储效率。

1基因序列比对原理分析及遗传算法与混沌理论研究

基因比对通常用于比对两条DNA序列或者蛋白质序列的同源性或者说相似性。首先对经典的动态规划进行了分析，其将一个大问题变成小问题，并逐步求解。由第一个字符开始，假设为缺失，此后每增加一个字符，都有三种可能：mismatch，match，deletion/insert，计算对应的打分，得高分者为最优解，逐步迭代至最后一个字符[1]。

双序列比对的实质就是在两条待比较序列的任意位置插入一个或多个空位，使两个序列具有最大的相似性，然后再根据比较结果推断其生物学意义。

遗传算法是计算数学中用于解决全局最优解的一种进化搜索算法。利用生物进化的规划，首先对问题的解空间进行编码，产生一定的个体，再通过遗传、变遗、自然选择及杂交等手段对个体进行演变，然后再始搜索。但传统的遗传算法亦存在不足，如早熟收敛、随机漫游等。

混沌是决定动力學系统中出现的一种貌似随机的运动，这种运动就是由系统内部的非线性因素引起的。

混沌是对确定性事物混乱无序状态中潜在内在规律的一种描述，是非线性科学的重要分支。混沌的基本思想可以理解为，首先把原有混沌空间的混沌变量，线性映射到求解间，然后根据混沌的特性，在解空间对目标进行混沌搜索，混沌优化方法具有初始条件有很强的敏感性，初始条件下非常微小的变化，若经过n次不断放大，也会造成巨大的影响。正是这种第三性，才使混沌算法容易跳出局部最优点，找到全局最优解。

鉴于混沌优化理论与遗传算法的特点，将二者相结合提出一扬长避短的新的方法，即能提高收敛速度，又能跳出局部最优的局限。组织算法首先通过混沌优化过程产生初始个体，再以遗传算法求得的最优解为中心加以小幅度混沌扰动，来进行搜索，找到全局最优点。

2基于混沌遗传的双序列比对改进算法

经典遗传算法存在种群分布不均匀，收敛速度慢，常陷于局部最优解等问题。针对此问题提出基于Logistic映射的混沌遗传算法，使用混沌映射产生混沌序列代替随机个体产生过程来改进遗传算法，保持种群多样性的同时提升算法效率，降低迭代次数达到全局最优解。主要研究以下四个方面的内容。

（1）基因序列的遗传编码;

（2）适应度计算函数的设计;

（3）空位罚分;

（4）混沌与遗传算子的融合，依据序列比对的主要操作和遗传算法的进化过程，设计了选择、混沌交叉和混沌变异三种算子。

2.1基因序列的遗传编码

例：对如图1所示的序列S和序列T，根据Need-leman-Wunsch算法建立矩阵，在矩阵的当前位置向下一位置移动只有三种可能，向右、沿对角线向右下、向下，并分别用字符R、B和D表示，则两个序列的比对的一个结果，便可用从矩阵左上角到右下角的一条路线，这个路线可以用一个字符串A来表示，且该字符串中的字符属于集合{R，B，D}。向下或向右移动一格，表示在垂直或水平序列中插入一个空位，沿对角线移动一格，表示下一位两序列的字符是匹配的。序列S与T的比对结果则可以表示为字符串：“BBBBBRBBBB”，即为染色体的编码。

2.2适应度计算

对于每一个体，根据其对应的序列比对字符串及空位罚分公式计算出相应序列比对的分值，适应度值是个体是否能进行迭代的依据，在其计算的过程中要适应度值不为负，如出现负值则需要做一定的转换。

2.3空位罚分

生物在进化过程中，必然会有基因的改变，因此在实际的序列比对时必须考虑碱基的插入或缺失的变化，而这种插入和缺失可能是一个也可能是多个碱基缺失或插入，空位罚分即是为反映这种变化的方法。为了能更真实的反应出序列的相似性，采用更能体现生物学意义的仿射空位打分法。单个空位与连续空位采用不同的赋值方法，单个的空位罚分采用定值Xg，连续空位中第一个空位为Xg，之后的每个空位用Yg表示，连续的空位长为K，则仿射空位打分法的计算方法为Xg+k*Yg。

2.4混沌遗传算子设计

依据序列比对的主要操作和遗传算法的进化过程，设计了选择操作、混沌交叉操作和混沌变异操作。

（1）选择操作：每次选择两个个体，仅保留适应度较大的个体进入下一代群体中待选，将生成的初始群体中的PopSize个个体进行适应度评价，适应度值越大的个体被遗传到下一代的概率也越大。本算法采用随机联赛选择（Stochastic Tournament Model）方，联赛规模N的取值为2。

（2）混沌交叉操作：设有L位长染色体，在（0，1）区间上随机取一个数xn为初值，利用Logistic 模型迭代产生一个（0，1）区间的混沌序列xn+1。利用公式C= （int）xn+1*L把序列xn+1映射至染色体基因位置空间，以此来确定交叉操作发生位置，并以概率Pc进行单点交叉。在形成新的子代的过程中，仅需小范围更换部分点基因。

（3）混沌变异操作：利用混沌序列确定混沌交叉位置的方法来确定变异点位置，并以pm的概率从父代中随机选取变异个体，在某一位或某几位变异位置上作变异运算。

（4）结束条件：达到预定的迭代次数或者最大值不在变化时停止搜索。

3基于Spark云计算的基因序列比对实现实验环境

本实验的Spark集群是由一个主节点（NameNode）和3个从节点（DataNode）构成。以学院实验室的虚拟化大数据平台为基础，采用如下的配置：64位虚拟机4台，Centos6.5操作系统;服务器为Apache的hadoop- 2.5.2;Spark版本为Spark-3.0.6，JDK版本为1.8;Scala版本为2.12.6，并采用集成的开发环境Eclipse。

为了提高本实验的可比性，在实验室的同等配置的虚拟机上，安装与Spark集群相同的操作系统，作为单机版实验。并从NCBI（national center for biotechno-logy information）下载不同大小数据集的比对序列进行两种实验的比对，结果如表1所示：

4结论

該算法利用混沌算法与遗传算法的互补性，一定程度上增强了序列比对的敏感性，改进了比对质量，优化了遗传算法的局部搜索能力。由于Spark云计算的运行机制，本算法在处理大规模数据多步迭代计算时，能大大的提高计算效率，随着文件大小的增加，处理相同的数据集时，集群方法明显比单机法时间，且文件越大，这种优势越明显。但在分析小数据时则没有更多的优势。

参考文献

[1] 王芳芳，马志强，王素华.基于遗传算法的序列比对方法[J].吉林大学学报（信息科学版），2013（3）：423-429.

[2] 刘振羽.基于Spark的基因组学数据比对算法的并行化研究与比对平台构建[D].呼和浩特：内蒙古农业大学，2019.