跳到主要內容

臺灣博碩士論文加值系統

(3.233.217.106) 您好!臺灣時間:2022/08/17 22:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張家銘
研究生(外文):Jia-Ming Chang
論文名稱:緊湊集合關係及其在演化樹和多重序列排比之評估的應用
論文名稱(外文):Compact Set Relation and Its Application in the Evaluation of the Evolution Tree and Multiple Sequence Alignment
指導教授:唐傳義
指導教授(外文):Chuan Yi Tang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
中文關鍵詞:Compact SetMultiple Sequence AlignmentEvolution Tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:159
  • 評分評分:
  • 下載下載:12
  • 收藏至我的研究室書目清單書目收藏:1
現有評估演化樹(Evolution Tree)或多重序列比對(Multiple Sequence Alignemnt)的理論,
都過於強調數學上的絕對最佳解,例如:兩兩距離和(Sum-of-Pair)、樹型大小(Tree Size),等等。
本篇論文中,我們將從相對遠近關係是否保持的角度,提出一個新的評估標準,即以緊湊集合定義的鄰近關係。
就一個好的演化樹或多重序列比對而言,任三個物種在演化樹上或比對後的遠近關係,應與建樹前或比對前的遠近關係一致;
然而有些物種間的遠近關係或許不是那麼重要,因此我們利用緊湊集合的特性
(即集合內任意兩元素之間最長的距離,仍小於該集合中任一元素與集合外元素之間最短的距離),選出較為重要的遠近關係,
並且利用這些關係是否獲得保持來評估演化樹或多重序列比對的優劣。
本論文最後進行一系列的實驗,利用在緊湊集合所定義的鄰近關係,評估現有一些知名的建立演化樹與多重序列比對的程式。
此外本論文也提出一個新的多重序列比對演算法--YAMA-MST。實驗數據證明,YAMA-MST比起現有MSA的程式,
更能符合評估演化樹的需要。

1 INTRODUCTION 1
1.1 Estimating the Evolution Tree . . . . . . . . . . . . . . . . . . . . . 1
1.2 Estimating Multiple Sequence Alignment . . . . . . . . . . . . . . . 3
2 THE COMPACT SET 5
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Constructing Compact Sets . . . . . . . . . . . . . . . . . . . . . . 6
2.3 The Neighboring Relation With Repsect To Compact Sets . . . . . 10
3 ESTIMATING THE EVOLTION TREE 13
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 The Estimation Algorithm . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Exprimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 ESTIMATING MIULTIPLE SEQUENCE ALIGNMENT 18
4.1 The Estimation Algorithm . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 YAMA-MST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Exprimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 CONCLUSIONS AND FUTURE WORK 23

[1] V. Bafna, E.L. Lawler, and P.A. Pevzner. Approximation algorithms for
multiple sequence alignment. Theoretical Computer Science, 182:233—244,
1997.
[2] W. Bains. Multan: a program to align multiple dna sequences. Mucleic Acids
Research, 14:159—177, 1986.
[3] G.J. Barton and M.J.E. Sternberg. A stragtegy for the rapid multiple align-ment
of protein. Journal of Molecular Biology, 19:327—337, 1987.
[4] P. Bonizzoni and G. Della Vedova. The complexity of multiple sequence
alignment with SP-score that is a metric. Theoretical Computer Science,
259:63—79, 2001.
[5] J. Carlos and J. Meidanis. Introdution to computational molecular biology.
PWS publishing company, 1997.
[6] H. Carrillo and D. Lipman. The multiple sequence alignment problem in
biology. SIAM Journal on Applied Mathematics, 48(5):1073—1082, 1988.
[7] S.C. Chan, A.K.C. Wong, and D.K.Y. Chiu. A survey of multiple sequence
comparison methods. Bulletin of Mathematical Biology, 48:1073—1082, 1992.
[8] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to
Algorithms. MIT Press, Cambridge, MA, second edition, 2001.
[9] F. Corpet. Multiple sequence alignment with hierarchical clustering. Nucleic
Acids Research, 16:10881—10890, 1988.
25
[10] E. Dekel, J. Hu, and W. Ouyang. An optimal algorithm for finding compact
sets. Information Processing Letters, 44:285—289, 1992.
[11] D.J.Lipman and S.F.Altschul. A tool for multiple sequences alignment. In
Proc.Nat.Acad. Sci. U.S.A., 1989.
[12] D.Snakoff. Simultaneous solution of rna folding, alignment and protosequence
prolblems. SIAM J. Appl. Math., 1985.
[13] J.T. Fang. Constructing and application of evolutionary tree’s measurement
model. Master’s thesis, Department of Computer Science National Tsing Hua
University, 2000.
[14] D.F. Feng and R.F. Doolittle. Progressive sequence alignment as a prerequisite
to correct phylogenetic trees. Journal of Molecular Evolution, 25:351—360,
1987.
[15] H.N. Gabow and R.E. Tarjan. A linear-time algoritm for a special case of
disjoint set union. J. Comput. System Sci., 30:209—221, 1985.
[16] G.H. Gonnet, C. Korostensky, and S. Benner. Evaluation measures of multiple
sequence alinments. Journal of Computational Biology, 7:261—276, 2000.
[17] D. Gusfield. Efficient methods for multiple sequence alignment with guaran-teed
error bounds. Bulletin of Mathematical Biology, 55:141—154, 1993.
[18] D. Harel and R.E. Tarjan. Fast algorithm for finding nearest common ances-tor.
SIAM. J. Comput., 13:285—289, 1984.
[19] S. Henikoff and J.G. Henikoff. Amino acid substitution matrices from protein
blocks. In Proceedings of the National Academy of Sciences USA, volume 8,
pages 1154—1171, 1998.
[20] D.G. Higgins and P. Sharpe. CLUSTAL: a package for performing multiple
sequence alignment on a microcomputer. Gene, 73:237—244, 1988.
[21] D.G. Higgins, J.D. Thompson, and T.J. Gibson. Using clustal for multiple
sequence alignments. Methods in Enzymology, 266:383—402, 1996.
26
[22] T. Jiang, P. Kearney, and M. Li. A polynomial time approximation scheme
for inferring evolutionary trees from quartet topologies and its application.
SIAM. J. Comput., 30:1942—1961, 2001.
[23] S.K. Kim. A note on finding compact sets in graphs represented by an adja-cency
list. Information Processing Letters, 57:335—338, 1996.
[24] M. Li, B. Ma, and L. Wang. Near optimal multiple alignment within a band
in polynomial time. In STOC, pages 425—434, Portland, Oregon, 2000.
[25] W. H. Li. Molecular Evolution. Sinauer Associates, Inc., 1997.
[26] S. Needleman 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.
[27] P.A. Pevzner. Multiple alignment, communication cost, and graph matching.
SIAM Journal on Applied Mathematics, 52:1763—1779, 1992.
[28] N. Saitou and M. Nei. The neighbor-joining method: a new method for
reconstructing phylogenetic trees. Molecular Biology and Evolution, 4:406—
425, 1987.
[29] B. Schieber and U. Vishkin. On finding lowest common ancestor:simplification
and parallelization. SIAM J. Comput., 17:1253—1262, 1988.
[30] S.F.Altschul and D.J.Lipman. Trees,star and mutiple biological sequence alig-ment.
SIAM J. Appl. Math., 1989.
[31] D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. J. Comput.
System Sci., 13:362—391, 1983.
[32] P.H.A. Sneath and R.R. Sokal. Numerical Taxonomy, pages 230—234. Free-man,
San Francisco, CA, 1973.
[33] R.E. Tarjan. Data Structure and Network Algoritms. SIAM, Philadelphia,
PA, 1983.
27
[34] W.R. Taylor. Multiple sequence alignmnet by a pairwise alignment. Computer
Applications in Biosciences, 3:81—87, 1987.
[35] J.D. Thompson, D.G. Higgins, and T.J. Gibson. CLUSTAL W: 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.
[36] J.D. Thompson, F. Plewinak, and O. Poch. Balibase: a benchmark alignment
database for the evolution of multiple sequence alignments. Bioinformatics,
15:87—88, 1999.
[37] J.D. Thompson, F. Plewinak, and O. Poch. A comprehensive comparison
of multiple sequence alignment programs. Nucleic Acids Res., 27:2682—2690,
1999.
[38] T.K. Vintsyuk. Speech discrimination by dynamic programming. Comput.,
4:52—57, 1967.
[39] L. Wang and T. Jiang. On the complexity of multiple sequence alignment.
Journal of Computational Biology, 1(4):337—348, 1994.
[40] B.Y. Wu. Constructing the maximum consensus tree from rooted. In the
proceedings of National Computer Symposium, 2001.
[41] D. Zivkovic. A fast algorithm for finding the compact sets. Information
Processing Letters, 38:339—342, 1991.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 管中祥(2001):<從「資訊控制」的觀點反思「電子化政府」的樂觀迷思>,《資訊社會研究》,1。南華大學社會學研究所。
2. 黃厚銘(2001):<Heidegger的哲學思想與資訊科技>,《資訊社會研究》,1。南華大學社會學研究所。
3. 蘇蘅、吳淑俊(1997):<電腦網路問卷調查可行性及回覆者特質的研究>,《新聞學研究》,54。
4. 賴鼎銘(1997):<後現代狀況下的圖書資訊服務>,《圖書館學與資訊科學》
5. 劉建基 (2001):<從批評倫理學論網路文本>,《第二屆文山評論學術研討會論文集》。
6. 廖鐿鈤(2001):<虛擬社區凝聚力的初探>,《資訊社會研究》1。南華大學社會學研究所。
7. 曹志漣(1998)<虛擬曼荼羅>,《中外文學》,26(11):78-109。
8. 郭良文、林素甘(2001):<質化與量化研究方法之比較分析>,《資訊傳播與圖書館學》,7(4)。
9. 許清琦 (2000):<電腦的發明、應用及對人類的影響>,《歷史月刊》1月號。
10. 孫秀蕙 (1997):<如何研究網路傳播>,《傳播研究簡訊》,9:1-6。
11. 吳齊殷(1998b):<虛擬社區vs.真實生活>,《科學月刊》,29(8):668。
12. 吳筱玫 (1999):<電子報對傳統新聞媒體的衝擊>,《網路通訊雜誌》,90。
13. 林文剛(1997):〈卡拉OK在身份認同構成的模糊特性〉,《新聞學研究》,
14. 李順興(1999b):〈網路文學形式與「讀寫者」的出現〉,《文訊》雜誌,162:40-42。
15. 李順興(1999a):<當文字通了電:與姚大鈞談網路文學>,《聯合文學》,159: