Graph theoretic methods for the analysis of structural relationships in biological macromolecules

被引:22
作者
Artymiuk, PJ
Spriggs, RV
Willett, P
机构
[1] Univ Sheffield, Krebs Inst Biomolec Res, Sheffield S10 2TN, S Yorkshire, England
[2] Univ Sheffield, Dept Mol Biol & Biotechnol, Sheffield S10 2TN, S Yorkshire, England
[3] Univ Sheffield, Dept Informat Studies, Sheffield S10 2TN, S Yorkshire, England
来源
JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY | 2005年 / 56卷 / 05期
关键词
D O I
10.1002/asi.20140
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Subgraph isomorphism and maximum common subgraph isomorphism algorithms from graph theory provide an effective and an efficient way of identifying structural relationships between biological macromolecules. They thus provide a natural complement to the pattern matching algorithms that are used in bioinformatics to identify sequence relationships. Examples are provided of the use of graph theory to analyze proteins for which three-dimensional crystallographic or NMR structures are available, focusing on the use of the Bron-Kerbosch clique detection algorithm to identify common folding motifs and of the Ullmann subgraph isomorphism algorithm to identify patterns of amino acid residues. Our methods are also applicable to other types of biological macromolecule, such as carbohydrate and nucleic acid structures.
引用
收藏
页码:518 / 528
页数:11
相关论文
共 73 条
[1]   BASIC LOCAL ALIGNMENT SEARCH TOOL [J].
ALTSCHUL, SF ;
GISH, W ;
MILLER, W ;
MYERS, EW ;
LIPMAN, DJ .
JOURNAL OF MOLECULAR BIOLOGY, 1990, 215 (03) :403-410
[2]  
[Anonymous], MOL SIMILARITY DRUG
[3]  
[Anonymous], 1983, CHEM GRAPH THEORY
[4]   STRUCTURAL RESEMBLANCE BETWEEN THE FAMILIES OF BACTERIAL SIGNAL-TRANSDUCTION PROTEINS AND OF G-PROTEINS REVEALED BY GRAPH THEORETICAL TECHNIQUES [J].
ARTYMIUK, PJ ;
RICE, DW ;
MITCHELL, EM ;
WILLETT, P .
PROTEIN ENGINEERING, 1990, 4 (01) :39-43
[5]  
Artymiuk PJ, 1997, NATURE, V388, P33, DOI 10.1038/40310
[6]   Biotin carboxylase comes into the fold [J].
Artymiuk, PJ ;
Poirrette, AR ;
Rice, DW ;
Willett, P .
NATURE STRUCTURAL BIOLOGY, 1996, 3 (02) :128-132
[7]   IDENTIFICATION OF BETA-SHEET MOTIFS, OF PSI-LOOPS, AND OF PATTERNS OF AMINO-ACID-RESIDUES IN 3-DIMENSIONAL PROTEIN STRUCTURES USING A SUBGRAPH-ISOMORPHISM ALGORITHM [J].
ARTYMIUK, PJ ;
GRINDLEY, HM ;
POIRRETTE, AR ;
RICE, DW ;
UJAH, EC ;
WILLETT, P .
JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1994, 34 (01) :54-62
[8]   A GRAPH-THEORETIC APPROACH TO THE IDENTIFICATION OF 3-DIMENSIONAL PATTERNS OF AMINO-ACID SIDE-CHAINS IN PROTEIN STRUCTURES [J].
ARTYMIUK, PJ ;
POIRRETTE, AR ;
GRINDLEY, HM ;
RICE, DW ;
WILLETT, P .
JOURNAL OF MOLECULAR BIOLOGY, 1994, 243 (02) :327-344
[9]   SUBSTRUCTURE SEARCHING METHODS - OLD AND NEW [J].
BARNARD, JM .
JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1993, 33 (04) :532-538
[10]  
BAXEVANIS AD, 2001, BIOINFORMATICS