序列比對優(yōu)化算法研究.pdf

1、序列比對是整個生物信息學(xué)中重要的組成部分，是從生物分子序列中進行信息分析與挖掘的基礎(chǔ)。通過序列比對人們可以從DNA序列中推斷出蛋白質(zhì)分子的結(jié)構(gòu)；通過序列比對人們可以從基因數(shù)據(jù)庫中搜索查找新的序列；通過序列比對人們可以分析生物進化以及推斷生物分子的結(jié)構(gòu)與功能信息。 本文首先介紹了分子生物學(xué)背景知識，對生物序列比對技術(shù)的各個方面進行了介紹，包括序列比對的基本原理、全局比對、局部比對、雙序列比對和多序列比對。其中研究了幾種用于序列比對

2、的軟件系統(tǒng)。FASTA搜索和BLAST搜索用于雙序列比對，能夠在數(shù)據(jù)庫中找出與新序列相關(guān)的已知序列。ClustalW程序用于多序列比對，它是目前比較好的一種多序列比對軟件。 在對多序列比對的研究中，主要是基于漸進算法的全局多序列比對算法的分析和實現(xiàn)。闡述了漸進比對算法的原理，算法用到了許多基本算法，主要是動態(tài)規(guī)劃算法和Needleman—Wunsch算法，討論了系統(tǒng)發(fā)生樹的構(gòu)建以及鄰近歸并算法。分析了空位罰分和打分矩陣對比對的影

3、響．在此基礎(chǔ)上，用面向?qū)ο蟮姆椒ㄔO(shè)計了漸進算法的全局多序列比對軟件系統(tǒng)，文章給出了設(shè)計思想和UML活動圖、UML類圖。在JBuilderX開發(fā)平臺上實現(xiàn)了軟件系統(tǒng)，并給出了JBuilderX根據(jù)代碼自動生成的UML類圖。對于測試結(jié)果按組進行分析。 在漸進算法的基礎(chǔ)上，本文提出可以使用迭代算法對全局多序列比對軟件系統(tǒng)進行改進，文章給出了改進的方法和具體設(shè)計。最后，使用BAliBASE數(shù)據(jù)庫中142個文件進行測試，給出了測試用例。并