Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Chemical graph generator
A chemical graph generator is a software package to generate computer representations of chemical structures adhering to certain boundary conditions. The development of such software packages is a research topic of cheminformatics. Chemical graph generators are used in areas such as virtual library generation in drug design, in molecular design with specified properties, called inverse QSAR/QSPR, as well as in organic synthesis design, retrosynthesis or in systems for computer-assisted structure elucidation (CASE). CASE systems again have regained interest for the structure elucidation of unknowns in computational metabolomics, a current area of computational biology.
Molecular structure generation is a branch of graph generation problems. Molecular structures are graphs with chemical constraints such as valences, bond multiplicity and fragments. These generators are the core of CASE systems. In a generator, the molecular formula is the basic input. If fragments are obtained from the experimental data, they can also be used as inputs to accelerate structure generation. The first structure generators were versions of graph generators modified for chemical purposes. One of the first structure generators was CONGEN, originally developed for the DENDRAL project, the first artificial intelligence project in organic chemistry. DENDRAL was developed as a part of the Mariner program launched by the NASA to search for life on Mars. CONGEN dealt well with overlaps in substructures. The overlaps among substructures rather than atoms were used as the building blocks. For the case of stereoisomers, symmetry group calculations were performed for duplicate detection.
After DENDRAL, another mathematical method, MASS, a tool for mathematical synthesis and analysis of molecular structures, was reported. As with CONGEN, the MASS algorithm worked as an adjacency matrix generator. Many mathematical generators are descendants of efficient branch-and-bound methods from Igor Faradjev and Ronald C. Read's orderly generation method. Although their reports are from the 1970s, these studies are still the fundamental references for structure generators. In the orderly generation method, specific order-check functions are performed on graph representatives, such as vectors. For example, MOLGEN performs a descending order check while filling rows of adjacency matrices. This descending order check is based on an input valence distribution. The literature classifies generators into two major types: structure assembly and structure reduction. The algorithmic complexity and the run time are the criteria used for comparison.
The generation process starts with a set of atoms from the molecular formula. In structure assembly, atoms are combinatorically connected to consider all possible extensions. If substructures are obtained from the experimental data, the generation starts with these substructures. These substructures provide known bonds in the molecule. One of the earliest attempts was made by Hidetsugu Abe in 1975 using a pattern recognition-based structure generator. The algorithm had two steps: first, the prediction of the substructure from low-resolution spectral data; second, the assembly of these substructures based on a set of construction rules. Hidetsugu Abe and the other contributors published the first paper on CHEMICS, which is a CASE tool comprising several structure generation methods. The program relies on a predefined non-overlapping fragment library. CHEMICS generates different types of component sets ranked from primary to tertiary based on component complexity. The primary set contains atoms, i.e., C, N, O and S, with their hybridization. The secondary and tertiary component sets are built layer-by-layer starting with these primary components. These component sets are represented as vectors and are used as building blocks in the process.
Substantial contributions were made by Craig Shelley and Morton Munk, who published a large number of CASE papers in this field. The first of these papers reported a structure generator, ASSEMBLE. The algorithm is considered one of the earliest assembly methods in the field. As the name indicates, the algorithm assembles substructures with overlaps to construct structures. ASSEMBLE overcomes overlapping by including a "neighbouring atom tag". The generator is purely mathematical and does not involve the interpretation of any spectral data. Spectral data are used for structure scoring and substructure information. Based on the molecular formula, the generator forms bonds between pairs of atoms, and all the extensions are checked against the given constraints. If the process is considered as a tree, the first node of the tree is an atom set with substructures if any are provided by the spectral data. By extending the molecule with a bond, an intermediate structure is built. Each intermediate structure can be represented by a node in the generation tree. ASSEMBLE was developed with a user-friendly interface to facilitate use. The second version of ASSEMBLE was released in 2000. Another assembly method is GENOA. Compared to ASSEMBLE and many other generators, GENOA is a constructive substructure search-based algorithm, and it assembles different substructures by also considering the overlaps.
The efficiency and exhaustivity of generators are also related to the data structures. Unlike previous methods, AEGIS was a list-processing generator. Compared to adjacency matrices, list data requires less memory. As no spectral data was interpreted in this system, the user needed to provide substructures as inputs. Structure generators can also vary based on the type of data used, such as HMBC, HSQC and other NMR data. LUCY is an open-source structure elucidation method based on the HMBC data of unknown molecules, and involves an exhaustive 2-step structure generation process where first all combinations of interpretations of HMBC signals are implemented in a connectivity matrix, which is then completed by a deterministic generator filling in missing bond information. This platform could generate structures with any arbitrary size of molecules; however, molecular formulas with more than 30 heavy atoms are too time consuming for practical applications. This limitation highlighted the need for a new CASE system. SENECA was developed to eliminate the shortcomings of LUCY. To overcome the limitations of the exhaustive approach, SENECA was developed as a stochastic method to find optimal solutions. The systems comprise two stochastic methods: simulated annealing and genetic algorithms. First, a random structure is generated; then, its energy is calculated to evaluate the structure and its spectral properties. By transforming this structure into another structure, the process continues until the optimum energy is reached. In the generation, this transformation relies on equations based on Jean-Loup Faulon's rules. LSD (Logic for Structure Determination) is an important contribution from French scientists. The tool uses spectral data information such as HMBC and COSY data to generate all possible structures. LSD is an open source structure generator released under the General Public License (GPL). A well-known commercial CASE system, StrucEluc, also features a NMR based generator. This tool is from ACD Labs and, notably, one of the developers of MASS, Mikhail Elyashberg. COCON is another NMR based structure generator, relying on theoretical data sets for structure generation. Except J-HMBC and J-COSY, all NMR types can be used as inputs.
In 1994, Hu and Xu reported an integer partition-based structure generator. The decomposition of the molecular formula into fragments, components and segments was performed as an application of integer partitioning. These fragments were then used as building blocks in the structure generator. This structure generator was part of a CASE system, ESESOC.
A series of stochastic generators was reported by Jean-Loup Faulon. The software, MOLSIG, was integrated into this stochastic generator for canonical labelling and duplicate checks. As for many other generators, the tree approach is the skeleton of Jean-Loup Faulon's structure generators. However, considering all possible extensions leads to a combinatorial explosion. Orderly generation is performed to cope with this exhaustivity. Many assembly algorithms, such as OMG, MOLGEN and Jean-Loup Faulon's structure generator, are orderly generation methods. Jean-Loup Faulon's structure generator relies on equivalence classes over atoms. Atoms with the same interaction type and element are grouped in the same equivalence class. Rather than extending all atoms in a molecule, one atom from each class is connected with other atoms. Similar to the former generator, Julio Peironcely's structure generator, OMG, takes atoms and substructures as inputs and extends the structures using a breadth-first search method. This tree extension terminates when all the branches reach saturated structures.
Hub AI
Chemical graph generator AI simulator
(@Chemical graph generator_simulator)
Chemical graph generator
A chemical graph generator is a software package to generate computer representations of chemical structures adhering to certain boundary conditions. The development of such software packages is a research topic of cheminformatics. Chemical graph generators are used in areas such as virtual library generation in drug design, in molecular design with specified properties, called inverse QSAR/QSPR, as well as in organic synthesis design, retrosynthesis or in systems for computer-assisted structure elucidation (CASE). CASE systems again have regained interest for the structure elucidation of unknowns in computational metabolomics, a current area of computational biology.
Molecular structure generation is a branch of graph generation problems. Molecular structures are graphs with chemical constraints such as valences, bond multiplicity and fragments. These generators are the core of CASE systems. In a generator, the molecular formula is the basic input. If fragments are obtained from the experimental data, they can also be used as inputs to accelerate structure generation. The first structure generators were versions of graph generators modified for chemical purposes. One of the first structure generators was CONGEN, originally developed for the DENDRAL project, the first artificial intelligence project in organic chemistry. DENDRAL was developed as a part of the Mariner program launched by the NASA to search for life on Mars. CONGEN dealt well with overlaps in substructures. The overlaps among substructures rather than atoms were used as the building blocks. For the case of stereoisomers, symmetry group calculations were performed for duplicate detection.
After DENDRAL, another mathematical method, MASS, a tool for mathematical synthesis and analysis of molecular structures, was reported. As with CONGEN, the MASS algorithm worked as an adjacency matrix generator. Many mathematical generators are descendants of efficient branch-and-bound methods from Igor Faradjev and Ronald C. Read's orderly generation method. Although their reports are from the 1970s, these studies are still the fundamental references for structure generators. In the orderly generation method, specific order-check functions are performed on graph representatives, such as vectors. For example, MOLGEN performs a descending order check while filling rows of adjacency matrices. This descending order check is based on an input valence distribution. The literature classifies generators into two major types: structure assembly and structure reduction. The algorithmic complexity and the run time are the criteria used for comparison.
The generation process starts with a set of atoms from the molecular formula. In structure assembly, atoms are combinatorically connected to consider all possible extensions. If substructures are obtained from the experimental data, the generation starts with these substructures. These substructures provide known bonds in the molecule. One of the earliest attempts was made by Hidetsugu Abe in 1975 using a pattern recognition-based structure generator. The algorithm had two steps: first, the prediction of the substructure from low-resolution spectral data; second, the assembly of these substructures based on a set of construction rules. Hidetsugu Abe and the other contributors published the first paper on CHEMICS, which is a CASE tool comprising several structure generation methods. The program relies on a predefined non-overlapping fragment library. CHEMICS generates different types of component sets ranked from primary to tertiary based on component complexity. The primary set contains atoms, i.e., C, N, O and S, with their hybridization. The secondary and tertiary component sets are built layer-by-layer starting with these primary components. These component sets are represented as vectors and are used as building blocks in the process.
Substantial contributions were made by Craig Shelley and Morton Munk, who published a large number of CASE papers in this field. The first of these papers reported a structure generator, ASSEMBLE. The algorithm is considered one of the earliest assembly methods in the field. As the name indicates, the algorithm assembles substructures with overlaps to construct structures. ASSEMBLE overcomes overlapping by including a "neighbouring atom tag". The generator is purely mathematical and does not involve the interpretation of any spectral data. Spectral data are used for structure scoring and substructure information. Based on the molecular formula, the generator forms bonds between pairs of atoms, and all the extensions are checked against the given constraints. If the process is considered as a tree, the first node of the tree is an atom set with substructures if any are provided by the spectral data. By extending the molecule with a bond, an intermediate structure is built. Each intermediate structure can be represented by a node in the generation tree. ASSEMBLE was developed with a user-friendly interface to facilitate use. The second version of ASSEMBLE was released in 2000. Another assembly method is GENOA. Compared to ASSEMBLE and many other generators, GENOA is a constructive substructure search-based algorithm, and it assembles different substructures by also considering the overlaps.
The efficiency and exhaustivity of generators are also related to the data structures. Unlike previous methods, AEGIS was a list-processing generator. Compared to adjacency matrices, list data requires less memory. As no spectral data was interpreted in this system, the user needed to provide substructures as inputs. Structure generators can also vary based on the type of data used, such as HMBC, HSQC and other NMR data. LUCY is an open-source structure elucidation method based on the HMBC data of unknown molecules, and involves an exhaustive 2-step structure generation process where first all combinations of interpretations of HMBC signals are implemented in a connectivity matrix, which is then completed by a deterministic generator filling in missing bond information. This platform could generate structures with any arbitrary size of molecules; however, molecular formulas with more than 30 heavy atoms are too time consuming for practical applications. This limitation highlighted the need for a new CASE system. SENECA was developed to eliminate the shortcomings of LUCY. To overcome the limitations of the exhaustive approach, SENECA was developed as a stochastic method to find optimal solutions. The systems comprise two stochastic methods: simulated annealing and genetic algorithms. First, a random structure is generated; then, its energy is calculated to evaluate the structure and its spectral properties. By transforming this structure into another structure, the process continues until the optimum energy is reached. In the generation, this transformation relies on equations based on Jean-Loup Faulon's rules. LSD (Logic for Structure Determination) is an important contribution from French scientists. The tool uses spectral data information such as HMBC and COSY data to generate all possible structures. LSD is an open source structure generator released under the General Public License (GPL). A well-known commercial CASE system, StrucEluc, also features a NMR based generator. This tool is from ACD Labs and, notably, one of the developers of MASS, Mikhail Elyashberg. COCON is another NMR based structure generator, relying on theoretical data sets for structure generation. Except J-HMBC and J-COSY, all NMR types can be used as inputs.
In 1994, Hu and Xu reported an integer partition-based structure generator. The decomposition of the molecular formula into fragments, components and segments was performed as an application of integer partitioning. These fragments were then used as building blocks in the structure generator. This structure generator was part of a CASE system, ESESOC.
A series of stochastic generators was reported by Jean-Loup Faulon. The software, MOLSIG, was integrated into this stochastic generator for canonical labelling and duplicate checks. As for many other generators, the tree approach is the skeleton of Jean-Loup Faulon's structure generators. However, considering all possible extensions leads to a combinatorial explosion. Orderly generation is performed to cope with this exhaustivity. Many assembly algorithms, such as OMG, MOLGEN and Jean-Loup Faulon's structure generator, are orderly generation methods. Jean-Loup Faulon's structure generator relies on equivalence classes over atoms. Atoms with the same interaction type and element are grouped in the same equivalence class. Rather than extending all atoms in a molecule, one atom from each class is connected with other atoms. Similar to the former generator, Julio Peironcely's structure generator, OMG, takes atoms and substructures as inputs and extends the structures using a breadth-first search method. This tree extension terminates when all the branches reach saturated structures.