利用動態時間扭曲及最小二乘平差比對蛋白質結構

Dynamic Time Warping and Least Squares Adjustment for Protein tructure Alignment

蕭雯鴻(hsiao wên hung)

指導教授 ： 蕭翰文

亞洲大學/資訊學院/生物資訊學系碩士班/碩士(2006年)

摘要

在蛋白質的研究之中，蛋白質結構比對是很重要的一個部份。一般來說，蛋白質結構比對可以為兩個部份：整體比對與局部比對。在本研究之中，從原始的蛋白質結構之中取出了一維的特徵。其次混合了動態時間扭曲與最小二乘平差法做為整體蛋白質比對的基本步驟，並透過迭代的方式來求得比對結果。其中動態時間扭曲目的為找出蛋白質氨基酸的對應關係，動態時間扭曲則用以轉換座標並修正座標。利用比對中每一對應的氨基酸配對，計算出一權值來加速從粗略到精細比對的收斂。在結果之中，初步證實了對於整體比對的情況，本研究所使用的方法是有用且有效率的。然而，此方法對於比對的準確度及有
效的使用計算機的記憶體仍有改善的空間。

關鍵字

動態時間扭曲

並列摘要

Protein structure alignment is of importance in protein study. In general, such task can be divided into two categories, i.e. global and local structure alignment. In this paper, one-dimensional features are extracted first from the original protein structures. A hybrid approach combining dynamic time warping and least squares adjustment is proposed for global alignment of protein 3D structures in an iterative fashion, where dynamic time warping is responsible for coarse alignment of two structure and least squares adjustment handles the fine matching of amino acid residues. The residuals of matched pairs are utilized to calculate the weights to accelerate the convergence of coarse-to-fine matching. The preliminary results have demonstrated the effectiveness and efficiency of the proposed approach. However, there is still a room for improvement in terms of accuracy and memory usage.

並列關鍵字

Dynamic Time Warping

參考文獻

20. 陳尹, (2004), 以橢圓群集為基礎的蛋白質結構比對演算法之研究. 台灣大學資訊工程學碩士論文.

1. Needleman, S.B. and Wunsch, C.D., (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453.

2. Higgins, D. and Taylor, W., (2000). Bioinformatics: Sequence, Structure and Databanks: A Practical Approach. Oxford University Press.

3. Taylor, W.R. and Orengo, C.A., (1989). Protein structure alignment. Journal of Molecular Biology. 208(1), l-22.

4. Shindyalov, I.N. and Bourne, P.E., (1998). Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Engineering, 11(9). 739-747