結構限制下的序列比對：模型、技術與應用

Structural-Constrained Sequence Comparison: Models, Techniques and Applications

吳展碩(Chan Shuo Wu)

指導教授 ： 黃光璿

國立暨南國際大學/科技學院/資訊工程學系/博士(2009年)

https://doi.org/10.6837/NCNU.2009.00176

摘要

近年來，由於RNA基因的功能日漸受到重視，如何分析這些帶有結構資訊的基因便成了新的挑戰，而其中一個關鍵技術就在於實現符合結構意義的基因序列比對。對於這類需要考慮結構資訊的序列比對問題，本論文提出兩個數學上定義明確的計算模型，探討其計算上的特性，並發展出有效率的演算法來實現結構限制下的序列比對技術。經由實驗，我們可以看出這個演算法能產生具有生物演化意義且準確的序列比對結果。

關鍵字

結構限制下的序列比對 ； 序列比對 ； 編輯距離 ； 間缺懲罰 ； 計算生物學 ； 同源序列 ； 動態規劃 ； 演算法

並列摘要

The structural-constrained sequence comparison is an important technique for RNA gene analysis. In this thesis, we discuss this topic and propose two models. We discuss the computational properties of our models and develop an efficient algorithm to deal with RNA gene comparison problem. Experimental results in this thesis revealed that our method is more accurate and biological meaningful than several existing ones.

並列關鍵字

sequence comparison ； edit distance ； alignment ； affine-gap penalty ； computational biology ； algorithm ； homology ； dynamic programming

參考文獻

{Ak06} T. Akutsu. A relation between edit distance for ordered trees and edit distance for Euler strings. extit{Information Processing Letters}, 100:105--109, 2006.

{AGGN04} J. Alber, J. Gramm, J. Guo, and R. Niedermeier. Computing the similarity of two sequences with nested arc annotations. extit{Theoretical Computer Science}, 312:337--358, 2004.

{AS05} J. Alliali and M.-F. Sagot. A new distance for high level RNA secondary structure comparison. extit{IEEE/ACM Transactions on Computational Biology and Bioinformatics}, 2(1):4--14, 2005.

{AGMM90} S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. extit{Journal of Molecular Biology}, 215:403--410, 1990.

{AMSZ97} S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zheng, W. Miller, and D. J. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. extit{Nucleic Acids Research}, 25:3389--3402, 1997.