(3.238.99.243) 您好！臺灣時間：2021/05/15 19:15

### 詳目顯示:::

:

• 被引用:0
• 點閱:131
• 評分:
• 下載:0
• 書目收藏:0
 本研究發展一套相關性分析法（Correlation Approach）進行序列比對（Sequence Alignment）。這種方法可將序列比對拆成相關性比對、搜尋與計分三個階段處理，因此分數矩陣（Scoring Matrix）僅在最後階段加總計分時併入考量即可，它的變動並不影響最佳比對序列（Optimal Sequence）的搜尋；且保證能找到所有的最佳比對序列。相關性分析法係利用反互斥或運算（Exclusive NOR）進行比對序列的運算，比對字元相符（Match）則輸出1，不相符（Mismatch）則輸出0，再從0及1所組成的相關性矩陣（Correlation Matrix）建構累加相關性矩陣（Cumulative Correlation Matrix），而從中搜尋出所有最佳比對序列的路徑（Path）並找到相應的最佳比對序列，最後加入分數矩陣計算最佳比對序列的總分。因為前兩步驟都不需要考量分數矩陣，所以除了最後計分階段之外相關性分析法並不受分數矩陣的變動而影響比對結果。但若採用動態規劃（Dynamic Programming）做雙序列比對，則分數矩陣的決定會影響動態規劃的比對結果，一旦分數矩陣變動則必須重新所有比對過程與計算；且不能保證找到全部的最佳序列比對。實驗結果顯示，所提出的方法不但能夠就不同的分數矩陣進行快速運算，提供完整最佳序列比對的資訊，而且較直覺易懂。
 This study develops a novel method for sequence alignment based on correlation appoach. This approach can be broken down into three stages – correlation, searching and scoring which are decoupling processes. A scoring process is incorporated into the alignment process in the final stage. Therefore, the variation of scoring matrix doesn’t affect the correlation and searching procedures. Moreover, all feasible optimal sequences are ensured to be obtained by using the developed approach. The correlation approach for sequence alignment is mainly based on exclusive NOR operation. If two symbols are matching, output 1as a result, if mismatch, output 0. Subsequently, all feasible paths of optimal sequences are searched and their corresponding sequences are found from the correlation matrix and cumulative correlation matrix. Finally, the score of optimal the sequence is calculated with the specified scoring matrix. Due to the 1st and 2nd stages not considering scoring matrix, the variation of scoring matrix couldn’t affect the aligned results with the correlation approach. Yet, dynamic programming, which is widely used in sequence alignment, often suffers from the recalculation of the whole alignment process while scoring matrices change. Therefore, different optimal sequences are obtained. Compared with dynamic programming, the developed alignment approach with three stages of decoupling processes is proved to provide complete sets of optimal sequences and a more efficient and comprehensive way for sequence alignment.
 誌謝………………………………………………………………………I中文摘要……………….………………………………………………II英文摘要………………………………………………………………III圖目錄………………….………………………………………………VI表目錄………………….………………………………………………IX第一章 前言……………………………………………………………1第二章 文獻探討………………………………………………………4 2.1 動態規劃（Dynamic Programming）.................6 2.1.1 Needleman-Wunsch Method（Global）……………6 2.1.2 Smith-Waterman Method（Local）………………11 2.2 散列編碼法……………………………………………….14 2.3 序列資料庫搜尋………………………………………….16 2.3.1 FASTA（EBI）………………………………………17 2.3.2 BLAST（NCBI）…………………………………….20第三章 材料與方法………………………………………………….25 3.1 反互斥或運算…………………………………………….25 3.2 相關性矩陣的路徑搜尋………………………………….26 3.2.1 路徑搜尋演算法………………………………….28 3.2.2 區域性序列比對連接成全域性序列比對……….29 3.2.3 最佳比對序列加權計分………………………….34 3.3 不相符的無間隙比對與間隙比對……………………….35 3.3.1 不相符的無間隙比對………………………………36 3.3.2 不相符的間隙比對…………………………………38第四章 實驗結果與討論…………………………………………….41 4.1 以動態規劃法進行序列比對…………………………….41 4.1.1 產生唯一的回溯路徑………………………………41 4.1.2 產生不同的回溯路徑………………………………44 4.2 以相關性分析法進行序列比對………………………….47 4.2.1 以相關分析法解決DP僅能產生唯一路徑的問題…47 4.2.2 以相關分析法解決DP可能產生不同路徑的問題…51 4.3 以軟體驗證實驗結果…………………………………….55 4.3.1 利用EMBOSS進行序列比對…………………………55 4.3.2 利用Correlation進行序列比對………………….56第五章 結論………………………………………………………….60參考文獻……………………………………………………………….62
 1. Altschul, S. F., R. J. Carrol and D. J. Lipman 1989. Weights for data related by a tree. J. Mol. Biol. 207: 647-653.2. Altschul, S. W., W. Gish, W. Miller, E. Meyers and D. J. Lipman 1990. Basic local alignment search tool. J. Mol. Biol. 215: 403–410.3. Allison, L. 1993. Normalization of affine gap cost used in optimal sequence alignment. J. Theory. Biol. 161: 263–269.4. Bellman, R. E. 1957. “Dynamic Programming,” Princeton Univ. Press,Princeton, NJ.5. Blum, Norbert 2000. Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology. Journal of Algorithms 35: 129-1686. Comet, J. P. and J. Henry 2002. Pairwise sequence alignment using a PROSITE pattern-derived similarity score. Computers and Chemistry 26: 421 – 4367. Fitch, W. M. 1966. An improved method of testing for evolutionary homology. J. Mol. Biol. 16: 9–16.8. Fitch, W. M. and T. F. Smith 1983. Optimal sequence alignments. Proc. Natl. Acad. Sci. USA 80: 1382–1386.9. Helman, P. and A. Rosenthal 1985. A comprehensive model of dynamic programming. SIAM J. on Algebraic and Discrete Methods 6: 319-334.10. Henikoff, Steven. 1996. Scores for sequence searches and alignments. Current Opinion in Structural Biology 6: 353-36011. Iwamoto, S. 1993. From Dynamic Programming to Bynamic Programming Journal of Mathematical Analysis and Applications 177: 56-7412. Lipman, D. J. and W. R. Pearson 1985. Improved tools for biological sequence comparison. Science 227: 1435-1441.13. Matsuda, H., T. Ishihara and A. Hashimoto 1999. Classifying molecular sequences using a linkage graph with their pairwise similarities. Theoretical Computer Science 10: 305-32514. Meyers, E. and W. Miller 1988. Optimal alignments in linear space. CABIOS 4: 11–1715. Meyers, E. and W. Miller 1988. Sequence comparison with concave weighting functions. Bull. Math. Biol. 50: 97–12016. Needleman, S. B. and C. D. Wunsch 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48: 443–453.17. Schwikowski, B. and M. Vingron 2003. Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions. Discrete Applied Mathematics 127: 95-11718. Smith, T. F., M. S. Waterman and W. M. Fitch 1981. Comparativebiosequence metrics. J. Mol. Evol. 18: 38–46.19. Smith, R. F. and T. F. Smith 1990. Automatic Generation of Primary Sequence Patterns from Sets of Related Protein Sequences. Proc. Nat. Acad. Sci. USA 87: 118-12220. Waterman, M. S., T. F. Smith and W. A. Beyer 1976. Some biological sequence metrics. Adv. Math. 20: 367–38721. Waterman, M. S. 1984. General methods of sequence comparison. Math. Biol. 46: 473–50022. Wilbur, J. and D. J. Lipman, 1984. The context dependent comparison of biological sequences. SIAM J. Appl. Math. 44: 557–56723. Wu, Y. F. and H. Maitre 1988. A new dynamic programming method for stereo vision ignoring epipolar geometry. Pattern Recognition, 9th International Conference 11: 146–148
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 楊永年，〈建立以地方政府為主體之救災組織體系-以九二一大地震與八掌溪兩岸比較〉。《中央警察大學警學叢刊》，第32卷第3期，民90.11，頁245-268。 2 彭朱如、王維元、張錦文，〈醫院對外合作策略與績效評估〉，《醫院》，第31卷第2期，民87，頁32-44。 3 沈慶盈，〈從組織間關係談社會服務資源的整合〉，《社區發展季刊》，民89，頁145-155。

 1 骨骼肌細胞中神經醯胺影響胰島素訊息傳遞之機轉 2 以可靠度分析航機系統與維修成本研究-以F航空公司為例 3 Wii遙控技術應用於數位萵苣博物館之操控 4 主管教練行為對員工知識移轉績效與創新行為影響之研究—以主管部屬交換關係為調節變項 5 應用DoDAF架構模式建立救災應變流程模擬 6 PPP2R2B基因：啟動子記述及Bβ1/Bβ2isoform在神經退化的角色 7 以液相層析電噴灑四極柱飛行時間質譜儀及毛細管電泳線上濃縮技術對九種色胺類濫用藥物的分析研究 8 對甲苯磺酸在醣化學的應用：一個較環保的醣基建構單元合成法 9 薄膜光學檢測技術發展與應用 10 利用接地點運動分析與實現機器蛇之CPG可微分步態 11 雙線性系統控制使用函數近似法 12 利用基因演算法自動產生機器蛇攀階步態 13 熱休克蛋白過度表現及氧化壓力對SCA17細胞模式影響之研究 14 第十七型脊髓小腦共濟失調症致病機轉：伴隨蛋白的保護功能與TATA結合蛋白CAG三核苷重複擴增造成不正常蛋白質摺疊之研究

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