Cut vertex method for identifying complex molecule substructures

Abstract

Embodiments of the present invention avoid the processing problems associated with using conventional computer systems for identifying and characterizing all of the substructures (e.g., metabolites) of large complex molecules by using a defined minimum cleavable unit (MCU) and an MCU graph for a chosen molecule, as well as a 'cut vertex' in the MCU graph for the chosen molecule. The system splits the MCU graph of the chosen molecule at the specified cut vertex to produce two separate MCU graph components (i.e., a first MCU subgraph and a second MCU subgraph) of the chosen molecule, and generates and traverses a first line graph component and a second line graph component, respectively, for the two MCU subgraph components with a graph traversing algorithm to generate and store in memory a first database of substructures and molecular weights for the first component, and a second database of substructures and molecular weights for the second line graph component. Subsequently, embodiments of the present invention can perform binary searches on the two databases (or the two subsections of a single database) to identify and produce graphic representations of all of the substructures of the chosen molecule that have molecular weights that match the query molecular weight (or range of query molecular weights), including the substructures of the chosen molecule that straddle (i.e., include) the cut vertex.