基于格代数的最长公共子序列近似求解  

Computing Longest Common Subsequences Approximately Based on Lattice

作　　者：孙焘[1] 朱晓明[1] SUN Tao ZHU Xiao-ming(School of Innovation and Entrepreneurship, Dalian University of Technology, Liaoning 116024, China)

机构地区：[1]大连理工大学创新创业学院,辽宁116024

出　　处：《计算机科学》2017年第2期270-274,共5页Computer Science

摘　　要：多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构"格",通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。The longest common subsequences can represent the common information of a sequence set,and it has many important applications in many fields,such as computational genomics,information retrieval and so on.Computing longest common subsequences is a famous NP-hard problem with multiple solutions.Some approximate algorithms have a low time complexity,but the result set only has one subsequence.For the sequence set with many longest common subsequences,the information loss is overmuch.In this paper,we presented a new approximate algorithm for this problem.Our algorithm employs a specific mathematical structure called lattice.Firstly,the common lattice of two sequences is computed through dynamic programming and then the common lattice of the current lattice and the current sequence recursively combined with the greedy algorithm are also computed.As the paths in a common lattice contain many common subsequences,the result set contains many longest common subsequences of the original sequence set.And the validity of our algorithm is proved through theory and experiment.

关 键 词：最长公共子序列 格 近似算法 贪心算法 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]