臺灣博碩士論文加值系統

多重序列排對問題在計算分子生物學上是一個相當基礎的問題，我們已經知道這是一個NP-hard 的問題．要找到這個問題的最佳解會花費相當多的時間．為了可以得到不錯且花費時間少的解法，學者們發展出一些漸次性的解法．這些漸次性的方法會先將一雙雙的序列排對好，再將這些成雙的序列合併．
在這片論文中，我們將著重在解決群聚的多重序列排對上．我們試著從不同的觀點來面對序列排對問題．我們使用矩陣來表示序列．當兩個序列排對好後，它的結果依然可以使用矩陣來呈現，也就是說我們可以將這些排對好的序列想像成以矩陣表示的區塊．這與之前的漸次性方法是不太一樣的．漸次性方法每次總是考慮兩個序列在排對，而我們的方法可以考慮兩群序列的排對．
在這篇論文的最後，我們做了一些實驗比較區塊排對與一些漸次性解法的差異．我們可以發現區塊排隊在群聚的多重序列排對上取得了相當的優勢．

Multiple sequence alignment is a fundamental problem in computational molecular biology. It has been known as an NP-hard problem. To find its optimal solution will take a lot of time. For a reasonable wait and an acceptable solution, we have progressive methods. These methods perform pairwise alignment, and then combine them in to a multiple sequence alignment.
In this thesis, we focus on multiple sequence alignment containing clusters. We try to take another view point to deal with sequence alignment. We use a matrix to present a sequence. Every sequence will be represented as a matrix. After two sequences (matrices) are aligned, the result of the alignment will again be represented by a matrix and then the original two sequences (matrices) will be discarded. That is, the result of aligning a set of sequences will always be considered as a block and represented by a matrix. This is thus different from the old ways in which only two sequences are aligned, not a group of aligned sequences and another group of aligned sequences.
In this thesis, we will show some experimental results to test our proposed method. Block alignment outperforms those progressive methods for sequences containing clusters.

Abstract I
摘要 II
Dedication III
Acknowledgement IV
Chapter 1 Introduction 1
Chapter 2 Dynamic Programming on Alignment 3
2.1 Pairwise Alignment 3
2.2 Multiple Sequence Alignment 6
Chapter 3 Progressive Methods 10
3.1 The Algorithm Proposed 2-Approximation by Gulsfield 11
3.2 Minimal Spanning Tree Strategy 14
Chapter 4 Block Alignment 18
4.1 Data Structure 18
4.2 Score Function 21
4.3 The Recurrence 26
4.4 The Algorithm Based upon the Block Alignment 30
Chapter 5 Experimental Results 37
5.1 2-cluster 37
5.2 3-cluster 39
5.3 2-cluster of Real Data 41
Chapter 6 43
Conclusion 43
Bibliography 44

[AL89] Trees, Stars and Multiple Biological Sequence Alignment, Altschul, S. F. and Lipman, D. J., SIAM Journal on Applied Mathematics, Vol. 49, 1989, pp. 197-209.
[BLP94] Approximation Algorithms for Multiple Sequence Alignment, Bafna, V., Lawler, E. L. and Pevzner, P., Proc. of the 5th Annual Symp. on Combin. Pattern Matching(CPM''94). Lecture Notes in Computer Science, Vol. 807, 1974, pp. 43-53 .
[BLP97] Approximation Algorithms for Multiple Sequence Alignment, Bafna, V., Lawler, E. and Pevzner, P., Theoretical Computer Science, Vol. 182, 1997, pp. 233-244.
[CL88] The Multiple Sequence Alignment Problem in Biology, Carrillo, H. and Lipman, D., SIAM Journal on Applied Mathematics, Vol. 48, No. 5, 1988, pp. 1073-1082.
[CWC92] A Survey of Multiple Sequence Comparison Methods, Chan, S. C., Wong, A. K. C. and Chiu, D. K. Y., Bulletin of Mathematical Biology, Vol. 54, No. 4, 1992, pp. 563-598 .
[FD87] Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees, Feng, D. and Doolittle, R., Journal of Molecular Evolution, Vol. 25, 1987, pp. 351-360.
[G91] Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds, Gusfield, D., Tech. Report; Computer Science Division; University of California; Davis; CSE-91-4, 1991.
[LAK89] A Tool for Multiple Sequence Alignment, Lipman, D. J., Altschul, S. F. and Kececioglu, J. D., Proc. Nat. Acad. Sci., Vol. 86, 1989, pp. 4412-4415.
[LCTT2002] Introduction to the Design and Analysis of Algorithms, Lee, R. C. T., Chang, R. C., Tseng, S. S. and Tsai, Y. T., Flag Press, 2002.
[P2000] Computational Molecular Biology: An Algorithmic Approach, Pevzner, P. A., MIT Press, 2000.
[S75] Minimal Mutation Trees of Sequences, Snakoff, D., SIAM Journal on Applied Mathematics, Vol. 28, 1975, pp. 35-42.
[S85] Simultaneous Solution of the RNA Folding, Alignment and Protoseqeunce Problem, Sankoff, D., SIAM Journal of Applied Mathematics, Vol. 45, 1985, pp. 810-825.
[W95] Introduction to Computational Biology, Waterman, M. S., London: Chapman & Hall, 1995.
[WSB76] Some Biological Sequence Metrics, Waterman, M. S., Smith, T. F. and Beyer, W. A., Advances in Applied Mathematics, Vol. 20 , 1976, pp. 367-378.