3。3。1 优化算法的设计 19

3。3。2 继续优化方向 21

第四章  算法的代码实现 23

4。1 FAST_LCS的代码实现 23

4。2 Quick_DP的代码实现 25

4。3 新的算法的代码实现 27

第五章  算法测试 29

5。1 FAST_LCS的测试 29

5。2 Quick_DP的测试 31

5。3 新的算法的测试 34

第六章  总结与展望 35

结  论 36

致  谢 37

参 考 文 献 38

第一章  引言

1。1 研究背景和意义

生物序列可被视为符号数列。比如，一个蛋白质可由20个不同的字母（氨基酸）组成，DNA序列（基因）可被视为由DNA中最基本的4个子结构A，C，G和T组成。当一个新的生物序列被发现，如果想要知道与它最相似的其他序列，可通过字符序列匹配。序列匹配还能成功的在引起癌症的基因和正常基因找到他们之间的联系。查找多个字符序列的相似点的一种方法就是寻找他们的最长公共子序列。

寻找两个字符序列的最长公共子序列就是前面提到的LCS问题。虽然LCS问题是全部序列对比一种特殊情况，但是所有序列对比的算法都能用来解决LCS问题。将字符序列的数量扩展至2个以上，就为MLCS问题。该问题的研究成果能被广泛的应用于生物基因[1]，模式识别[2]等领域，具有广泛的前景和深远的意义。

1。2 国内外研究现状

1。3 本文工作

在这篇论文中，介绍LCS/MLCS问题的传统算法，详细描述最新算法，提出优化方法，并实现算法并验证结果，提出该问题可进一步优化的方向和方法。

1。4 本文组织结构

在第一章中，介绍该问题的相关背景和国内外现状，第二章中对该问题进行了详细的描述，并对传统算法进行了较为详细的说明，第三章中实现了该问题目前较为优秀的算法FAST_LCS算法[7]，Quick_DP算法[8]和优化后的新算法，第四章中实现算法，第五章中验证算法结果。第六章是总结该问题和展望未来的解决方向。

第二章  LCS/MLCS问题的概述

2。1 LCS/MLCS问题的描述

在一个既定的字符序列中删除多个字符就可得到它的字符子序列。假设序列 A={a1,a2,…,an}和 B={b1 ,b2 ,…, bn}是基于字符集∑上的两个字符串，那么最长公共子序列就是查找X与Y当中数量最多的字符数的集合。而MLCS问题就是寻找3或者3个以上字符串的最长公共子序列。因此，LCS问题是MLCS问题的一种情况。一般情况下，MLCS并不唯一，多个字符序列可能存在多个MLCS。

目前有多种性能良好的LCS/MLCS算法，从技术角度可以将算法分为动态规划算法和基于支配点的算法[9]。从算法的并发角度可以将该算法分为串行算法和并行算法[10]，下面将对此做一个简单的介绍，阐述相关的算法。

2。2 传统算法概述

2。2。1 基于动态规划的算法

MLCS问题的传统方法是以动态规划算法为基础的。在最简单的情况下，给定两个长度分别为n1和n2的字符序列a1,a2，动态规划算法反复的建立一个n1*n2的矩阵L，其中L[i,j],0<i<n1,0<j<n2，a1[1,2,。。。,i]和a2[1,2,。。。,j]前缀的LCS(最长公共子序列)的长度，定义如下：