一种最优相似度的公共序列研究

武明超 崔晓兵 姚欣 邵咏慧

摘   要：针对多条序列最长公共子序列的多解问题，为了能够求出若干条字符串序列，对它们共有的最大相似序列，在计算中按照相似度和长度进行打分，并且对输出的子序列进行排序，以便能够输出相似序列的位置并且达到最优的相似度。根据最优相似度确定字符串之间匹配的公共长度和重复率，用比重复率作为判别相似度的一个指标，在一个已知的字符串，通过和其他字符的比较，利用此种思想，可以找出插入在字符串中的空格位置，并能使相似度达到最优化。通过构建代数结构“格”，利用递归求解当前格与当前序列的公共格。再通过动态规划求出最长公共子序列的长度数组和状态数组，矩阵搜索求出所有有效的跳跃点，能有效避免重复搜索，大大提高时间效率。

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

随着科学技术的进步，人们利用序列的相似性比较研究各个方向。例如，生物学中的亲子鉴定、医学中的诊断病基因确定疾病。随着科学的进步，字符串之间的相似问题也成为研究的重点，同时，提出了许多类似于上述的序列相似度算法。根据不同的特征，相似度的计算方法也不尽相同，主要有方面相似算法、统计关联算法、相似语义算法等。有人提出结合3种算法的优缺点，建立多层规划模型。其中，相似字面主要包括距离编辑和类似的字或者詞语的计算方法。因此，此研究在各个方面都得到了广泛的应用。例如同分异构的数据检索、图谱分析以及基因分析等。多条序列的最长公共子序列可以代表多条序列的公共信息，其在诸多领域里有着重要的应用，针对求解多条序列的最长公共子序列式的非确定性多项式（Nondeterministic Polynominal，NP）（Non-deterministic Polynomial，NP）难问题，本质为多解问题。一些近似算法虽然时间复杂度较低，但只能求出单一解，对于有多解的序列集合，求得的结果信息量损失较大。针对求解多条序列的最长公共子序列式的多解问题，本文利用一个新的近似算法来解决最长公共子序列问题。算法引入了称为“格”的代数结构，利用动态规划求出两序列的公共格，并通过递归求得当前格与当前序列的公共格。求得公共格中的路径保存了多条公共子序列，使最终求出的最长公共子序列也为多个。根据最长公共子序列的特点，利用动态规划法求出最长公共子序列的长度数组和状态数组，并通过矩阵搜索求出所有有效的跳跃点，构造求解所有最长公共子序列的算法并通过程序给予实现。能有效避免重复搜索，时间效率大大提高，特别适用于基因工程中的基因片段分析，并通过实验验证了算法的可靠性[1]。

1    算法介绍

广义后缀树（Generalized Suffix Tree，GST）算法思想是利用长度为m的串P，利用某个函数通过计算得到每个对应的序列值。并且把每个长度为1的字符串按照一定的长度进行划分，便可以得到一定长度的子串，然后对每个子字符串利用同样的函数计算便可以得到一个序列值。只有那些和模式串有相同序列值的子字符串才有可能和模式串匹配。如果文本子字符串中的序列值和模式串的序列值都不相同的话，那么该字符串一定不能匹配模式串。在RKRGST算法中指定一个长度，这个长度也可被称为搜索长度，利用这个长度可以对两个字符串同时进行划分，使用同一个序列，两数分别计算出每个划分的序列值，并且存储起来，然后通过比较字符串这些序列值，凡是序列值相同的就认为这两个长度是子字符串匹配，然后对这两个子串后面的字符串进行贪婪匹配，如果后面的字符依旧相同，则继续匹配，直到两者不能匹配为止，同时，记录这个匹配长度和分别在字符串中开始匹配的位置与字符中开始匹配的位置，首先，将这些信息储存起来;然后，继续去匹配其他长度的子串，通过对每对能够匹配的子串都进行贪婪匹配，最后，再记录匹配的长度、开始位置等信息。如果有两次找到的匹配的最大长度是相同的，那么就将新找到的匹配信息记录到前一个和其匹配长度相同的后面，从而可以形成一个匹配链表[2]。

2    改进后的格算法

本文研究了一个计算最长公共子序列[1]的算法，称为格方法。该方法利用了代数结构[2]，尽可能多地保存动态规划[3]信息，与传统算法相比，此算法在集中的序列数量与精确度方面都有一定提升。如果节点数增加，会导致公共格中的路径数量也会增加，进而为找到更长的公共子序列[4]提供了可能性。就算小灵通定位系统（Location Service Center，LSC）的长度没有变化，由计算得出的信息也使最终求出的数量增加[3]。

在很多领域内，求解最长公共子序列都有着重要的应用。在求信息序列的最大子序列时，首先，提取序列的公共信息，通过进一步检索与分类。获取各个基因序列间的匹配度。由于格结构自身的特点，使得求出的公共子序列也有很多个。本文通过相关理论分析和实验验证了算法的正确性和可靠性[4]。

3    算法实现

3.1  数据结构选取

本文采用的数据结构为数组。二维数组C[i][j]用于判断最优解的构造顺序以及计算最优解的长度。二维数组B[i][j]用于记录最优解的构造顺序，在打印最优解时作一个索引。X[i]，Y[j]用于存储输入的两个子序列[5]。

3.2  LCS值输出函数

函数名为Print_LCS。实现方法为自底向上判断记录符号，并输出符合条件的X[i]或Y[j]，通过递归比较方便，就是通过比较两个字符串的首个字符是否一样，如过相同就将其添加。然后剔除首字符，剩下的子字符串继续进行递归匹配。如果两个字符串的首字符不同，则通过3种对齐策略分别计算可能的最长公共字串，然后取其最长的一个与当前已知的最长公共字串进行比较。如果比当前已知的最长公共字串长，就用计算值代替当前值。

通过对字符串的反复递归，对“栈”的操作经常发生访问冲突的错误，故只能用少量的数据处理，并且当数据存放到文件中时，子函数和主函数对同一文件的操作有覆盖和不显示的问题，因此，创建了两个文本文件用于对实验结果的存放。

本次设计通过动态算法解决最长公共子序列问题，对于求两个序列的一个最长公共子序列，LCSlength算法时间复杂性为0（alen*blen） ，能够得到比较理想的效果。但从另一方面看，这种算法在对C[i-1][j]与C[i][j-1]值的比较中忽略了相等时的情况，即当两个序列的最长公共子序列不一致时，不可能通过此算法求出所有的最优公共序列。

LCS算法首先规定一个或者多个字符串，然后删除多个字符或者保留全部字符，但要保证操作后不改变其他字符间的相对位置，然后计算可得到最优的公共序列。采用递推法来计算出公共长度。首先，给定任意两个字符串，不难得出，任意两个字符串的距离必然不超过它们的总长度。即使这个结论对结果没有太大帮助，但通过这至少可以知道，任意两个字符串的距离必然是有限的。需要集中考虑，如何能把这个问题进行转化，通过求解规模较小的同样的子问题来解决。

本文针对最大公共子序列进行研究，最大公共子序列在各领域也有着广泛的应用，但是在解决公共子字符串的问题上还存在不足之处，即时间复杂度长、空间复杂度高。即使降低了时间复杂度，在空间复杂度相对来说还较高，并且编程难以实现。本文研究的算法结合两者的优点，既在限制线性时间复杂度的同时，也降低了空间复杂度，而且便于编程实現。

4    结语

文中首先定义了一个指标，这个指标用来衡量字符串之间的相似度，此指标是根据字符串之间的重复率设定的，根据不同的对象，此指标不尽相同，具有很好的鲁棒性。利用此思想，能够高效找出字符串中插入的空格位置，同时，能使二者之间的相似度达到最优。

本次研究通过对字符串的反复递归，对“栈”的操作经常发生访问冲突的错误，故只能才用少量的数据处理，并且当数据存放到文件中时，子函数和主函数对同一文件的操作有覆盖和不显示的问题，因此，创建了两个文本文件用于对实验结果的存放。本文给出了算法的相关理论并通过实验验证了算法的可靠性。能有效避免重复搜索，时间效率大大提高，特别适用于基因工程中的基因片段分析，为信息检索、基因序列匹配等提供了一定的参考价值。

[参考文献]

[1]孙焘，朱晓明.基于格代数的最长公共子序列近似求解[J].计算机科学，2017（2）：270-274.

[2]朱晓明.序列的公共特征提取算法研究[D].大连：大连理工大学，2016.

[3]肖侃，谭长庚，丁玲.基于中文分词的文本相似度动态规划算法[J].现代电子技术，2011（8）：72-74，78.

[4]张毅超，车玫，马骏.求最长公共子串问题的算法分析[J].计算机仿真，2007（12）：97-100，116.

[5]郑翠玲.最长公共子序列算法的分析与实现[J].武夷学院学报，2010（2）：44-48.

Research on a common sequence with optimal similarity

Wu Mingchao1， Cui Xiaobing1， Yao Xin2， Shao Yonghui1

（1.School of Computer and Information Engineering， Henan Normal University， Xinxiang 453000， China;

2.Chengdu University， Chengdu 610000， China）

Abstract：For the multi-solution problem of the longest common subsequence of multiple sequences， in order to be able to find several sequences of strings， the largest similar sequence they share is scored according to the similarity and length in the calculation， and the output is sub- The sequences are sorted so that the positions of similar sequences and the similarity of high matches can be output. Then use two strings to slide the number of matches between the comparison and the overlap rate of the two strings when sliding， thus defining the measure of similarity， by determining that one string is less than the other. An algorithm is designed to determine the position of the inserted space in the matrix of the string matching and to maximize the similarity index. Then， by constructing an algebraic structure “grid”， the common lattice of the current lattice and the current sequence is solved by recursion can effectively avoid repeated searches， greatly improving time efficiency.

Key words：longest common subsequence; approximate algorithm; greedy algorithm