生物信息學中的序列相似性比對算法.pdf

1、序列相似性比對是生物信息學中基本的信息處理方法，它對于發(fā)現(xiàn)生物序列中的功能、結構和進化的信息具有非常重要的意義。主要思想就是運用某種特定的數學模型或算法，找出兩個或多個序列之間的最大匹配堿基或殘基數，比對的結果反映了算法在多大程度上反映了序列之間的相似性關系以及它們的生物學特征。因此，生物信息學中分析的序列相似性比對的簡單有效算法一直是生物學家關心的問題，序列比對也是計算生物學中解決象序列裝配，進化樹重構及基因組分析等眾多問題的第一步。

2、進行序列相似性比對的算法很多，而這些算法大多數都是基于動態(tài)規(guī)劃算法，只是在其基礎上進行了不同程度的改進而已。根據同時比對的序列數目的不同，將序列相似性比對算法分成雙序列相似性比對算法和多序列相似性比對算法。 本文在第二章前三節(jié)詳細地介紹了這些基于動態(tài)規(guī)劃算法的序列相似性比對算法。所有這些算法有個共同的特點：算法是字符串比較算法，序列的比較是字符上的比較，它們的差異性體現(xiàn)在彼此間存在不同的子序列或子結構，而相似性體現(xiàn)在它們有共同

3、的子序列或子結構，因此我們很自然的會想到尋找生物序列的最長公共子序列，這就是所謂的LCS問題。近兩年國內外一些學者給出了DNA序列的圖形表示，用幾何的方法比較生物序列，這些理論已經基本成熟。我們在第四節(jié)介紹了DNA序列圖形表示的相關理論并給出了一種基于二維圖形表示的尋找生物序列和生物結構的最長公共子序列的算法，該算法簡單并可視化。很適合用于生物序列的比較和分析。在第三章給出了用于尋找mRNA序列和蛋白序列的最優(yōu)局部對比和全局對比的對比算