甘秋云

(福州理工学院计算与信息科学学院，福建 福州 350014)

1 引言

随着人类各项基因组计划的逐渐实施，核酸和蛋白质的数据正呈现指数级增长，如何处理分析庞大的生物数据，成为当今科学家所面临的一项重大的挑战，生物信息学也随之发展。生物信息学是一门将生物学、计算机科学、数学及其他处理技术相结合的学科，在生命科学研究中占有重要的地位，它的主要任务是探寻高效的研究和分析生物数据的工具，找出具有重要价值的生物学知识，从而分析和探究生物数据所蕴含的信息，进一步理解生命和进化关系[1]。

序列比对是生物信息学研究的主要课题之一，是运用特定的算法分析2条或多条序列之间的相似性的过程。通过序列比对，可以判断2条基因序列之间是否具有相似性，进而分析同源性，推导生物进化的过程，它对于发现生物序列中的功能、结构和进化信息都具有重要的意义[2]。

当今，序列比对算法有很多，主要类型有：双序列比对和多序列比对、全局比对和局部比对。典型的全局比对算法是Needleman-Wunsch算法，局部比对算法为Smith Waterman算法。双序列比对算法中较成熟的是基于动态规划的算法，和由此提出的FASTA(FAST-ALL)和BLAST(Basic Local Alignment Search Tool)算法；多序列比对主要用于识别多条序列的公共特征，主要有clustalW算法、MAFFT(Multiple Alignment using Fast Fourier Transform)算法和MUSCLE(Multiple Protein Sequence Alignment)算法[3]。

由于不同的比对算法具有不同的空间复杂度和时间复杂度，因此在序列比对过程中，数据的存储和比对结果的精准度也不同，面对呈指数级增长的生物数据，如何研究并设计一种高效精准的DNA序列比对算法，已经成为生物信息学面临的挑战之一。……