最長公共子序列算法的改進和優(yōu)化.pdf

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

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

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