改進最佳成對序列比對之修剪演算法

An Improved Pruning Algorithm for Optimal Pairwise Sequence Alignment

吳柏鋒(Po-Feng Wu)

指導教授 ： 劉如生

元智大學/資訊學院/資訊工程學系/碩士(2004年)

摘要

在生物資訊學的領域內，序列比對的問題一直廣受大家的重視。基本上，針對生物序列進行的許多相關研究，例如：尋找基因位置、建立物種親緣關係、蛋白質結構預測……等，這些問題都必須建立在序列比對的基礎上，因此發展良好的序列比對演算法是一項十分重要的課題。
在求最佳解的比對方式中，動態規劃是較常用的演算法，但是其最大的缺點是運算時間過長。本篇論文提出許多的調整與改進方式，包括間隔處罰以及運算的順序，利用BLAST演算法改進下限的尋找……等。依模擬結果，我們的改進修剪演算法相較於Needleman的演算法，平均可以節省約 30% 的時間。因此，本演算法對於求最佳成對序列比對的問題，獲得相當不錯的改進結果。

關鍵字

序列比對 ； 動態規劃 ； BLAST演算法

並列摘要

In the bioinformatics research area, the sequence alignment is a fundamental and well-known problem. Basically, many related works about biology sequence, such as finding gene position, building phylogeny of species, protein structure prediction, and so on, are based on the sequence alignment. Therefore, developing a good sequence alignment algorithm becomes an important issue.
To obtain an optimal solution of sequence alignment, the dynamic programming method is often to be adopted. However, the major drawback for dynamic programming algorithm is that it takes too much computing time. In this thesis, we propose several modifying and improving strategies including affine gap penalty, changing the computing progress, utilizing BLAST algorithm to improve the lower bound value, and so on. From the simulation, it shows that comparing with Needleman algorithm, our improved pruning algorithm may save 30% computing time. Therefore, our algorithm has a marvelous improvement to find the optimal solution of pairwise sequence alignment.

並列關鍵字

sequence alignment ； dynamic programming ； BLAST

參考文獻

[1] Altschul,S.F., et al, “Basic local alignment search tool”, J. Mol. Biol, 215, 1990, pp.403-410.

[2] Arslan,A.N., Egecioglu,O., and Pevzner,P.A.,“A new approach to sequence comparison: normalized sequence alignment”, Bioinformatics, 17, 2001, pp.327-337.

[3] Bray,N., Dubchak,I., and Pachter,L.,“AVID: A Global Alignment Program”, Genome Res., 13, 2003, pp.97-102.

[4] Brudno,M., et al.,“Automatic Whole-Genome Multiple Alignment of Rat, Mouse, and Human”, Genome Res., 14, 2004, pp.685-692.

[5] Brudno,M., et al.,“Glocal alignment: finding rearrangements during alignment”, Bioinformatics, 19, 2003, pp.i54-i62.