LZ復(fù)雜性算法及其在生物序列分析中的應(yīng)用研究.pdf

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

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

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

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