Cerruela García G, Luque Ruiz I, Gómez-Nieto MA. Cyclical conjunction: an efficient operator for the extraction of cycles from a graph.
JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES 2002;
42:1415-24. [PMID:
12444739 DOI:
10.1021/ci020373e]
[Citation(s) in RCA: 1] [Impact Index Per Article: 0.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/30/2022]
Abstract
The structural characteristics of a molecule, namely size, bond type and number, cycles, shape, and functional groups, will largely determine its physicochemical properties and biological activity. Extraction of data such as the complete structural information of a molecule's ring system is complex (NP-complete) and has traditionally involved high computational cost. The present study proposes a new operator for the extraction of cycles from a graph. Based on an initial cycle set, the operator employs a reduced number of operations in an iterative process of error-free cycle extraction, hence greatly reducing computational cost. Algorithm efficiency has been enhanced by designing new data structures suited to cycle storage, useful not only for interactive solutions but also for applications managing large volumes of information such as descriptor calculation, QSPR/QSAR, matching, clustering, screening, and filtering. Validation was performed by applying the algorithm to a test suite of chemical compounds of varying complexity.
Collapse