# 臺灣博碩士論文加值系統

(44.200.169.3) 您好！臺灣時間：2022/12/01 01:34

:::

### 詳目顯示

:

• 被引用: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.
 目錄中文摘要... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...IABSTRACT... ... ... ... ... ...... ... ... ... ... ... ... ... ... ...II誌謝... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...III目錄... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...IV圖目錄... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...V第一章 導論... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...11.1序列比對... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...21.2間隔處罰函數... ... ... ... ... ... ... ... ... ... ... ... ... ... ...101.3任意間隔處罰函數... ... ... ... ... ... ... ... ... ... ... ... ... ...121.4研究目的與動機... ... ... ... ... ... ... ... ... ... ... ... ... ...15第二章 相關研究... ... ... ... ... ... ... ... ... ... ... ... ... ... ...172.1凸形間隔處罰函數研究... ... ... ... ... ... ... ... ... ... ... ... ...182.2 GUSFIELD的凸形間隔處罰函數... ... ... ... ... ... ... ... ... ... ...212.3凸函數演算法兩大步驟說明... ... ... ... ... ... ... ... ... ... ... ...27第三章 我們的演算法... ... ... ... ... ... ... ... ... ... ... ... ... ...283.1凹形間隔處罰函數研究... ... ... ... ... ... ... ... ... ... ... ... ...293.2我們的演算法... ... ... ... ... ... ... ... ... ... ... ... ... ... ...323.3凹函數演算法兩大步驟說明... ... ... ... ... ... ... ... ... ... ... ...38第四章 結論... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...404.1 研究成果... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...404.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.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 結構限制下的序列比對：模型、技術與應用 2 快速整體與半整體比對演算法與基因序列分析 3 具限制條件的序列比對：考慮範圍與順序資訊

 無相關期刊

 1 永續校園環境更新診斷與改造評估之探討-以臺中市新社高中為例 2 金門國家公園民宿發展現況之研究 3 物流能耐、物流管理績效、競爭優勢與財務績效關係之研究-以科學園區廠商為例 4 半導體設備13.56MHz 2KW RF Generator機台之研究與分析 5 紅外線遙控器之BLE4.0橋接器 6 整合於穿戴裝置之無源式RFID感測器系統 7 基於CC型鐵芯的無線電力傳送系統之分析 8 LED訂單需求預測之研究-以某LED代工廠為例 9 銀行經營績效持續性之探討-以漂移者停駐者模型討論 10 接受飲食管理系統減重者之使用行為研究 11 新北市政府行銷觀光工廠之公私協力研究 12 我國集會遊行法修法方向之探討- 由司法院大法官釋字第718號解釋出發 13 胺基酸與結構字元間殘基接觸數之研究 14 電子零組件供應商評選關鍵因素之探討-以通訊產品製造商為例 15 國軍申訴制度服務品質之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室