基于動態(tài)規(guī)劃的全局雙序列比對優(yōu)化算法.pdf

1、目前隨著各種基因組測序計劃陸續(xù)完成，生物序列數(shù)據(jù)急劇增長，對高敏感性和高效率的序列算法的需求日益迫切。序列比對分析是生物信息學研究中的一個重要內(nèi)容。大多數(shù)序列比對算法和軟件通常以動態(tài)規(guī)劃思想作為其空位插入的核心方法，由于計算復雜度的原因，現(xiàn)有的序列比對算法計算速度較慢，在應用上受到很大限制。雖然近年來算法得到了不斷的改進，同時隨著計算機科學的發(fā)展，計算機硬件和軟件開發(fā)技術的提高算法在執(zhí)行效率和精度得到比較大的改善，然而由于算法在計算復雜

2、度方面沒有得到明顯的改善，使得算法在執(zhí)行時對硬件要求過高。從理論基礎上改善序列比對算法，降低其空間復雜度和時間復雜度，是提高計算效率和精度的重要手段。 本論文對當前具有代表性的雙序列比對算法：Needleman-Wunsch算法、Ukkonen算法、Divide-and-Conquer算法、 Hirschberg算法進行了闡述和研究，并在深入研究Ukkonen算法的基礎上，將checkpoint技術引入到替換矩陣的計算中，提出了

3、一個基于動態(tài)規(guī)劃思想全局雙序列比對優(yōu)化算法OGPSA(Optimized Global Pairwise Sequence Alignment)。OGPSA算法以參數(shù)k為調(diào)節(jié)工具，調(diào)整不同存儲空間下的時間開銷問題，克服傳統(tǒng)算法在優(yōu)化過程中容易陷入局部極小的缺點，使算法獲得全局最優(yōu)解。 本文最后以Genbank數(shù)據(jù)庫的DNA序列和SWISS-PROT數(shù)據(jù)庫的蛋白質(zhì)序列作為測試數(shù)據(jù)，對OGPSA算法、Needleman-Wunsch