臺灣博碩士論文加值系統

本研究發展一套相關性分析法（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-168

6. Comet, J. P. and J. Henry 2002. Pairwise sequence alignment using a PROSITE pattern-derived similarity score. Computers and Chemistry 26: 421 – 436

7. 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-360

11. Iwamoto, S. 1993. From Dynamic Programming to Bynamic Programming Journal of Mathematical Analysis and Applications 177: 56-74


12. 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-325

14. Meyers, E. and W. Miller 1988. Optimal alignments in linear space. CABIOS 4: 11–17

15. Meyers, E. and W. Miller 1988. Sequence comparison with concave weighting functions. Bull. Math. Biol. 50: 97–120

16. 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-117

18. Smith, T. F., M. S. Waterman and W. M. Fitch 1981. Comparative
biosequence 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-122

20. Waterman, M. S., T. F. Smith and W. A. Beyer 1976. Some biological sequence metrics. Adv. Math. 20: 367–387

21. Waterman, M. S. 1984. General methods of sequence comparison. Math. Biol. 46: 473–500

22. Wilbur, J. and D. J. Lipman, 1984. The context dependent comparison of biological sequences. SIAM J. Appl. Math. 44: 557–567

23. 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