Mitchell E M, Artymiuk P J, Rice D W, Willett P
Krebs Institute for Biomolecular Research, University of Sheffield, Western Bank, U.K.
J Mol Biol. 1990 Mar 5;212(1):151-66. doi: 10.1016/0022-2836(90)90312-A.
A substructure matching algorithm is described that can be used for the automatic identification of secondary structural motifs in three-dimensional protein structures from the Protein Data Bank. The proteins and motifs are stored for searching as labelled graphs, with the nodes of a graph corresponding to linear representations of helices and strands and the edges to the inter-line angles and distances. A modification of Ullman's subgraph isomorphism algorithm is described that can be used to search these graph representations. Tests with patterns from the protein structure literature demonstrate both the efficiency and the effectiveness of the search procedure, which has been implemented in FORTRAN 77 on a MicroVAX-II system, coupled to the molecular fitting program FRODO on an Evans and Sutherland PS300 graphics system.
本文描述了一种子结构匹配算法，该算法可用于从蛋白质数据库中自动识别三维蛋白质结构中的二级结构基序。蛋白质和基序以标记图的形式存储以供搜索，图的节点对应于螺旋和链的线性表示，边对应于线间角度和距离。本文还描述了对 Ullman 子图同构算法的一种修改，该修改算法可用于搜索这些图表示。使用来自蛋白质结构文献的模式进行的测试证明了搜索过程的效率和有效性，该过程已在 MicroVAX-II 系统上用 FORTRAN 77 实现，并与 Evans 和 Sutherland PS300 图形系统上的分子拟合程序 FRODO 相结合。
