臺灣博碩士論文加值系統

DNA序列可以表示成一長串由A、C、G與T四個字元所組成的文字資料，因為DNA序列的長度與複雜度，顯示出DNA序列視覺化方面所面臨的挑戰。在本篇論文中，我們提出了一個視覺化的方法，稱為VBP（經由五面體之視覺化）演算法將DNA序列視覺化並分析序列間之相似性。在論文中，我們應用一個馬可夫鏈模型來表示DNA序列以計算所有的狀態轉移機率，並且將這些狀態轉移機率對映成四個不同的五面體，根據這四個五面體，可以畫出一條三度空間的軌跡來表示DNA序列在巨觀之下的形態。
為了加快相似DNA序列的搜尋速度，提出一個以內容為基礎的搜尋方法來搜尋DNA序列資料庫中的相似序列出來。此方法利用Peano掃描法與傅立葉轉換將一維的DNA序列轉換成二維的遠場圖；接著使用主成分分析法擷取出特徵以有效的從資料庫中取出相似的DNA序列。藉著結合所提出的視覺化與相似序列搜尋方法，DNA序列的功能與相似的序列將可以快速的被辨別。

Genomic DNA sequences can been represented as long text data composed of alphabets A, C, T and G. These sequences present visualization challenges due to their length and complexity. In this paper, we proposed a visual technique called VBP (Visualization by Pentahedrons) algorithm to visualize and analyze similarity of DNA sequences. Here, a Markov chain model is employed to calculate the state transition probabilities of DNA sequences and map them into four different pentahedrons. According to these four pentahedrons, a three-dimensional trajectory can be drawn to represent the formation of DNA sequence in a global view.
For speeding up the similar DNA sequence search process, a content-based retrieval technique is proposed to search the similar DNA sequences against the DNA sequence database. This technique employed Peano scan method and Fourier Transformation to transfer 1D DNA nucleotide sequences into 2D far-field patterns. Then, PCA algorithm is used to extract features for effective DNA sequences retrieval. By combining proposed visualization and similarity search technologies, the functions and similarity of DNA sequences will be fast discriminated.

Chapter 1 Introduction ................................................. 1
1.1 Background ............................................. 1
1.2 Structure and Function of DNA .......................... 4
1.2.1 DNA Structure ................................... 4
1.2.2 Function of DNA ................................. 5
1.3 DNA Sequence Comparison................................ 5
1.3.1 Motivation ...................................... 5
1.3.2 Sequence Comparison ............................. 6
1.3.3 Conventional Method ............................. 7
1.4 Organization .......................................... 8
Chapter 2 Related Work ...................................... 9
2.1 Dynamic Programming ................................... 9
2.1.1 Alignment ...................................... 10
2.1.2 Needleman-Wunsch Algorithm ..................... 11
2.1.3 Smith-Waterman Algorithm ....................... 14
2.2 Digital Signal Processing Technique .................. 17
2.2.1 Numerical Mapping .............................. 17
2.2.2 Sequence Comparison ............................ 18
2.3 Visualization ........................................ 20
Chapter 3 Visualization by Pentahedrons Algorithm .......... 23
3.1 DNA Sequence Visualization ........................... 23
3.2 Proposed VBP Algorithm ............................... 23
3.2.1 Markov Chain Model for DNA Sequence ............ 24
3.2.2 Pentahedrons Mapping ........................... 25
3.2.3 Three-Dimensional Trajectory Plotting .......... 28
3.3 Experimental Result .................................. 30
3.4 Three Components of Trajectory ....................... 40
3.5 Discussion ........................................... 42
Chapter 4 Similarity Search through Content-Based Retrieval Technique ................................................... 44
4.1 Background ........................................... 44
4.2 Algorithm ............................................ 45
4.2.1 Combination of Peano Scan Algorithm with Fast Fourier Transformation ...................................... 47
4.2.2 Principle Component Analysis (PCA) ............. 55
4.2.3 Similarity Search .............................. 56
4.3 Simulation Result .................................... 57
4.4 Discussion ........................................... 58
Chapter 5 Conclusion .................................................. 61
References .................................................. 63

[1] Benjamin Lewin, Genes VII, OXFORD UNIVERSITY PRESS, 2000.
[2] S. B. Needleman and C. D. Wunsch, “A efficient method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of Molecular Biology, 48：443-453, 1970.
[3] Temple F. Smith and Michael S. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology, 147：195-197, 1981.
[4] E. A. Cheever, D. B. Searls, W. Karunaratne, and G. C. Overton, “Using signal processing techniques for DNA sequence comparison,” Bioengineering Conference, 1989. Proceedings of the 1989 Fifteenth Annual Northeast, pp. 173-174, 1989.
[5] D. Anastassiou, “DSP in genomics: processing and frequency -domain analysis of character strings,” IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 2, pp. 1053-1056, 2001.
[6] P. Cristea, “Genetic signal analysis,” Sixth International Symposium on Signal Processing and its Applications, Vol. 2, pp. 703-706, 2001.
[7] D. Anastassiou, “Genomic signal processing,” IEEE Signal Processing Magazine, Vol. 18, pp. 8-20, 2001.
[8] W. Wong, and D. H. Johnson, “Computing linear transforms of symbolic signals,” IEEE Transaction on Signal processing, Vol. 50, pp. 628-634, 2002.
[9] D. Wu, J. Roberge, D. J. Cork, B. G. Nguyen and T. Grace, “Computer visualization of long genomic sequence,” IEEE Visualization 93, p.p. 308-315, 1993.
[10] E. H.-H Chi, P. Barry, E. Shoop, J. V. Carlis, E. Retzel, and J. Ried, “Visualization of biological sequence similarity search results,” IEEE Visualization 95, pp. 44-51, 1995.
[11] H. H. Chi, J. Riedl, E. Shoop, J. V. Carlis, E. Retzel and P. Barry, “Flexible information visualization of multivariate data from biological sequence similarity searches,” IEEE Visualization 96, pp. 133-140, 1996.
[12] Richard Durbin, Sean R. Eddy, Anders Krogh and Graeme Mitchison, Biological sequence analysis, CAMBRIDGE UNIVERSITY PRESS, 1998.
[13] H. J. Jeffery, “Chaos game representation of genetic sequences,” Nucleic Acids Research, vol. 18, pp. 2163-2170, 1990.
[14] H. J. Jeffery, “Chaos game visualization of sequences,” Computer and Graphics, vol. 16, pp. 25-33, 1992.
[15] H. Williams and J. Zobel, “Indexing nucleotides databases for fast query evaluation,” Fifth International Conference on Extending Database Technology, pp. 275-288, 1996.
[16] W. Chen and K. Aberer, “Efficient querying on genomic databases by using metric space indexing techniques,” Proceedings of the Eighth International Workshop on Database and Expert Systems Applications, pp. 148-152, 1997.
[17] H. Williams and J. Zobel, “Indexing and retrieval for genomic databases,” IEEE Trans. On Knowledge and Data Engineering, Vol. 14, pp. 63-78, 2002.
[18] H. Matsuda, “Querying genomic database by using a parallel logic programming system on distributed computing environment,” Proceedings of the 1995 IEEE Pacific Rim Conference on Communication, Computers, and Signal Processing, pp. 333-336. 1995.
[19] K. M. Yang, L. Wu, and M. Mills, “Fractal based image coding scheme using Peano scan,” IEEE Internal Symposium on Circuits and Systems, Vol. 3, pp. 2301-2304, 1988.
[20] A. Ansari and A. Fineberg, “Image data compression and ordering using Peano scan and lot,” IEEE Trans. On Consumer Electronics, Vol. 38, pp. 436-445, 1992.
[21] Y. J. Yang and W. N. Lie, “Sort-scan predictive vector quantization on multispectral satellite images,” Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, Vol. 4, pp.191-194, 1999.
[22] M. Turk and A. Pentland, “Eigenfaces for recognition,” Journal of Cognitive Neuroscience, Vol. 3, pp. 71-86, 1991.
[23] D. A. Benson, I. Karsch-Mizrachi, D. J. Lipman, J. Ostell, B. A. Rapp and D. L. Wheeler, “GenBank,” Nucleic Acids Research, Vol. 30, pp. 17-20, 2002.