REPRESENTATION AND SEARCHING OF CARBOHYDRATE STRUCTURES USING GRAPH-THEORETIC TECHNIQUES

This paper describes how the carbohydrate structures in the Complex Ca rbohydrate Structure Database (CCSD) can be represented by labelled gr aphs, in which the nodes and edges of a graph are used to denote the r esidues and the inter-residue linkages, respectively, of a carbohydrat e. These graph representations are then searched with a subgraph-isomo rphism algorithm. We describe the use of one such algorithm, that due to Ullmann, and demonstrate that it provides a very precise way of sea rching the structures in CCSD. We also describe the use of screening t echniques that can eliminate many of the CCSD structures from the subg raph-isomorphism search, with a consequent increase in the speed of th e search. (C) 1997 Elsevier Science Ltd.