雙序列比對算法的研究與改進

李丹

摘要

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

【關鍵詞】生物信息學雙序列比對 動態規劃

1引言

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

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

2動態規劃思想

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

3一種改進的基于動態規劃的全局雙序列比對算法

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

4結論

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

參考文獻

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

[2]李鎳嵐，李其申，張永.一種基于動態規劃的全局雙序列比對優化算法[J].電腦知識與技術（學術交流），2007，1（06）：124-126.

[3]T.K.Attwood，D.J.Parry-Smith.生物信息學概論[M].羅靜初譯.北京：北京大學出版社，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