雙序列比對算法的研究與改進(jìn)

李丹

摘要

隨著生物信息學(xué)的飛速發(fā)展，生物數(shù)據(jù)海量激增，序列比對作為生物學(xué)的計算核心，在其精確性和敏捷性方面都提出了更高的要求。在研究傳統(tǒng)序列比對算法的基礎(chǔ)上，本文提出一種改進(jìn)的基于動態(tài)規(guī)劃的全局雙序列比對算法，有效降低了時間復(fù)雜度和空間復(fù)雜度。

【關(guān)鍵詞】生物信息學(xué)雙序列比對 動態(tài)規(guī)劃

1引言

生物信息學(xué)（Bioinformatics）是生物學(xué)與計算機科學(xué)及應(yīng)用數(shù)學(xué)等學(xué)科相互交叉形成的一門新學(xué)科，它通過對生物學(xué)實驗數(shù)據(jù)的獲取、加工、存儲、檢索與分析，揭示這些資料所蘊含的生物學(xué)意義。序列比對是生物學(xué)計算的核心，是生物學(xué)中最基本、最重要的方法。序列比對又叫序列聯(lián)配，提供了一個有力的途徑來試圖提示兩個序列之間是否具有足夠的相似性（Similarity）。最常見的比對是蛋白質(zhì)序列之間或核酸序列之間的兩兩比對，通過比較兩個序列之間的相似性區(qū)域，尋找二者可能的分子進(jìn)化關(guān)系。

序列比對的分類，從同時進(jìn)行比對的序列個數(shù)方面，分為雙序列比對（Pair-wise Sequence Alignment）和多序列比對（Multiple Sequence Alinment）；從比對范圍考慮可分為全局比對Global Alignment）和局部比對（Local Alignment）。

2動態(tài)規(guī)劃思想

動態(tài)規(guī)劃（Dynamic Programming）是運籌學(xué)的一個分支，是求解決策過程（Decision Process）最優(yōu)化的數(shù)學(xué)方法。把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法。基于動態(tài)規(guī)劃的全局雙序列比對算法思想：首先，計算兩個序列的相似分值，存入一個得分矩陣中，運用迭代法；其次，尋找最優(yōu)比對序列，運用回溯法。

3一種改進(jìn)的基于動態(tài)規(guī)劃的全局雙序列比對算法

算法改進(jìn)之處，在得分矩陣的計算過程中只存儲前一行和當(dāng)前行，并記錄得分值的來源。優(yōu)點是節(jié)省存儲空間，由改進(jìn)前的O（nxn），降為O（n），且在得分矩陣計算過程中同時記錄元素的來源，最佳比對路徑的獲得不需要回溯。

4結(jié)論

隨著生物學(xué)數(shù)據(jù)的海量增加，對序列比對算法的空間性和時間性提出更高的要求，如何二者兼得，將成為生物信息學(xué)中一個非常重要且具有挑戰(zhàn)性的研究課題。本文提出一種改進(jìn)的基于動態(tài)規(guī)劃的全局雙序列比對算法，在存儲空間和運算速度兩方面均有質(zhì)的提高。隨著研究的深入，如何建立合理的相似性度量準(zhǔn)則，如何提高準(zhǔn)確率和運算速度，新的序列比對算法必將不斷增加。

參考文獻(xiàn)

[1]羅超權(quán)，余新炳，昌才.英漢生物化學(xué)與分子醫(yī)學(xué)詞典[M].北京：中國醫(yī)藥科技出版社，2005.

[2]李鎳嵐，李其申，張永.一種基于動態(tài)規(guī)劃的全局雙序列比對優(yōu)化算法[J].電腦知識與技術(shù)（學(xué)術(shù)交流），2007，1（06）：124-126.

[3]T.K.Attwood，D.J.Parry-Smith.生物信息學(xué)概論[M].羅靜初譯.北京：北京大學(xué)出版社，1999.

[4]Bel1man R，Ka1aba R.Dynamic Programming and Statistical Communication Theory[J].Proceedings of the National Academy of Sciences of the United States of America，1957，43（08）：749.endprint