LZ復雜性算法及其在生物序列分析中的應用研究.pdf

1、Lempel-Ziv（LZ）復雜性是符號序列的根本屬性之一。經過適當?shù)拇至；头柣?，生物大分子（DNA、RNA、蛋白質等）也可表示成一維符號序列的形式。通過對生物序列的LZ復雜性及其它相關特性進行分析、比較，可以為解決近年來生物信息學領域許多基于序列分析的重要問題提供新的計算方法和研究途徑。 論文首先研究了LZ復雜性的概念和基本性質，在此基礎上提出符號序列最長后綴前綴（LSP）劃分的概念，證明了LSP劃分與LZ復雜性定義中完備

2、生成劃分的等價性。提出了通過非空符號序列的LSP劃分來進行LZ復雜性計算的LSP-LZC算法。采用基于帶后綴鏈接的后綴樹構造算法作為主要的計算步驟，算法LSP-LZC總的計算復雜度為線性時間和線性空間，在時間效率上優(yōu)于現(xiàn)有的LZ復雜性算法。 LZ復雜性是單個符號序列的數(shù)值屬性。為了刻畫不同序列間的LZ復雜性關系，論文提出了條件LZ復雜性的概念?；跅l件LZ復雜性，進一步提出度量序列間相似關系的LZ復雜性相似度，證明了LZ復雜性

3、相似度滿足相似性測度的正定、自反和對稱等性質。論文將LZ復雜性相似度應用于分子系統(tǒng)進化樹重構的研究中。分別以線粒體全基因組和病毒全基因組DNA序列作為計算數(shù)據(jù)，基于LZ復雜性相似度對29種有胎盤哺乳動物和SARS冠狀病毒進行系統(tǒng)進化樹的重構，都得到了具有合理生物學意義的結果。 基于LZ復雜性相似度，論文提出了相似度矩陣特征變換的概念和LZ復雜性核及核矩陣的構造方法。證明了LZ復雜性核的正定性和LZ相似關系不變性。給出了基于LZ復

4、雜性核的支持向量機模型在符號序列的模式分析中進行學習和預測的方法。利用上述方法，可以實現(xiàn)基于一級序列數(shù)據(jù)的蛋白質亞細胞位點類型的機器預測。在真實的分別由部分真核生物和原核生物組成的兩個標準數(shù)據(jù)集上進行預測實驗，都取得了良好的效果。 論文還提出了基于蛋白質接觸圖間的LZ復雜性分析進行蛋白質三維結構比較的方法。因為蛋白質的三維結構數(shù)據(jù)不能表示成符號序列的形式，論文通過計算蛋白質三維結構的接觸圖，并計算蛋白質對應接觸圖間的LZ復雜性相