臺灣博碩士論文加值系統

同時排比多條核苷酸或胺基酸序列是分子生物領域分析序列時不可獲缺的工具之一。藉由多重序列排比可以：尋找描繪蛋白質家族內的特徵區域；檢驗或證明新序列和已存在的序列家族是否具有同源性；協助預測新序列的二級或三級結構；做為演化分析的前奏。
礙於多維度動態規劃法所需大量的計算時間和貯存空間使得多重序列排比變得窒礙難行。目前所被提出的方法都只是基於經驗法則，並不能確保所得的結果具被有任何生物意義。然而評估多重排比優劣乃根據具有演化性質的計分策略和缺口罰分，因此利用演化樹來指引多重序列排比是有根據和必要的。
本篇論文主要介紹如何以簡約的原則同時重建演化樹和進行多重序列排比，這個構想首先由sankoff在1973年所提出。在1989年Hein進一步利用序列圖結合動態規劃法提出可行的演算法TREEALIGN。我們改變Hein演算法中指引樹建立的方式，根據序列兩兩的編輯距離以互鄰合併法建立指引樹，用來指引運算順序，並使用三種改變樹型態的經驗法則，期待能同時建立符合最簡約原則的演化樹和多重排比。

Simultaneous alignment of numerous nucleotide or amino acid sequence is a necessary tool when analyzing the structure of the sequences in the field of molecular biology. Multiple sequence alignment can be used to search for and depict the conserved domain in the protein family, examine and prove if there is any homogeneity between the new sequence and the existed protein family, to help predict the secondary or tertiary structures of new sequence, and to serve as the first step in molecular evolutionary analysis.
The problems of large amounts of calculated time and space needed in the multidimensional dynamic programming make the multiple sequence alignment difficult to perform. The practical methods presented so far are just heuristic, and they can’t be assured that the results have any biological meaning. However, evaluating the multiple sequence alignment always depends on scoring scheme and gap penalty which reflect the evolutionary relation. Therefore, the use of phylogenetic trees to guide multiple sequence alignment captures the evolutionary relation is an essential way.
This thesis discusses the simultaneous construct of phylogenetic tree and multiple sequence alignment based on the principle of parsimony. This idea was first put forward by Sankoff in 1973. In 1989, Hein presented the feasible algorithm by further using sequence graph combined with dynamic programming. We modified the methods that Hein constructed his guide tree in the algorithm. According to the edit distances for every pair of sequences, we build the guide tree by neighboring joining method and apply it to guide the order of alignment. Also, we use three kinds of perturbation of tree topology to reconstruct the phylogenetic tree and multiple alignments according to the principle of parsimony.

第一章、序論
第二章、序列排比
第一節、序列排比簡介
第二節、胺基酸置換矩陣
一、PAM矩陣
二、BLOSUM矩陣
第三節、序列全域排比
第四節、序列局部排比
第五節、多重序列排比
第六節、多維度動態規劃法
第三章 演化樹
第一節、何謂演化樹
第二節、重建演化樹
第三節、距離法
第四節、最簡約法
第五節、編輯距離
第四章 以演化樹指引多重排比
第一節、樹狀排比
第二節、以距離法建立演化樹指引漸進式排比
第三節、以簡約法建立演化樹指引樹狀排比
第四節、問題與討論
一、局部最佳解非全域最佳解
二、序列圖近年來的其它應用
參考文獻

[1] Altschul, S. F., Gish, W., Miller, W., Myers, E. W., and Lipman, D. J., 1990. Basic Local Alignment Search Tool. Journal of Molecular Biology, 215:403-410.

[2] Dayhoff, M. O., Schwartz, R. M. and Orcutt, B. C., 1978. A model of evolutionary change in proteins. Atlas of Protein Sequence and Structure, vol. 5, suppl. 3, pp.345-352.

[3] Dayhoff, M. O. and Schwartz, R. M., 1978. Matrices for detecting distant relationships. Atlas of Protein Sequence and Structure, vol. 5, suppl. 3, pp.353-358.

[4] Feng, D. F. and Doolittle, R. F., 1987. Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees. J. Mol. Evol. 25, 351-360.

[5] Fitch, W. M., 1971. Toward defining the course of evolution: minimum change for a specified tree topology. Sys. Zool, 20:406-416.

[6] Gotoh, O. An improved algorithm for matching biological sequence. Journal of Molecular Biology, 162:705-708.

[7] Gupta, S. K., Kececioglu J. D., and Schaffer A. A., 1995. Improving the practical space and time efficiency of the shortest-paths approach to sum -of-pairs multiple sequence alignment. J. Comput. Biol, 2:459-472.

[8] Hartigan, J. A., 1973. Minimum mutation fits to a given tree. Biometrics, 29:53-65.

[9] Hein, J., 1989. A new method that simultaneously aligns and reconstructs ancestral sequence for any number of homologous sequence, when the phylogeny is given. Molecular Biology and Evolution, 6(6):649-668.

[10] Hein, J., 1989. A tree reconstruction method that is economical in the number of pairwise comparisons used. Molecular Biology and Evolution, 6(6):669-684.

[11] Hein, J., 1990. Unified approach to alignment and phylogenies. Methods in Enzymology, 188:626-645.

[12] Hein, J., 1994. Treealign, In: Griffin, A. M. Griffin, H. G. (Eds.), Computer analysis of sequence data, Part II, Methods in Molecular Biology, Vol 25, Iquman Press, Totowa, USA, Chapter 28, pp. 349- 364.

[13] Henikoff, S. and Henikoff, J. G., 1982. Amino acid substitution matrices from Protein blocks. Proc. Natl. Acad. Sci, USA 89:10915-10919.

[14] Henikoff, S. and Henikoff, J. G., 1991. Blocks database and its applications. Nucleic. Acids. Res., 19:6565-6572.

[15] Henikoff, S. and Henikoff, J. G., 1991. Automated assembly of protein blocks for database searching. Nucleic. Acids. Res, 19:6565-6572.

[16] Jiang, T., Lawler, E. L., and Wang, L., 1994. Aligning sequences via an evolutionary tree: Complexity and approximation(extended abstract). In: Proceeding of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 760-769, Montreal, Quebec, Canada.

[17] Lee, C., Grasso, C. and Sharlow, M. F., 2002. Multiple sequence. alignment using partial order graphs. Bioinformatics, 18(3):452-64

[18] Levenshtein, V. I., 1966. Binary codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 10:707-710

[19] Lipman, D. J. and Pearson, W. R., 1985. Rapid and sensitive protein similarity searches. Science, 227:1435-1441.

[20] Lipman, D. J. and Pearson, W. R., 1988. Improved tools for biological sequence comparison. Proc. Natl. Academy Science, 85:2444-2448.

[21] Lipman, D. J., Altschul, S. F. and Kececioglu, J. D., 1989. A tool for multiple sequence alignment. Proc. Natl. Academy Science, 86: 4412 -4415.

[22] Needleman, S. B. and Wunsch, C. D., 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48:443-453

[23] Pearson, W. R., 1995. Comparison of methods for searching protein sequence databases. Protein Science, 4:1145-1160.

[24] Raphael, B., Zhi, D., Tang, H. and Pevzner, P., 2004. A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res. 14, 2336-2346.

[25] Saitou, N. and Nei, M., 1987. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution, 4:406-425.

[26] Sankoff, D., 1975. Minimal mutation tree of sequence. SIAM. Appl. Math., 28:35-42

[27] Sankoff, D. and Cedergren, R. J., 1983. Simultaneous comparison of three or more sequences related by a tree. In Sankoff, D. and Kruskal, J. B., eds., Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison. Addison-Wesley. Chapter 9, pp.253-264.

[28] Sankoff, D. and Kruskal, J., 1983. Time warps, string edits and macromolecules: the theory and practice of sequence comparison. Addison-Wesley.

[29] Schwikowski, B. and Vingron, M., 1997. The deferred path heuristic for the generalized tree alignment problem. J. Comp. Biol., 4:415-43 1.

[30] Sellers, P. H. 1974. On the theory and computation of evolutionary distance. SIAM J. Appl. Math, 26:787-793.

[31] Smith, T. F., Waterman, M. S. and Fitch, W. M., 1981. Comparative biosequence metrics. J. Mol. Evol., 18:38-46.

[32] Smith, T. F. and Waterman, M. S., 1981. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195- 197.

[33] Sokal, R. R. and Michener, C. D., 1958. A statistical method for evaluating systematic relationships. University of Kansas Scientific Bulletin, 28:1409-1438.

[34] Studier, J. A. and Keppler, K. J., 1988. A note on the neighbour-joining algorithm of Saitou and Nei. Molecular Biology and Evolution, 5: 729 -731.

[35] Thompson, J. D. Higgins, D. G. and Gibson, T. J., 1994. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res., 22:4673- 4680.

[36] Thompson, J. D., Higgins, D. G. and Gibson, T. J., 1994. Improved sensitivity of profile searches through the use of sequence weights and gap excision. CABIOS 10, 19-29.

[37] Wang, L. and Jiang, T., 1994. On the complexity of multiple sequence alignment. Journal of Computational Biology 1(4), 337-348.

[38] Wheeler, W. C. and Gladstein, D. S. 1994. MALIGN: A multiple sequence alignment program. J Hered, 85:417-418.