基因序列匹配算法发展及应用基因序列匹配是通过匹配算法，寻找两个或者多个序列之间的相似性和同源 性，常见于对蛋白质序列和DNA序列的匹配。基因序列匹配算法从始至今，在 保证匹配结果精度的前提下，不断演变出匹配时间较少的算法，以提供更优的匹 配性能。文章即是介绍基因序列匹配算法的演变和实际的应用。标签：基因匹配；算法演变；算法应用Abstract： Gene sequence matching is to find the similarity and homology between two or more sequences by matching algorithm ， which is usually used to match protein sequence and DNA sequence. From the beginning to now， gene sequence matching algorithms have evolved to provide better matching performance under the premise of ensuring the accuracy of matching results. This paper introduces the evolution and practical application of gene sequence matching algorithm.Keywords： gene matching； algorithm evolution； algorithm application 绪论 随着生物科学和计算机科学的迅猛发展，计算机和生物相结合形成一门新学 科，利用计算机对数据的快速处理能力，挖掘大量而复杂的生物數据，为生物医 学的飞跃提供了有利条件。从1990年人类基因组计划至今，已完成了人类基因 组DNA30亿个碱基对的测序，破译了人类超过95%的遗传信息，我国也在2017 年 12 月启动了“中国十万人基因组计划”，通过绘制中国人精细的基因组图谱， 来研究疾病健康和基因遗传的关系。世界各国对生物基因组测序工作极快地展 开，而且可以预测，今后DNA测序需求的增长将更为惊人，这些海量数据的积 累和运算，挖掘与分析，离不开现代的计算机技术。由于生物基因库的不断扩充和细化，提高基因序列匹配的性能迫在眉睫。基 因序列匹配算法也由原来单一的动态规划，全局匹配逐渐发展成启发式的局部最 优算法。同时为了获得更准确的数据，在查询匹配序列之前，添加了对基因序列 的过滤条件，算法的不断创新加之对前人算法的改良，使基因序列匹配算法逐步 走向成熟。1 全局匹配算法全局匹配即整体考虑整条基因序列相似性，一条序列转化成另一条序列需要 的最小距离决定了该序列相似性的得分值，距离越小，则得分越高，相似度也越 高。较为常见的是动态规划算法，该算法通过拆解问题，之后处理问题之间不同 状态之间的关系，使问题可以通过递归的方式去分解1。动态规划算法适用于整体问题最优解包含子问题最优解和某一状态不会被