刘清雪 罗宇航

摘 要：针对现有比对方法速度和准确率不高问题，采用混沌遗传算法快速搜索最优解，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算法，该法速度快、直接，但易早熟。第二种方法是精确的多序列比对方法，它比渐进法结果更优，但计算量过于集中，因此待比序列数量受限。第三种方法是基于迭代的方法，如模拟退火、遗传算法和进化编程等。遗传算法通过自然选择过程的类比，通过设计编码方式、遗传与变遗算子、设计目标函数、演化出一批候选解决方案。虽然遗传算法易于并行化，能降低时间成本，但其自身存在局部优化、收敛速度慢等缺陷，为此引入混沌算法来实现种群多样化以及快速收敛。……