跳到主要內容

臺灣博碩士論文加值系統

(44.200.169.3) 您好!臺灣時間:2022/12/01 01:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡維謙
研究生(外文):Cai,Wei-Qian
論文名稱:考慮凹形間隔處罰函數之有效率生物序列比對演算法
論文名稱(外文):Efficient Algorithms of Sequence Alignments with Concave Gap Penalties
指導教授:吳哲賢吳哲賢引用關係
指導教授(外文):Wu,Jer-Shyan
學位類別:碩士
校院名稱:中華大學
系所名稱:生物資訊學系碩士班
學門:生命科學學門
學類:生物訊息學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:44
中文關鍵詞:演算法凹形間隔處罰函數序列比對
外文關鍵詞:AlgortihmsSequence alignmentsConcave gap penalties
相關次數:
  • 被引用被引用:0
  • 點閱點閱:88
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
生物序列比對問題是生物資訊學中,非常基礎及重要的研究課題,如何讓序列比對的時間減少,而達到有效率的生物序列比對,一直是一個被廣泛討論的問題。
針對序列比對問題,假設n及m為比對兩序列長度,n ≧ m。首先是由Needleman及Wunsch於1970年,針對無間隔處罰函數,提出O(nm)演算法。接著Waterman、Smith及Beyer於1976 年,提出考慮任意間隔處罰函數,時間複雜度O(nm2) 的演算法。Gotoh於1982年針對線性間隔處罰,提出時間複雜度為O(nm)的演算法。針對凸形間隔處罰函數,Myers及Miller於1988年、Galil 及Giancarlo於1989 年,以及Gusfield於1997 年,也分別提出了時間複雜度O(nmlogm)的演算法。
然而到目前為止,尚未有學者針對凹形間隔處罰函數的序列比對問題,提出相關研究。本篇論文中我們是針對凸形間隔處罰函數序列比對問題,深入討論並研究分析其特性後,進而推導出時間複雜度O(nmlogm)有效率的演算法。

Biological sequence alignments problem is a very basic and important researches on Bioinformatics, how to reduce the excution time and obtain efficient sequence alignments has been widely discussed.
For sequence alignments problem, where n, m are the sequence lengths, n ≧ m, Needleman and Wunsch first proposed the O(nm) algorithms in 1970. And then, Waterman, Smith and Beyer in 1976, proposed O(nm2) algorithms for affine gap penalties function. In 1982, Gotoh proposed O(nm) algorithms for linear gap penalties. For convex gap penalties, Myers and Miller in 1988, Galil and Giancarlo in 1989, and Gusfield in 1997, they also proposed O(nmlogm) algorithms.
Until now, there is no scholars to propse researches about sequence alignments problem with concave gap penalties. In this paper, we focus our researches on sequence alignments problem with convcave gap penalties, and finally proposed O(nmlogm) efficient algorithms.

目錄
中文摘要... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...I
ABSTRACT... ... ... ... ... ...... ... ... ... ... ... ... ... ... ...II
誌謝... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...III
目錄... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...IV
圖目錄... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...V
第一章 導論... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...1
1.1序列比對... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...2
1.2間隔處罰函數... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
1.3任意間隔處罰函數... ... ... ... ... ... ... ... ... ... ... ... ... ...12
1.4研究目的與動機... ... ... ... ... ... ... ... ... ... ... ... ... ...15
第二章 相關研究... ... ... ... ... ... ... ... ... ... ... ... ... ... ...17
2.1凸形間隔處罰函數研究... ... ... ... ... ... ... ... ... ... ... ... ...18
2.2 GUSFIELD的凸形間隔處罰函數... ... ... ... ... ... ... ... ... ... ...21
2.3凸函數演算法兩大步驟說明... ... ... ... ... ... ... ... ... ... ... ...27
第三章 我們的演算法... ... ... ... ... ... ... ... ... ... ... ... ... ...28
3.1凹形間隔處罰函數研究... ... ... ... ... ... ... ... ... ... ... ... ...29
3.2我們的演算法... ... ... ... ... ... ... ... ... ... ... ... ... ... ...32
3.3凹函數演算法兩大步驟說明... ... ... ... ... ... ... ... ... ... ... ...38
第四章 結論... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...40
4.1 研究成果... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...40
4.2 未來研究目標... ... ... ... ... ... ... ... ... ... ... ... ... ... ...41
參考文獻... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...43
[1] J. Palmer and L. Herbon, “Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence”, J. Mol. Evolut, Vol. 27, pp. 87-97, 1988.
[2] W. Li, Z. Gu, H. Wang, and A. Nekrutenko, “Evolutionary analyses of the human genome”, Nature, Vol. 409, pp. 847-849, 2001.
[3] S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman, “Basic Local Alignment search Tool”, J. Mol. Biol., 215, pp. 403-410, 1990.
[4] G. Gonnet, M. Cohen, and S. Benner. "Exhaustive matching of the entire protein sequence database", Sci., Vol. 256, pp. 1443-1445, 1992.
[5] S. Altschul and B. Erickson, “Optimal sequence alignment using affine gap costs”, Bull. Math. Biol., Vol. 48, pp. 603-616, 1986.
[6] J. Fickett, “Fast Optimal alignment”, Nucleic Acids Res., Vol. 12, pp. 175-180, 1984.
[7] Z. Galil and R. Giancarlo, “Speeding up dynamic programming with applications to molecular biology”, Theor. Comp. Sci., Vol. 64, pp. 107-118, 1989.
[8] W. Pearson and W. Miller. “Dynamic programming algorithms for biological sequence comparison”, Numerical Computer Methods, Vol. 210, pp. 575-601, 1992.
[9] S. Needleman and C. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins”, J. Mol. Biol, Vol. 48, pp. 443-453, 1970.
[10] S. Karlin and S. Altschul. “Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes”, Proceedings of the National Academy of Sciences of the U.S.A., Vol. 87, pp. 2264-2268, 1990.
[11] D. Gusfield, “Algorithms on strings, Trees and sequences”, Cambridge University Press, Cambridge, 1997.
[12] M. Waterman, T. Smith, and W. Beyer, “Some biological sequence metrices”, Advances in Mathematics, Vol. 20, pp. 367-387, 1976.
[13] O. Gotoh, “An improved algorithm for matching biological sequences”, J. Mol. Boil., Vol. 162, pp. 705-708, 1982.
[14] M. Waterman, “Efficient sequence alignment algorithms”, J. Theor. Biol., Vol. 108, pp. 333-337, 1984.
[15] W. Miller and E. Myers, “Sequence comparisons with concave weighting functions”, Bull. Math. Biol., Vol. 50, pp. 97-120, 1988.
[16] D. Gusfield, K. Balasubramanian, and D. Naor. “Parametric optimization of sequence alignment”, Journal of Algorithmica, Special Issue on String Algorithms, Vol. 12, pp. 312-326, 1994.
[17] M. Waterman and M. Eggert. “A new algorithm fo best subsequence alignments with application to tRNA-rRNA comparisons”, J. Mol. Boil., Vol. 197, pp. 723-725, 1987.
[18] M. Fredman, “Algorithms for computing evolutionary similarity measures with length independent gap penalities”, Bull. Math. Biol., Vol. 46, pp. 533-566, 1984.
[19] S. Altschul and B. Erickson, “Optimal sequence alignment using affine gap costs”, Bull. Math. Biol., Vol. 48, pp. 603-616, 1986.
[20] S. Altschul and W. Gish, “Local Alignment Statistics”, Methods Enzymol. Vol. 266, pp. 460-480, 1996.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top