title: Representation and searching of carbohydrate structures using graph-theoretic techniques.
abstract: 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.
authors.affiliation: Krebs Institute for Biomolecular Research, Department of Information Studies, University of Sheffield, UK.
authors.forename: I J
authors.initials: IJ
authors.lastname: Bruno
authors.forename: N M
authors.initials: NM
authors.lastname: Kemp
authors.forename: P J
authors.initials: PJ
authors.lastname: Artymiuk
authors.forename: P
authors.initials: P
authors.lastname: Willett
mesh_terms: 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
chemical_list: D002241:Carbohydrates; D009844:Oligosaccharides