Bruno IJ, Kemp NM, Artymiuk PJ, Willett P. Representation and searching of carbohydrate structures using graph-theoretic techniques.
Carbohydr Res 1997;
304:61-7. [PMID:
9403995 DOI:
10.1016/s0008-6215(97)00196-1]
[Citation(s) in RCA: 10] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/05/2023]
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.
Collapse