基于序列兩兩比較的進(jìn)化樹構(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)化樹。構(gòu)建進(jìn)化樹的方法主要分為三類,即距離法、簡約法和似然法。本文將對距離法做一些探索性的改進(jìn)研究。 傳統(tǒng)的距離法一般通過多序列比對計(jì)算距離矩陣,而多序列比對是一個(gè)NP難問題,在序列數(shù)目較多時(shí)難以獲得最優(yōu)比對結(jié)果。一種解決方法是采用啟發(fā)式的多序列比對算法,另一種方法是通過計(jì)算某種

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

3、存限制。Hirschberg算法具有線性空間復(fù)雜度,可以用來解決Needle-Wunschman算法的內(nèi)存問題,但是計(jì)算時(shí)間需求要多一倍,約為O(2mn)。本文試圖在時(shí)間和空間復(fù)雜度之間進(jìn)行折衷,通過引入一種新的檢查點(diǎn)(Check_Point)計(jì)算方法,提出了基于分塊遞歸的序列比對算法。理論分析表明,該算法的空間需求大約在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)之間。同源物種的線粒體全基因組序列比對實(shí)驗(yàn)進(jìn)一步證明了新算法的正確性,表明在序列之間的歸一化編輯距離小于0.25時(shí),新算法能夠比Hirschberg算法快10％以上。因此分塊遞歸序列比對算法在諸如同源序列分析、系統(tǒng)進(jìn)化樹構(gòu)造等領(lǐng)域具有一定的應(yīng)用價(jià)值。 由于直接通過序列比對得到的距離易受序列長度影響,與真實(shí)進(jìn)化距離的差別較大,因此需要進(jìn)