Representation and searching of carbohydrate structures using graph-theoretic techniques.
This paper describes how the carbohydrate structures in the Complex Carbohydrate Structure Database (CCSD) can be represented by labelled graphs, in which the nodes and edges of a graph are used to denote the residues and the inter-residue linkages, respectively, of a carbohydrate. These graph representations are then searched with a subgraph-isomorphism algorithm. We describe the use of one such algorithm, that due to Ullmann, and demonstrate that it provides a very precise way of searching the structures in CCSD. We also describe the use of screening techniques that can eliminate many of the CCSD structures from the subgraph-isomorphism search, with a consequent increase in the speed of the search.
Bruno
I J
IJ
Krebs Institute for Biomolecular Research, Department of Information Studies, University of Sheffield, UK.
Kemp
N M
NM
Artymiuk
P J
PJ
Willett
P
P
D000465:Algorithms; D002236:Carbohydrate Conformation; D002240:Carbohydrate Sequence; D002241:Carbohydrates / Q000737:chemistry*; D003196:Computer Graphics; D003201:Computers; D016208:Databases, Factual; D016247:Information Storage and Retrieval; D008969:Molecular Sequence Data; D015394:Molecular Structure; D009844:Oligosaccharides / Q000737:chemistry; D012984:Software
D002241:Carbohydrates; D009844:Oligosaccharides