基于序列兩兩比較的進(jìn)化樹(shù)構(gòu)造方法研究.pdf

1、系統(tǒng)進(jìn)化分析是生物信息學(xué)中的重要研究領(lǐng)域,它的主要研究手段是從一組同源的DNA或蛋白質(zhì)序列出發(fā),計(jì)算各個(gè)序列之間的進(jìn)化距離,進(jìn)而構(gòu)建反映物種進(jìn)化關(guān)系的進(jìn)化樹(shù)。構(gòu)建進(jìn)化樹(shù)的方法主要分為三類,即距離法、簡(jiǎn)約法和似然法。本文將對(duì)距離法做一些探索性的改進(jìn)研究。 傳統(tǒng)的距離法一般通過(guò)多序列比對(duì)計(jì)算距離矩陣,而多序列比對(duì)是一個(gè)NP難問(wèn)題,在序列數(shù)目較多時(shí)難以獲得最優(yōu)比對(duì)結(jié)果。一種解決方法是采用啟發(fā)式的多序列比對(duì)算法,另一種方法是通過(guò)計(jì)算某種

2、序列之間的兩兩距離代替多序列比對(duì)。對(duì)于計(jì)算兩兩距離的方法而言,Hansan H.Out和Khalid Sayood提出了一種基于LZ復(fù)雜度的距離,能夠正確地重構(gòu)某些進(jìn)化樹(shù)。本文則試圖通過(guò)利用一種滿足三角不等式的歸一化編輯距離來(lái)繞過(guò)多序列比對(duì)的困難,但仍然需要對(duì)序列進(jìn)行兩兩比對(duì)分析。 序列的兩兩比對(duì)通常采用Needle-Wunschman算法,其時(shí)間和空間復(fù)雜度均為O(mn)(m,n為比對(duì)兩序列的長(zhǎng)度),對(duì)長(zhǎng)序列容易超過(guò)計(jì)算機(jī)的內(nèi)

3、存限制。Hirschberg算法具有線性空間復(fù)雜度,可以用來(lái)解決Needle-Wunschman算法的內(nèi)存問(wèn)題,但是計(jì)算時(shí)間需求要多一倍,約為O(2mn)。本文試圖在時(shí)間和空間復(fù)雜度之間進(jìn)行折衷,通過(guò)引入一種新的檢查點(diǎn)(Check_Point)計(jì)算方法,提出了基于分塊遞歸的序列比對(duì)算法。理論分析表明,該算法的空間需求大約在O(5(m+n)+Ls×min(m-1,n-1)+C2)至O(5(m+n)+Ls×(m+n-2)+C2)之間,時(shí)間需

4、求介于O(1.5mn)到O(3mn)之間,但在序列相似度較高時(shí)介于O(1.5mn)到O(2mn)之間。同源物種的線粒體全基因組序列比對(duì)實(shí)驗(yàn)進(jìn)一步證明了新算法的正確性,表明在序列之間的歸一化編輯距離小于0.25時(shí),新算法能夠比Hirschberg算法快10％以上。因此分塊遞歸序列比對(duì)算法在諸如同源序列分析、系統(tǒng)進(jìn)化樹(shù)構(gòu)造等領(lǐng)域具有一定的應(yīng)用價(jià)值。 由于直接通過(guò)序列比對(duì)得到的距離易受序列長(zhǎng)度影響,與真實(shí)進(jìn)化距離的差別較大,因此需要進(jìn)