臺灣博碩士論文加值系統

序列比對在生物資訊學上是最基本且重要的部份。當發現某一未知序列時，欲找出其功能或結構時，可以利用與已知序列比對結果，得知其與相似序列可能具有相似功能或結構。
本篇論文針對現今應用最為廣泛的雙序列比對工具：BLAST，做為研究之對象。首先對BLAST比對結果曲線取一寬度，利用全域序列比對方法，作帶狀動態規劃分析，嘗試提昇BLAST比對結果分數(內部改進方法)。接著對BLAST比對結果曲線兩端，運用外部延伸技巧，期望能找出BLAST未能包含的相似序列片段，再度提高序列比對分數(外部改進方法)。
最後我們的實驗結果得知： BLAST比對分數和相同範圍的區域序列比對分數相近，表示內部改進空間有限；而針對BLAST比對結果較差的情況，外部改進方法有顯著的提昇序列比對分數，表示外部改進方法是一個快速且有效率改進BLAST的工具。

Sequence alignment is the most basic and important topic on bioinformatics. While we have one new unknown sequence, do pairwise sequence alignment with another defined sequence, and find they are the similar functions and structures.
In this paper, our research topic put on the most popular pairwise sequence alignment tool ： BLAST. First using global sequence alignment to do band dynamic programming on BLAST result curve, try to enhance the alignment score (inner improvement). And then using extended technique to find some new similar sequence not in BLAST result, again enhance the alignment score (outside improvement).
Finally by our program result, we find the profit of inner improvement is little, but the profit of outside improvement is obvious. So outside improvement is one fast and efficient tool to improve BLAST.

第一章 簡介
1-1 序列比對
1-2 全域序列比對
1-3 局部序列比對
1-4 間格處罰函數
1-5 計分矩陣
第二章 BLAST
2-1 簡介
2-2 Ungapped BLAST演算法
2-3 Gapped BLAST 演算法
第三章 改進BLAST之演算法
3-1 帶狀動態規劃
3-2 改進演算法之簡介
3-3 內部帶狀動態規劃
3-4 外部延伸帶狀動態規劃
第四章 實驗數據
4-1 資料來源
4-2 實驗結果
第五章 結論
5-1 研究成果
5-2 未來研究方向

[1] S. F. Altschul and B. W. Erickson, “Optimal sequence alignment using affine gap costs.” Bull. Math. Biol., 48, pp.603-616, 1986.
[2] S. F. Altschul and W. Gish, “Local Alignment Statistics.” Methods Enzymol. 266, pp.460-480, 1996.
[3] S. F. Altschul and S. Suhai, “Theoretical and Computational Method in Genome Research.” Plenum Press, New York, pp.1-14, 1997.
[4] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, “Basic Local Alignment search Tool.” J. Mol. Biol., 215, pp.403-410, 1990.
[5] S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman, “Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.” Nucleic Acids Res. 25, pp.3389-3402, 1997.
[6] K. M. Caho, W. R. Pearson, and W. Miller, “Aligning Two Sequences within a Specified Diagonal Band. Comput.” Appl. Biosci., 8, pp.481-487, 1992.
[7] J. W. Fickett, “Fast Optimal alignment.” Nucleic Acids Res., 12, pp.175-180, 1984.
[8] W. M. Fitch and T. F. Smith, “Optimal sequence alignments.” Proc. Natl. Acad. Sci. US, 80, pp.1382-1386, 1983.
[9] O. Gotoh, “An improved algorithm for matching biological sequences.” J. Mol. Biol., 162, pp.705-708, 1982.
[10] S. Henikoff and J. G. Henikoff, “Amino acid substitution matrices from protein relationships.” Proc. Natl. Acad. Sci. USA, 89, pp.10915-10919, 1992.
[11] S. Karlin, and S. F. Altschul, “Applications and statistics for multiple high-scoring segments in molecular sequences.” Proc. Natl. Acad. Sci. USA, 90, pp.5873-5877, 1993.
[12] E. W. Myers and W. Miller, “Optimal alignments in linear space.” Comput. Appl. Biosci., 48, pp.603-616, 1988.
[13] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequences of two proteins.” J. Mol. Biol. 147, pp.195-197, 1970.
[14] W. R. Pearson, “Rapid and sensitive comparison with FASTP and FASTA.” Methods Enzymol., 183, pp.63-98, 1990.
[15] W. R. Pearson, “Searching protein sequence libraries: Comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms.” Genomics, 11, pp.635-650, 1991.
[16] W. R. Pearson and D. J. Lipman, “Improved tools for biological sequence comparison.” Proc. Natl. Acad. Sci. USA, 85, pp.2444-2448, 1988.
[17] W. R. Pearson and W. Miller, “Dynamic Programming Algorithms for Biological Sequence Comparison.” Methods Enzymol., 210, pp.575-601, 1992.
[18] R. M. Schwartx and M. O. Dayhoff, “Atlas of Protein Sequence and Structure. National Biomedical Research Foundation.” Washington, DC, Vol. 5, Suppl. 3, pp.353-358, 1978.
[19] T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences.” J. Mol. Biol., 147, pp.195-197, 1981.
[20] T. F. Smith, M. S. Waterman, and C. Burks, “The statistical distribution of nucleic acid similarities.” Nucleic Acids Res., 13, pp.645-656, 1985.