臺灣博碩士論文加值系統

多重序列排比在生物序列的分析上是一個重要的工具，應用的範圍從搜尋資料庫中相似的序列到蛋白質結構預測都是應用的範圍。處理多重序列排比問題時，以動態程式規劃可以求得最佳解的排比不一定為生物上的最佳解，而且隨著序列數目的增加使得動態程式規劃顯得不切實際。另一種較快速的方法為漸進似演算法，將相似度最高的兩條序列先行合併再依相似度的高低一一合併，但合併的順序產生不同的排比結果。
由於最佳解並非生物上的最佳排比，以串接次佳解的方式有機會找到更接近的解，這樣也能降低時間複雜度。另外一方面本演算法會串接所有合併方式，對漸進似演算法而言多花一些時間就有找到更好排比的可能性。

Multiple sequence alignment is an important tool to analysis biological sequence from searching similar sequence in database to protein structure. The optimal solution of dynamic programming is not always real biological solution when the number of sequence is increasing. Another method is progressive algorithm, it combined most similar sequence and then added next similar sequence. But the order of combining sequence have different alignment.
Due to the optimal alignment is not always the best alignment in biological alignment, combining the pairwise suboptimal alignment have the possibility to find a better solution. The method also can decrease the time complexity. On the other hand, there is a possibility to find better alignment when we take a few time to try all combination.

1-1動機與目的…………………………………………………………1
1-2研究方法……………………………………………………………2
1-3研究架構……………………………………………………………3
2-1序列排比結果的介紹與評估………………………………………4
2-2動態程式規劃(Dynamic Programming)………………………6
2-3漸進似排比演算法(以ClustalW演算法說明)…………………9
2-4現有序列排比演算法的分類……………………………………12
3-1系統流程圖………………………………………………………16
3-2產生次佳解排比…………………………………………………17
3-3結合次佳解排比…………………………………………………18
3-4分差的範圍及限制………………………………………………19
4-1實驗結果一(固定分差範圍)……………………………………22
4-2實驗結果二(增加分差範圍)……………………………………23
結論.............................................32

[1] O. Gotoh. An improved algorithm for matching biological sequences. Journal of molecular Biology, 162:705-708, 1989. [2] M.S. Waterman. General methods of sequence comparison. Bulletin of Mathematical Biology, 46:473-500, 1984. [3] D. Sankoff. Matching sequence under deletion-insertion constraints. In proceedings of the National Academy of Science U.S.A, volume 64, pages 4-6, Washington, DC, 1972. Academy. [4] Joao Setubal and Joao Meidanis. Sequence comparison and database search. In Introduction To Computational Molecular Biology, pages 47-103. PWS, 1997. [5] Bashford, D., Chothia, C. and Lesk, A.M J.Mol. Biol. 196, 199-216, 1987. [6] Saitou, N. and Nei, M. Mol. Biol. Evol. 4, 406-425, 1987. [7] Thompson, J.D., Higgins, D.G. and Gibson, T.J CABIOS 10, 19-29, 1994. [8] C.Notredame, Recent progress in multiple sequence alignment: a survey Ashley Publications Ltd, 2001. [9] D.J. Lipman, S.F. Altschul, J.D. Kececioglu, A tool for multiple sequence alignment. Proc. Natl. Acad. Sci. pp.4412-4415, 1989. [10]J. Stoye, Multiple sequemce alignment with the divide-and-conquer method, Gene, vol. 211, no. 2,pp.45-56,1998. [11]J.D. Thompson, D.G. Higgins, T.J. Gibson, CLUSTALW: improving sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acid Res.,pp.4673-4680, 1994. [12]Hogeweg P, Hesper B: The aligement of sets of sequences and the construction of phylogenetic tree. An integrated method. J. Mol. Evol. 20,175-186, 1984. [13]Feng D-F,Doolittle RF: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol.25, 351-360, 1987. [14]Taylor WR: A flexible method to align large numbers of biological sequences. J. Mol. Evol. 28, 161-169, 1998. [15]Devereux J, Haeberli P, Smithies O: GCG package. Nucleic Acids Res. 12, 387-395, 1984. [16]Corpet F: Multiple sequence alignment with hierarchical clustering. Nucleic Acids Res.16, 10881-10890, 1988. [17]C. Notredame, D.G. Higgins, J Heringa , T-Coffee: A novel method for fast and accurate multiple sequence alignment, J. Mol. Biol, 2000. [18]T Shibuya, H Imai, Enumerating suboptimal alignments of multiple biological sequences efficiently, Proc. 2nd Pacific Symp. Biocomputing, 1997. [19]D. Eppstein, Proc. IEEE Founction of Computer Science, 35: pp.154-165,
1994. [20]T.Ikeda, and H. Imai, Proc. Genome Informatics Workshop V, pp.90-99, 1994. [21]J.D. Thompson, F Plewniak, O Poch, Bioinformatics, BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs, Nucleic Acids Res. 1999, 27(13), 2682-90 , 1999.