一种适合大数据分析的mlcs算法的设计与实现(附件)【字数：16917】
摘 要摘 要寻找多个字符序列的最长公共子序列是一个NP难问题，其中，求解两个字符串中的最长公共子序列LCS(Longest Common Subsequence，LCS)是求解多个字符串中的最长公共子序列MLCS(Multiple Longest Common Subsequence，MLCS)问题的一种特殊情况，它被广泛的应用于生物信息和基因计算等领域，是相关领域的基础性工作。尽管前人为此付出很大的努力解决该问题或其特殊情况，但随着数据量的急剧增长，字符序列的数量和长度不断增长，传统的算法效率较低，需要研究一种更为高效，可靠的方法来处理该问题。本文首先研究传统的LCS/MLCS算法，主要是动态规划方法和基于支配点的方法，以及最新的LCS/MLCS算法，如FAST_LCS算法和Quick_DP算法，并对其做出一定的改进，使用Java语言实现最新的算法和改进的算法，在主流平台上测试，并对其进行分析，提出进一步优化的方向。关键词MLCS；动态规划；支配点；并行计算
目 录
第一章 引言 1
1.1 研究背景和意义 1
1.2 国内外研究现状 1
1.3 本文工作 2
1.4 本文组织结构 2
第二章 LCS/MLCS问题的概述 3
2.1 LCS/MLCS问题的描述 3
2.2 传统算法概述 3
2.2.1 基于动态规划的算法 3
2.2.2 基于支配点的算法 4
2.2.3 并行算法 6
第三章 LCS/MLCS问题的算法 7
3.1 FAST_LCS 7
3.1.1 匹配点和它的后继表 7
3.1.2 裁剪操作 9
3.1.3 FAST_LCS的框架和复杂度分析 10
3.1.4 结论 15
3.2 Quick_DP 15
3.2.1 串行算法 15
3.2.2 并行算法 18
3.3 MLCS算法的优化 19
3.3.1 优化算法的设计 19
3.3.2 继续优化方向 21
第四章 算法的代码实现 23 *好棒文|www.hbsrm.com +Q: ^351916072^
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 国内外研究现状
Smith?Waterman算法在1981年提出，是在Needleman?Wunsch算法发展而来的一种知名的LCS算法，并被证明是正确的。Aho 和eral通过决策树模型[3]计算出时间下限为O(mn)。通过动态规划算法[4]，这个问题能够用O(mn)的空间和O(mn)的时间解决。Mayers和Miller使用Hirschberg提出的技术在同样的时间精度下将空间效率降低至O(m+n)。
为了更多地减少计算时间，一些不同计算模型下的并发算法被提出。对于CREWPRAM模型，Aggarwal和Apostolicoetal各自独立的提出使用mn/logm 个处理器，时间效率为O(logmlogn)的算法。Luetal设计了两个并发LCS算法，一个使用mn/logm个处理器，时间效率为O(log2n+logm),另一个使用mn/(log2mloglogm)个处理器，时间效率为O(log2mloglogm)。Apostolicoetal提出了使用mn/loglogm个处理器，时间效率为的算法。Babu和Saxena优化了这些算法，他们提出使用mn个处理器时间复杂度为O(log2n)的并发算法。很多并发LCS算法也提出使用收缩阵列[5]，Robertetal提出使用m(m+1)个处理器，需要n+5m步骤的算法。Changetal提出使用mn个处理元素，需要4n+2m步骤的算法。Luceetal设计了一个带有m(m+1)/2个处理器的收缩阵列，需要n+3m+q步骤的算法（其中q是LCS的长度）。Freschi和Bogliolo提出计算RLE字符串的LCS的问题。他们的算法通过使用M+N个处理器元素的收缩阵列需要O(m+n)步骤的算法（M和N分别为相应字符串的长度，m和n运行在游程编码的相应长度）。
如果求解多个字符序列的公共子序列，时间复杂度会随着字符序列的增长急剧增长。比如，若是使用SmithWaterman算法去求解多个字符序列的LCS问题，时间复杂度就变为O(
2
n
?1)
i=1
n
n
i
，其中n是字符序列的数量，是相应字符序列的第i个字符。当n变得非常大时，算法就不可行。一些优化在此基础上就提出来了。MSA算法能够处理多达10个字符序列。从Carrillo和Lipman算法可以看出，对多维空间拆分并不能解决问题和免除计算。Stoye提出了一个继承自MSA算法的分而治之算法的DCA算法[6]。最近DCA的迭代实现算法OMA被证明能够提高DCA的效率和减少内存需求。基于Feng和Doolittle的算法，ClustalW被认为是在LCS计算上应用最为广泛的多字符序列匹配软件。
1.3 本文工作
目 录
第一章 引言 1
1.1 研究背景和意义 1
1.2 国内外研究现状 1
1.3 本文工作 2
1.4 本文组织结构 2
第二章 LCS/MLCS问题的概述 3
2.1 LCS/MLCS问题的描述 3
2.2 传统算法概述 3
2.2.1 基于动态规划的算法 3
2.2.2 基于支配点的算法 4
2.2.3 并行算法 6
第三章 LCS/MLCS问题的算法 7
3.1 FAST_LCS 7
3.1.1 匹配点和它的后继表 7
3.1.2 裁剪操作 9
3.1.3 FAST_LCS的框架和复杂度分析 10
3.1.4 结论 15
3.2 Quick_DP 15
3.2.1 串行算法 15
3.2.2 并行算法 18
3.3 MLCS算法的优化 19
3.3.1 优化算法的设计 19
3.3.2 继续优化方向 21
第四章 算法的代码实现 23 *好棒文|www.hbsrm.com +Q: ^351916072^
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 国内外研究现状
Smith?Waterman算法在1981年提出，是在Needleman?Wunsch算法发展而来的一种知名的LCS算法，并被证明是正确的。Aho 和eral通过决策树模型[3]计算出时间下限为O(mn)。通过动态规划算法[4]，这个问题能够用O(mn)的空间和O(mn)的时间解决。Mayers和Miller使用Hirschberg提出的技术在同样的时间精度下将空间效率降低至O(m+n)。
为了更多地减少计算时间，一些不同计算模型下的并发算法被提出。对于CREWPRAM模型，Aggarwal和Apostolicoetal各自独立的提出使用mn/logm 个处理器，时间效率为O(logmlogn)的算法。Luetal设计了两个并发LCS算法，一个使用mn/logm个处理器，时间效率为O(log2n+logm),另一个使用mn/(log2mloglogm)个处理器，时间效率为O(log2mloglogm)。Apostolicoetal提出了使用mn/loglogm个处理器，时间效率为的算法。Babu和Saxena优化了这些算法，他们提出使用mn个处理器时间复杂度为O(log2n)的并发算法。很多并发LCS算法也提出使用收缩阵列[5]，Robertetal提出使用m(m+1)个处理器，需要n+5m步骤的算法。Changetal提出使用mn个处理元素，需要4n+2m步骤的算法。Luceetal设计了一个带有m(m+1)/2个处理器的收缩阵列，需要n+3m+q步骤的算法（其中q是LCS的长度）。Freschi和Bogliolo提出计算RLE字符串的LCS的问题。他们的算法通过使用M+N个处理器元素的收缩阵列需要O(m+n)步骤的算法（M和N分别为相应字符串的长度，m和n运行在游程编码的相应长度）。
如果求解多个字符序列的公共子序列，时间复杂度会随着字符序列的增长急剧增长。比如，若是使用SmithWaterman算法去求解多个字符序列的LCS问题，时间复杂度就变为O(
2
n
?1)
i=1
n
n
i
，其中n是字符序列的数量，是相应字符序列的第i个字符。当n变得非常大时，算法就不可行。一些优化在此基础上就提出来了。MSA算法能够处理多达10个字符序列。从Carrillo和Lipman算法可以看出，对多维空间拆分并不能解决问题和免除计算。Stoye提出了一个继承自MSA算法的分而治之算法的DCA算法[6]。最近DCA的迭代实现算法OMA被证明能够提高DCA的效率和减少内存需求。基于Feng和Doolittle的算法，ClustalW被认为是在LCS计算上应用最为广泛的多字符序列匹配软件。
1.3 本文工作
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/wlw/408.html
