정렬된 잔기 사이의 최대거리와 유사도 그래프에 기반한 단백질 구조 정렬 = Protein Structure Alignment Based on Maximum of Residue Pair Distance and Similarity Graph

국문 초록 (Abstract)

최근 인간 게놈 프로젝트를 통해서 인간의 DNA가 해석된 이후 유전자가 생성하는 단백질의 기능에 대한 관심이 높아지고 있다. 단백질의 기능은 서열의 유사도보다는 진화과정 상에서 잘 보존되는 구조의 유사도에 더 연관되어 있다. 이를 통해 두 개의 단백질 간에 구조 유사성이 관찰되면 이로부터 이들이 유사한 생물학적 기능을 가질 것을 기대할 수 있다.
따라서 유사한 단백질 구조를 가진 단백질을 찾기 위한 방법으로 단백질 구조 정렬에 대한 많은 연구들이 진행되었다. 하지만 기존의 연구들은 유사도로 주로 RMSD(Root Mean Square Deviation)를 사용했기 때문에 두 단백질의 정렬 결과가 유사한지 혹은 유사하지 않은지를 직관적으로 판단하기 쉽지 않다. 또한 대부분의 기존 연구들은 정렬 결과로 최적의 정렬 결과 하나만을 찾기 때문에 서로 다른 목적을 가지는 사용자들을 만족시키기 어렵다. 따라서 본 논문에서는 새로운 유사도인 MRPD(Maximum of Residue Pair Distance)와 다수의 정렬 결과를 하나의 그래프로 표현하는 SG(Similarity Graph)을 기반으로 여러 가지 정렬 결과를 한 번에 생성하는 단백질 구조 정렬 방식을 제안한다. 단백질 정렬에 MRPD를 유사도로 사용하면 RMSD를 사용하는 경우에 비해서 유사 정도를 직관적으로 이해할 수 있을 뿐 아니라 신속하게 결과를 얻을 수 있다. SG는 사용자가 다양한 후보 정렬 결과들 중에서 자신이 원하는 정렬 결과를 신속히 검색할 수 있도록 지원한다. 따라서 본 논문에서 제안한 단백질 구조 정렬 알고리즘은 다양한 길이에 따른 다수의 최적 정렬들을 제시하여 사용자의 만족도를 향상시킬 수 있었으며, 다수의 정렬 결과 검색임에도 불구하고 정렬 시간은 기존 방법들과 거의 비슷하다는 장점이 있다.

다국어 초록 (Multilingual Abstract)

After the Human Genome Project finished the sequencing of a human DNA sequence, the concerns on protein functions are increasing. Since the structures of proteins are conserved in divergent evolution, their functions are determined by their structures rather than by their amino acid sequences. Therefore, if similarities between two protein structures are observed, we could expect them to have common biological functions. So far, a lot of researches on protein structure alignment have been performed. However, most of them use RMSD(Root Mean Square Deviation) as a similarity measure with which it is hard to judge the similarity level of two protein structures intuitively. In addition, they retrieve only one result having the highest alignment score with which it is hard to satisfy various users of different purpose. To overcome these limitations, we propose a novel protein structure alignment algorithm based on MRPD(Maximum of Residue Pair Distance) and SG (Similarity Graph). MRPD is more intuitive similarity measure by which fast filtering of unpromising pairs of protein pairs is possible, and SG is a compact representation method for multiple alignment results with which users can choose the most plausible one among various users’ needs by providing multiple alignment results without compromising the time to align protein structures.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 용어 정의
• 4. 유사도 그래프(Similarity Graph)
• 5. MRPD(Maximum of Residue Pair Distance)
• 6. 세부 알고리즘
• 7. 실험
• 8. 결론
• 참고문헌

참고문헌 (Reference)

• 1 C. Bron, "finding all cliques of an undirected graph Communications of the ACM" 16 : 575-457 577, 1973.
• 2 E. Tomita, "The worst-case time complexity for generating all maximal cliques" 161-170, 2004
• 3 J. F. Gibrat, "Surprising similarities in structure comparison" 6 (6): 377-385, 1996
• 4 P. E. Bourne, "Structural Bioinformatics" John Wiley & Sons Inc 2003
• 5 A. G. Murzin, "SCOP: a structural classification of proteins database for the investigation of sequences and structures" 247 : 536-540, 1995
• 6 "RCSB Protein Data Bank"
• 7 W. R. Taylor, "Protein structure comparison using iterated double dynamic programming" 8 : 654-665, 1999
• 8 L. Holm, "Protein structure comparison by alignment of distance matrices" 233 : 123-138, 1993
• 9 I. Eidhammer, "Protein structure comparison and structure patterns - an algorithmic approach" 2001
• 10 I. N. Shindyalov, "Protein structure alignment by incremental combinatorial extension (CE) of the optimal path" 11 (11): 739-747, 1998
• 11 L. Chen, "Protein structure alignment by deterministic annealing" 21 (21): 51-62, 2005
• 12 W. R. Taylor, "Protein structure alignment" 208 : 1-22, 1989.
• 13 M. A. Erdmann, "Protein Similarity from Knot Theory: Geometric Convolution and Line Weavings" 12 (12): 609-637, 2005
• 14 F. N. Abu-Khzam, "On the Relative Efficiency of Maximal Clique Enumeration Algorithms, with Applications to High-Throughput Computational Biology" 2005
• 15 F. S. Collins, "New Goals for the U.S. Human Genome Project: 1998-2003" 282 (282): 682-689, 1998
• 16 I. A. Jewett, "MINRMS: an efficient algorithm for determining protein structure similarity using root-mean- squared-distance" 19 (19): 625-634, 2003
• 17 K. S. Arun,T. S. Huang,and S. D. Blostein, "Least-squaresfitting of two 3-D point sets" pami-9 (pami-9): 698-700, 1987
• 18 D. Frishman, "Knowledge-based protein secondary structure assignment" 23 : 566-579, 1995
• 19 O. Camoglu, "Index- based Similarity Search for Protein Structure Databases" 2 (2): 99-126, 2004
• 20 V. Stix, "Finding all maximal cliques in dynamic graphs" 27 (27): 173 -186, 2004
• 21 R. Nussinov, "Efficient detection of three-dimensional structural motifs in biological macromolecules by computer vision techniques" 10495-10499, 1991.
• 22 W. Kabsch, "Dictionary of protein secondary structures pattern recognition of hydrogen-bonded and geometrical features" 22 : 2511-2631, 1983.
• 23 B. Dahiya, "De Novo protein design: fully automated sequence selection" 278 : 82-87, 1997
• 24 I. Lotan, "Approximation of Protein Structure for Fast Similarity Measures" 11 (11): 299 -317, 2004
• 25 L. Holm, "3-D lookup: Fast protein structure database searches at 90% reliability" 179-187, 1995