基于字典的ＤＮＡ序列壓縮算法研究及應用
2007-01-01 00:00:00林毅申林丕源彭宏
計算機應用研究 2007年6期
摘 要：在現有DNA序列數據壓縮算法的基礎上，以DNA序列數據的存儲效率及生物學解釋綜合考慮，設計并實現了基于字典的DNA序列壓縮算法DNADCompress。算法核心包括重復子串字典建立、字典項篩選、字串壓縮編碼三方面。實驗數據表明，數據壓縮算法壓縮效果達到常用DNA序列壓縮算法水平，并為序列生物學解釋提供基礎。
關鍵詞：數據壓縮;生物信息學;DNA序列數據
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2007)06-0265-03
生物信息學是一門交叉科學，它綜合運用數學、計算機科學和生物學知識及工具來闡明和理解大量生物數據所包含的生物學意義，其研究內容包括生物信息的獲取、處理、存儲、分發、分析和解釋等在內的所有方面。在生物學中，基因是由四種不同的脫氧核糖核苷酸(腺嘌呤、鳥嘌呤、胞嘧啶和胸腺嘧啶，簡稱為A、G、C和T)按照特定的編碼規則連接而成的脫氧核糖核酸(DNA)序列。其中蘊藏著生物體中所有的結構信息和控制信息。可以說基因就是生物體內的控制中心和一本完整地講述人體構造和運轉情況的指南，通過它可以揭開有關人體生長、發育、衰老、患病和死亡的秘密。自從1990年美國啟動人類基因組計劃以來，人與模式生物基因組的測序工作進展極為迅速。截至2005年3月，僅記錄在EMBL數據庫中的DNA序列已達85 134 714 382條［1］。生物學數據的積累并不只表現在DNA序列方面，與其同步的還有蛋白質的一級結構，即氨基酸序列的增長。生物信息數據急速的積累，在人類的科學研究歷史中是空前的。海量的數據必須通過生物信息學的手段進行收集、分析和整理后，才能成為有用的信息和知識［2］。
隨著生物序列數據日益增加，數據占用的存儲空間也日益增大。如何在有限的存儲空間存儲生物序列數據成為計算機專家和生物學家面臨的新問題。以更加有效的壓縮編碼方式，用較小的存儲空間存放較大的DNA序列數據是必然的選擇。但是，由于DNA序列數據的特殊性，即DNA序列數據由A、C、G、T四個字母組成，并且DNA序列長度可達到上千萬個堿基對，使用傳統的數據壓縮算法并不理想，由此出現了多種專門針對DNA序列的壓縮方法［3－8］。但是，在現有壓縮算法中，只是單純對數據進行壓縮，并沒有考慮到序列的生物學解釋，如在構建壓縮字典時根據重復子串出現頻率分析序列數據的特征。針對這一狀況，在序列進行壓縮過程中發掘序列的生物學解釋，是本系統追求的目標，即提高序列壓縮效果，并從中發掘生物學意義。
1 DNA數據壓縮的相關工作
以色列科學家Ziv和Lempel在1977年及1978年使用字典替換的思路對數據進行壓縮，并達到良好效果［9，10］，形成了LZ系列算法。1984年，Welch實現了LZ78算法的一個變種——LZW［11］。LZW繼承了LZ77和LZ78壓縮效果好、速度快的優點，在算法描述上更容易被人們接受，實現也比較簡單。20世紀80年代中期以后，人們對LZ77進行了改進，隨之誕生了一批今天還在大量使用的壓縮程序。LZ77得以和LZ78、LZW一起壟斷當今的通用數據壓縮領域。目前，基于字典方式的壓縮已經成為一個被廣泛認可的標準。
由于DNA序列數據的特殊性，使用傳統的數據壓縮算法并不理想。1993年Grumbach S.和Tahi F.從經典的基于字典壓縮的LZ系列算法中提出BioCompress算法［4］，從搜索和編碼兩方面針對DNA序列進行改進。兩年后，Sato H.等人提出Cfect算法［5］，引入后綴樹數據結構，提高搜索重復字符串速度，并提高序列數據的壓縮率。1999年X. Chen的GenCompress算法［6］是對BioCompress算法的改進，使序列數據壓縮的壓縮速度和壓縮率提高到實用層次。2002年，X.Chen、M.Li以生物數據序列比對為基礎，提出DNACompress算法［7］，進一步提高序列數據壓縮率。2004年，臺灣大學的張均合提出DNAC算法，在重復子串方面對DNA序列壓縮率進行討論［8］。
在以上算法基礎上，筆者以字典壓縮為基礎，結合對生物數據利用思想，設計和實現了稱之為DNADCompress的DNA序列數據壓縮算法。
2 DNADCompress的設計與實現
DNADCompress算法參考了DNA序列專用壓縮算法的設計思想，如BioCompress、Cfact、GenCompress，把數據壓縮算法分為兩個步驟：重復子串字典構建和字串壓縮編碼。其中字典構建包括了重復子串字典構建和字典項篩選算法兩個步驟。在重復子串字典構建中采用重復子串搜索算法得到輸入序列重復字典；字典項篩選算法是在重復字典中按照一定策略挑選合適的子串組成新字典；字串壓縮編碼算法根據新字典對輸入串進行替換，編碼后輸出壓縮后序列，最終輸出序列壓縮文件及字典壓縮文件。整個算法結構如圖1所示。
2.1 重復子串字典構建
重復子串字典構建算法流程是：讀取未壓縮的DNA序列數據文件，在輸入序列中使用重復子串搜索算法在序列中搜索重復子串，并建立重復子串字典，在字典中包含了輸入序列中所有的重復子串。使用字典項篩選算法在重復子串字典中按照一定策略挑選重復子串，組成壓縮字典。在壓縮字典中，字典項選取的好壞，直接影響壓縮算法的壓縮效果。構建字典時所耗費的資源也直接影響整個壓縮算法的算法效率。
在重復子串字典構建中，筆者采用了速度較慢的搜索算法，但保證了能把序列中重復兩次以上子串搜索出來，算法偽代碼如下：
2.2 字符壓縮編碼
字串壓縮編碼是在已建立的壓縮字典基礎上，對輸入串s進行替換得到替換串并對此進行壓縮的編碼過程，當中涉及替換策略和壓縮編碼算法。編碼的效果直接影響壓縮效果及非解壓檢索算法的檢索速度。
在字符壓縮編碼算法中，首先按順序讀取字典D(S)中每個字典項，對于每個字典項Ek=＜Uk，rk＞（其中U是S的子串；r（r≥2）為U在S中重復出現的次數；k=1，2，…，m，m為S中重復子串的個數），在S中把Uk替換為索引k，并把Ek加入壓縮字典D—(S)中。對s重復以上過程，得到壓縮字典D—（S）和替換串S—。對得到的D—(s)和S—，使用壓縮編碼進行壓縮，最后得到壓縮字典文件及壓縮串文件。
在壓縮編碼算法中，以字節為單位進行編碼壓縮，分別把A、G、C、T記為二進制代碼00、01、10、11，針對索引項及壓縮串進行不同編碼，編碼如下：
通過字串壓縮編碼算法，使用短符號替代長字符串，并對數字索引和核苷酸字符作進一步壓縮。如圖2的例子，壓縮后節省了20個字節，因此能達到較好的壓縮效果。
3對DNADCompress的討論
DNACompress算法是現在應用較廣的一種DNA序列壓縮算法，表2是使用DNADCompress算法和DNACompress算法進行的橫向對比。
從表2可以看到，本文算法的壓縮效果取決于序列內部特征，如序列內部重復子串的長度或者重復次數。當序列的重復子串較多且重復子串長度較長時，本文壓縮算法壓縮效果遠比DNACompress算法優秀；當序列中重復子串較少或重復子串長度較短時壓縮效果較差。這是由基于字典壓縮算法的特性決定的。
總體來說，當DNA序列越長時，本文壓縮算法的壓縮效果越好；當DNA序列包含的重復字串越多且重復子串長度較長時，本文壓縮算法的壓縮效果比DNACompress算法優秀。
本文壓縮算法首先建立了重復子串字典，在重復子串字典中針對序列特征進行搜索，總結出序列的特征，生物學家可以根據這些序列特征進行進一步研究，如分析不同序列間的微衛星結構、啟動子、轉錄子等結構。與DNACompress等傳統基于字典的壓縮算法相比，本文所提出的算法不僅考慮數據壓縮效果，而且兼顧了對生物數據的進一步使用。這是本文提出的算法與傳統壓縮算法相比的優勝之處。
本文提出的壓縮算法可作為生物信息學的基礎算法，在此基礎上可構建各種生物信息學系統，達到節省序列數據存儲空間及挖掘序列數據生物意義的目的。例如，使用本算法對Bioperl生物信息學軟件包［12］進行改進，構建二次數據庫的基本結構和基本接口，以及使用Bioperl核心模塊構建生物信息系統的基本環境，二者可以組成一個完整的生物二次數據庫及生物信息研究平臺［13］。
4 結束語
本文在傳統字典壓縮算法技術基礎上，考慮對DNA序列數據生物學解釋及進一步應用，搭建了基于字典的DNA序列數據壓縮算法架構。實驗數據表明，本算法數據壓縮部分壓縮效果達到了常用DNA序列壓縮算法水平。本算法考慮到序列生物學解釋，生物學家可以根據壓縮算法得到的序列特征數據對序列作進一步生物學解釋，這是本算法創新之處。
進一步的工作是，運用生物學知識構建具有生物信息學知識的字典，進一步提高數據壓縮率和降低重復序列搜索時間。利用重復子串字典數據，尋找序列的生物特性，使用人工智能方法對序列特征進行分析。對算法作進一步完善，在本算法基礎上設計非解壓檢索算法。更進一步工作是把算法推廣到普通文本數據上，這在實際應用中有重要意義。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
