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

李丹

摘要

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

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

1引言

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

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)

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

[2]李鎳嵐，李其申，張永.一種基于動(dòng)態(tài)規(guī)劃的全局雙序列比對(duì)優(yōu)化算法[J].電腦知識(shí)與技術(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