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

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

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

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