最長(zhǎng)公共子序列算法的改進(jìn)和優(yōu)化.pdf

1、一個(gè)給定字符串的子序列是在該字符串序列中刪除0個(gè)或者多個(gè)元素后得到的序列。給定序列X={x1,X2,…，Xn)和]，={y1,y2,…，yn}，設(shè)它們是定義在字符集∑={σ1,σ2,...，σs}上的兩個(gè)字符串，最長(zhǎng)公共子序列(簡(jiǎn)稱(chēng)LCS)問(wèn)題就是找出關(guān)于X和Y的公共子序列中長(zhǎng)度最長(zhǎng)的子序列。
　　 在求解LCS問(wèn)題的眾多算法中，由Rick提出的算法[15，16]有著良好的性能，該算法后來(lái)被Goeman和Clausen做了進(jìn)一步

2、的優(yōu)化和改進(jìn)[2]。改進(jìn)后算法的空間復(fù)雜度為線(xiàn)性復(fù)雜度O(ns)。然而當(dāng)該算法應(yīng)用于大規(guī)模序列(如遺傳基因序列)以及N-LCS問(wèn)題的時(shí)候，空間依然會(huì)成為算法的瓶頸。如2001年4月UCUS人類(lèi)基因組計(jì)劃發(fā)布了人類(lèi)基因序列，共包含28億對(duì)堿基，相應(yīng)的字符串序列為6G，如果用Goeman-Clausen LCS算法求解此問(wèn)題時(shí)需要96G的存儲(chǔ)空間，而96G的空間已經(jīng)超出了普通計(jì)算機(jī)的內(nèi)存空間。因此空間的優(yōu)化成了實(shí)踐中迫切需要解決的問(wèn)題。

3、r>　　 本文針對(duì)Goeman-Clausen LCS算法進(jìn)行空間改進(jìn)和優(yōu)化，做了下面幾點(diǎn)工作：(1)對(duì)Goeman-Clausen算法中的輔助數(shù)組的空間冗余進(jìn)行優(yōu)化；(2)對(duì)輔助數(shù)組利用Elias算法進(jìn)行壓縮；(3)對(duì)Elias算法做進(jìn)一步的優(yōu)化和改進(jìn)，使輔助數(shù)組的數(shù)據(jù)壓縮比進(jìn)一步提高。改進(jìn)后的算法保持了Goeman-Clausen算法的線(xiàn)性空間復(fù)雜度，但相對(duì)于原算法，空間得到了很大的節(jié)省，有效的克服了LCS算法應(yīng)用于大部分遺傳基因