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

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

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

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

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