一種最優(yōu)相似度的公共序列研究

武明超 崔曉兵 姚欣 邵詠慧

摘? ?要：針對(duì)多條序列最長(zhǎng)公共子序列的多解問題，為了能夠求出若干條字符串序列，對(duì)它們共有的最大相似序列，在計(jì)算中按照相似度和長(zhǎng)度進(jìn)行打分，并且對(duì)輸出的子序列進(jìn)行排序，以便能夠輸出相似序列的位置并且達(dá)到最優(yōu)的相似度。根據(jù)最優(yōu)相似度確定字符串之間匹配的公共長(zhǎng)度和重復(fù)率，用比重復(fù)率作為判別相似度的一個(gè)指標(biāo)，在一個(gè)已知的字符串，通過和其他字符的比較，利用此種思想，可以找出插入在字符串中的空格位置，并能使相似度達(dá)到最優(yōu)化。通過構(gòu)建代數(shù)結(jié)構(gòu)“格”，利用遞歸求解當(dāng)前格與當(dāng)前序列的公共格。再通過動(dòng)態(tài)規(guī)劃求出最長(zhǎng)公共子序列的長(zhǎng)度數(shù)組和狀態(tài)數(shù)組，矩陣搜索求出所有有效的跳躍點(diǎn)，能有效避免重復(fù)搜索，大大提高時(shí)間效率。

關(guān)鍵詞：最長(zhǎng)公共子序列;近似算法;貪心算法

隨著科學(xué)技術(shù)的進(jìn)步，人們利用序列的相似性比較研究各個(gè)方向。例如，生物學(xué)中的親子鑒定、醫(yī)學(xué)中的診斷病基因確定疾病。隨著科學(xué)的進(jìn)步，字符串之間的相似問題也成為研究的重點(diǎn)，同時(shí)，提出了許多類似于上述的序列相似度算法。根據(jù)不同的特征，相似度的計(jì)算方法也不盡相同，主要有方面相似算法、統(tǒng)計(jì)關(guān)聯(lián)算法、相似語義算法等。有人提出結(jié)合3種算法的優(yōu)缺點(diǎn)，建立多層規(guī)劃模型。其中，相似字面主要包括距離編輯和類似的字或者詞語的計(jì)算方法。因此，此研究在各個(gè)方面都得到了廣泛的應(yīng)用。例如同分異構(gòu)的數(shù)據(jù)檢索、圖譜分析以及基因分析等。多條序列的最長(zhǎng)公共子序列可以代表多條序列的公共信息，其在諸多領(lǐng)域里有著重要的應(yīng)用，針對(duì)求解多條序列的最長(zhǎng)公共子序列式的非確定性多項(xiàng)式（Nondeterministic Polynominal，NP）（Non-deterministic Polynomial，NP）難問題，本質(zhì)為多解問題。一些近似算法雖然時(shí)間復(fù)雜度較低，但只能求出單一解，對(duì)于有多解的序列集合，求得的結(jié)果信息量損失較大。針對(duì)求解多條序列的最長(zhǎng)公共子序列式的多解問題，本文利用一個(gè)新的近似算法來解決最長(zhǎng)公共子序列問題。算法引入了稱為“格”的代數(shù)結(jié)構(gòu)，利用動(dòng)態(tài)規(guī)劃求出兩序列的公共格，并通過遞歸求得當(dāng)前格與當(dāng)前序列的公共格。求得公共格中的路徑保存了多條公共子序列，使最終求出的最長(zhǎng)公共子序列也為多個(gè)。根據(jù)最長(zhǎng)公共子序列的特點(diǎn)，利用動(dòng)態(tài)規(guī)劃法求出最長(zhǎng)公共子序列的長(zhǎng)度數(shù)組和狀態(tài)數(shù)組，并通過矩陣搜索求出所有有效的跳躍點(diǎn)，構(gòu)造求解所有最長(zhǎng)公共子序列的算法并通過程序給予實(shí)現(xiàn)。能有效避免重復(fù)搜索，時(shí)間效率大大提高，特別適用于基因工程中的基因片段分析，并通過實(shí)驗(yàn)驗(yàn)證了算法的可靠性[1]。

1? ? 算法介紹

廣義后綴樹（Generalized Suffix Tree，GST）算法思想是利用長(zhǎng)度為m的串P，利用某個(gè)函數(shù)通過計(jì)算得到每個(gè)對(duì)應(yīng)的序列值。并且把每個(gè)長(zhǎng)度為1的字符串按照一定的長(zhǎng)度進(jìn)行劃分，便可以得到一定長(zhǎng)度的子串，然后對(duì)每個(gè)子字符串利用同樣的函數(shù)計(jì)算便可以得到一個(gè)序列值。只有那些和模式串有相同序列值的子字符串才有可能和模式串匹配。如果文本子字符串中的序列值和模式串的序列值都不相同的話，那么該字符串一定不能匹配模式串。在RKRGST算法中指定一個(gè)長(zhǎng)度，這個(gè)長(zhǎng)度也可被稱為搜索長(zhǎng)度，利用這個(gè)長(zhǎng)度可以對(duì)兩個(gè)字符串同時(shí)進(jìn)行劃分，使用同一個(gè)序列，兩數(shù)分別計(jì)算出每個(gè)劃分的序列值，并且存儲(chǔ)起來，然后通過比較字符串這些序列值，凡是序列值相同的就認(rèn)為這兩個(gè)長(zhǎng)度是子字符串匹配，然后對(duì)這兩個(gè)子串后面的字符串進(jìn)行貪婪匹配，如果后面的字符依舊相同，則繼續(xù)匹配，直到兩者不能匹配為止，同時(shí)，記錄這個(gè)匹配長(zhǎng)度和分別在字符串中開始匹配的位置與字符中開始匹配的位置，首先，將這些信息儲(chǔ)存起來;然后，繼續(xù)去匹配其他長(zhǎng)度的子串，通過對(duì)每對(duì)能夠匹配的子串都進(jìn)行貪婪匹配，最后，再記錄匹配的長(zhǎng)度、開始位置等信息。如果有兩次找到的匹配的最大長(zhǎng)度是相同的，那么就將新找到的匹配信息記錄到前一個(gè)和其匹配長(zhǎng)度相同的后面，從而可以形成一個(gè)匹配鏈表[2]。

2? ? 改進(jìn)后的格算法

本文研究了一個(gè)計(jì)算最長(zhǎng)公共子序列[1]的算法，稱為格方法。該方法利用了代數(shù)結(jié)構(gòu)[2]，盡可能多地保存動(dòng)態(tài)規(guī)劃[3]信息，與傳統(tǒng)算法相比，此算法在集中的序列數(shù)量與精確度方面都有一定提升。如果節(jié)點(diǎn)數(shù)增加，會(huì)導(dǎo)致公共格中的路徑數(shù)量也會(huì)增加，進(jìn)而為找到更長(zhǎng)的公共子序列[4]提供了可能性。就算小靈通定位系統(tǒng)（Location Service Center，LSC）的長(zhǎng)度沒有變化，由計(jì)算得出的信息也使最終求出的數(shù)量增加[3]。

在很多領(lǐng)域內(nèi)，求解最長(zhǎng)公共子序列都有著重要的應(yīng)用。在求信息序列的最大子序列時(shí)，首先，提取序列的公共信息，通過進(jìn)一步檢索與分類。獲取各個(gè)基因序列間的匹配度。由于格結(jié)構(gòu)自身的特點(diǎn)，使得求出的公共子序列也有很多個(gè)。本文通過相關(guān)理論分析和實(shí)驗(yàn)驗(yàn)證了算法的正確性和可靠性[4]。

3? ? 算法實(shí)現(xiàn)

3.1? 數(shù)據(jù)結(jié)構(gòu)選取

本文采用的數(shù)據(jù)結(jié)構(gòu)為數(shù)組。二維數(shù)組C[i][j]用于判斷最優(yōu)解的構(gòu)造順序以及計(jì)算最優(yōu)解的長(zhǎng)度。二維數(shù)組B[i][j]用于記錄最優(yōu)解的構(gòu)造順序，在打印最優(yōu)解時(shí)作一個(gè)索引。X[i]，Y[j]用于存儲(chǔ)輸入的兩個(gè)子序列[5]。

3.2? LCS值輸出函數(shù)

函數(shù)名為Print_LCS。實(shí)現(xiàn)方法為自底向上判斷記錄符號(hào)，并輸出符合條件的X[i]或Y[j]，通過遞歸比較方便，就是通過比較兩個(gè)字符串的首個(gè)字符是否一樣，如過相同就將其添加。然后剔除首字符，剩下的子字符串繼續(xù)進(jìn)行遞歸匹配。如果兩個(gè)字符串的首字符不同，則通過3種對(duì)齊策略分別計(jì)算可能的最長(zhǎng)公共字串，然后取其最長(zhǎng)的一個(gè)與當(dāng)前已知的最長(zhǎng)公共字串進(jìn)行比較。如果比當(dāng)前已知的最長(zhǎng)公共字串長(zhǎng)，就用計(jì)算值代替當(dāng)前值。

通過對(duì)字符串的反復(fù)遞歸，對(duì)“棧”的操作經(jīng)常發(fā)生訪問沖突的錯(cuò)誤，故只能用少量的數(shù)據(jù)處理，并且當(dāng)數(shù)據(jù)存放到文件中時(shí)，子函數(shù)和主函數(shù)對(duì)同一文件的操作有覆蓋和不顯示的問題，因此，創(chuàng)建了兩個(gè)文本文件用于對(duì)實(shí)驗(yàn)結(jié)果的存放。

本次設(shè)計(jì)通過動(dòng)態(tài)算法解決最長(zhǎng)公共子序列問題，對(duì)于求兩個(gè)序列的一個(gè)最長(zhǎng)公共子序列，LCSlength算法時(shí)間復(fù)雜性為0（alen*blen） ，能夠得到比較理想的效果。但從另一方面看，這種算法在對(duì)C[i-1][j]與C[i][j-1]值的比較中忽略了相等時(shí)的情況，即當(dāng)兩個(gè)序列的最長(zhǎng)公共子序列不一致時(shí)，不可能通過此算法求出所有的最優(yōu)公共序列。

LCS算法首先規(guī)定一個(gè)或者多個(gè)字符串，然后刪除多個(gè)字符或者保留全部字符，但要保證操作后不改變其他字符間的相對(duì)位置，然后計(jì)算可得到最優(yōu)的公共序列。采用遞推法來計(jì)算出公共長(zhǎng)度。首先，給定任意兩個(gè)字符串，不難得出，任意兩個(gè)字符串的距離必然不超過它們的總長(zhǎng)度。即使這個(gè)結(jié)論對(duì)結(jié)果沒有太大幫助，但通過這至少可以知道，任意兩個(gè)字符串的距離必然是有限的。需要集中考慮，如何能把這個(gè)問題進(jìn)行轉(zhuǎn)化，通過求解規(guī)模較小的同樣的子問題來解決。

本文針對(duì)最大公共子序列進(jìn)行研究，最大公共子序列在各領(lǐng)域也有著廣泛的應(yīng)用，但是在解決公共子字符串的問題上還存在不足之處，即時(shí)間復(fù)雜度長(zhǎng)、空間復(fù)雜度高。即使降低了時(shí)間復(fù)雜度，在空間復(fù)雜度相對(duì)來說還較高，并且編程難以實(shí)現(xiàn)。本文研究的算法結(jié)合兩者的優(yōu)點(diǎn)，既在限制線性時(shí)間復(fù)雜度的同時(shí)，也降低了空間復(fù)雜度，而且便于編程實(shí)現(xiàn)。

4? ? 結(jié)語

文中首先定義了一個(gè)指標(biāo)，這個(gè)指標(biāo)用來衡量字符串之間的相似度，此指標(biāo)是根據(jù)字符串之間的重復(fù)率設(shè)定的，根據(jù)不同的對(duì)象，此指標(biāo)不盡相同，具有很好的魯棒性。利用此思想，能夠高效找出字符串中插入的空格位置，同時(shí)，能使二者之間的相似度達(dá)到最優(yōu)。

本次研究通過對(duì)字符串的反復(fù)遞歸，對(duì)“?！钡牟僮鹘?jīng)常發(fā)生訪問沖突的錯(cuò)誤，故只能才用少量的數(shù)據(jù)處理，并且當(dāng)數(shù)據(jù)存放到文件中時(shí)，子函數(shù)和主函數(shù)對(duì)同一文件的操作有覆蓋和不顯示的問題，因此，創(chuàng)建了兩個(gè)文本文件用于對(duì)實(shí)驗(yàn)結(jié)果的存放。本文給出了算法的相關(guān)理論并通過實(shí)驗(yàn)驗(yàn)證了算法的可靠性。能有效避免重復(fù)搜索，時(shí)間效率大大提高，特別適用于基因工程中的基因片段分析，為信息檢索、基因序列匹配等提供了一定的參考價(jià)值。

[參考文獻(xiàn)]

[1]孫燾，朱曉明.基于格代數(shù)的最長(zhǎng)公共子序列近似求解[J].計(jì)算機(jī)科學(xué)，2017（2）：270-274.

[2]朱曉明.序列的公共特征提取算法研究[D].大連：大連理工大學(xué)，2016.

[3]肖侃，譚長(zhǎng)庚，丁玲.基于中文分詞的文本相似度動(dòng)態(tài)規(guī)劃算法[J].現(xiàn)代電子技術(shù)，2011（8）：72-74，78.

[4]張毅超，車玫，馬駿.求最長(zhǎng)公共子串問題的算法分析[J].計(jì)算機(jī)仿真，2007（12）：97-100，116.

[5]鄭翠玲.最長(zhǎng)公共子序列算法的分析與實(shí)現(xiàn)[J].武夷學(xué)院學(xué)報(bào)，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