臺灣博碩士論文加值系統

「序列比對」在分子生物學上是一個基本而重要的應用。很多比對序列的方法已經被提出，像是二序列比對(pair-wise sequence alignment)、三序列比對、限制條件二序列比對(Constraint pair-wise sequence alignment)、多序列比對(Multiple sequence alignment) 、限制條件多序列比對(Constraint Multiple sequence alignment)…等，其中限制條件多序列比對則是將多序列比對中的基本步驟 - 二序列比對替換為限制條件二序列比對。限制條件序列比對的優點在於可以結合生物學家的專業知識以增加序列比對結果的準確性。目前限制條件多序列比對的時間複雜度已改良至O((k-1)an2)，其中k為序列數、 為限制條件的個數、 為所有限制條件的長度總和、n為序列的長度。在這篇論文中，我們將提出平行的演算法將時間複雜度進一步改良為O((k/p-1)an2)，其中p代表處理器的數量。我們並利用MPI+C語言的方式實作出來且在平行環境下進行測試，從實驗數據和分析中，可以發現我們的方法有不錯的效能，而且能使限制條件多序列比對的應用性提高不少。

Generally speaking, biologists have the knowledge of their datasets concerning the structures / functionalities / consensuses. The concept of constrained sequence alignment is proposed to incorporate the biologist's knowledge into sequence alignment such that the user-specified residues / nucleotides are aligned together in the computed alignment. Tang et al. were first to investigate constrained multiple sequence alignment problem. Their algorithm for two sequences alignment with constraints runs in time and need space. Later, this result was improved independently by two groups of researchers to time and space using the same approach of dynamic programming. Then, Chin Lung Lu designed a memory-efficient algorithm to improve the two sequence alignment with constraints by adopting the divide-and-conquer approach, this memory-efficient algorithm for solving CPSA problem can run in time and need only space, where is the sum of the length of constraints and usually in the practical applications. In this paper, we designed a parallel algorithm for the constrained multiple sequence alignment based on the memory-efficient algorithm designed by Chin Lung Lu and the progressive strategy. Then using this algorithm, we developed a parallel version tool for the constrained multiple sequence alignment.

中文摘要...................................................i
致謝辭....................................................ii
目錄 ....................................................iii
Abstract .................................................iv
1. Introduction ...........................................1
2. CMSA Algorithm .........................................4
3. Parallel Algorithm for CMSA ...........................18
4. Experimental results and analysis .....................45
5. Conclusions ...........................................55
Reference ................................................56

1: Chin Lung Lu and Yen Pin Huang. A memory-efficient algorithm for multiple sequence alignment with constraints. Bioinformatics 2005 21(1):20-30
2: Tang,C.Y., Lu,C.L., Chang,M.D.T., Tsai,Y.T., Sun,Y.J., Chao,K.M., Chang,J.M., Chiou,Y.H., Wu,C.M., Chang,H.T. and Chou,W.I. (2003) Constrained multiple sequence alignment tool development and its application to RNase family alignment. J. Bioinform. Comput. Biol., 1, 267–287.
3. P. Bonizzoni and G.D.V edova. The complexity of multiple sequence alignment with SP-score that is a metric. Theoretical Computer Science, 259:63 –79, 2001.
4. L.W ang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1:337 –348, 1994.
5. F.Co rpet. Multiple sequence alignment with hierarchical clustering. Nucleic Acids Research, 16:10881 –10890, 1988.
6. D. F.Fen g and R.F . Doolittle. Progressive sequence alignment as a prerequisite to correct phylogenetic trees. Journal of Molecular Evolution, 25:351 –360, 1987.
7. D.Hi ggins and P.S harpe. CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene, 73:237 –244, 1988.
8. W.R. Taylor. Multiple sequence alignment by a pairwise algorithm. CABIOS, 3:81 –87, 1987.
9. J. D.T hompson, D.G. Higgs, and T.J. Gibson. CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties, and weight matrix choice. Nucleic Acids Research, 22:4673 –4680, 1994.
10. H.Carrillo and D.Lipman. The multiple sequence alignment problem in biology. SIAM Journal on Applied Mathematics, 48:1073 –1082, 1988.
11. S. C. Chan, A. K. C. Wong, and D. K. Y. Chiu. A survey of multiple sequence comparison methods. Bulletin of Mathematical Biology, 54:563 –598, 1992.
12. Chin,F.Y.L., Ho,N.L., Lamy,T.W., Wong,P.W.H. and Chan,M.Y. (2003) Efficient constrained multiple sequence alignment with performance guarantee. In Proceedings of the IEEE Computer Society Bioinformatics Conference (CSB 2003). IEEE,
Los Alamitos, CA, pp. 337–346.
13. Yu,C.T. (2003) Efficient algorithms for constrained sequence alignment problems. Master’s Thesis, Department of Computer Science and Information Management, Providence University.
14. S.Needl eman and C.Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Evolution, 48:443–453, 1970.