仇瑛姿

摘 要：基因序列匹配是通过匹配算法，寻找两个或者多个序列之间的相似性和同源性，常见于对蛋白质序列和DNA序列的匹配。基因序列匹配算法从始至今，在保证匹配结果精度的前提下，不断演变出匹配时间较少的算法，以提供更优的匹配性能。文章即是介绍基因序列匹配算法的演变和实际的应用。

关键词：基因匹配；算法演变；算法应用

中图分类号：Q343.1 文献标志码：A 文章编号：2095-2945（2018）13-0063-02

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测序需求的增长将更为惊人，这些海量数据的积累和运算，挖掘与分析，离不开现代的计算机技术。

由于生物基因库的不断扩充和细化，提高基因序列匹配的性能迫在眉睫。基因序列匹配算法也由原来单一的动态规划，全局匹配逐渐发展成启发式的局部最优算法。同时为了获得更准确的数据，在查询匹配序列之前，添加了对基因序列的过滤条件，算法的不断创新加之对前人算法的改良，使基因序列匹配算法逐步走向成熟。……