( 您好!臺灣時間:2022/05/29 16:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::


研究生(外文):Ta-Chin Hsu
論文名稱(外文):Multiple Sequence Alignment via Phylogenetic Tree
指導教授(外文):Arthur Chou
外文關鍵詞:phylogenetic treemultiple sequence alignmentsequence graph
  • 被引用被引用:0
  • 點閱點閱:856
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
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.
第三章 演化樹
第四章 以演化樹指引多重排比
[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.
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
第一頁 上一頁 下一頁 最後一頁 top