摘  要寻找多个字符序列的最长公共子序列是一个NP难问题,其中,求解两个字符串中的最长公共子序列LCS(Longest Common Subsequence,LCS)是求解多个字符串中的最长公共子序列MLCS(Multiple Longest Common Subsequence,MLCS)问题的一种特殊情况,它被广泛的应用于生物信息和基因计算等领域,是相关领域的基础性工作。尽管前人为此付出很大的努力解决该问题或其特殊情况,但随着数据量的急剧增长,字符序列的数量和长度不断增长,传统的算法效率较低,需要研究一种更为高效,可靠的方法来处理该问题。本文首先研究传统的LCS/MLCS算法,主要是动态规划方法和基于支配点的方法,以及最新的LCS/MLCS算法,如FAST_LCS算法和Quick_DP算法,并对其做出一定的改进,使用Java语言实现最新的算法和改进的算法,在主流平台上测试,并对其进行分析,提出进一步优化的方向。87037

毕业论文关键词:MLCS;动态规划;支配点;并行计算

Abstract Finding the longest common subsequence of a sequence consisted of characters is a NP hard problem, the solution of two strings of the longest common sub sequence LCS (longest common subsequence LCS) is a special case of the solution of a string of the longest common sub sequence MLCS of several strings (multiple longest common subsequence, MLCS), which is been widely used in the fields of biological information and gene computing, and it is the basic work in related fields。 Although previous paid great effort to solve the problem or the special circumstances, with a sharp increase in the amount of data, the continuous growth of character sequence number and length and the low efficiency of the traditional algorithm, we need to study a more efficient and reliable method to deal with the problem。 First of all, this paper studies the traditional LCS/MLCS algorithm, mainly is dynamic programming method and method based on control point and the latest LCS/MLCS algorithm such as FAST_LCS algorithm and Quick_DP algorithm, and try my best to make some improvements。 Finally, I use Java language to realize the FAST_LCS, Quick_DP algorithm and improved algorithm tested in the mainstream platform test and further optimization method is proposed in this paper。

Keywords: LCS; Dynamic Programming; Control Point; Parallel Computing

目  录

第一章  引言 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算法的优化

上一篇:java+mysql云平台的移动考试系统设计
下一篇:射频识别技术的公司会议签到系统后台子系统设计

基于PageRank算法的网络数据分析

大电流LED驱动器LTC3454【506字】

Windows操作系统最新补丁大全【3058字】

ERP技术发展的现状趋势及...

网页恶意代码的十一大危...

大网络环境下的数据挖掘用户的行为挖掘

C#+sqlserver大学体育馆预订管理系统设计

我国风险投资的发展现状问题及对策分析

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

互联网教育”变革路径研究进展【7972字】

老年2型糖尿病患者运动疗...

新課改下小學语文洧效阅...

安康汉江网讯

ASP.net+sqlserver企业设备管理系统设计与开发

张洁小说《无字》中的女性意识

网络语言“XX体”研究