Enumerating Tree-Like Graphs and Polymer Topologies with a Given Cycle Rank
Open Access
Abstract
Cycle rank is an important notion that is widely used to classify, understand, and discover new chemical compounds. We propose a method to enumerate all non-isomorphic tree-like graphs of a given cycle rank with self-loops and no multiple edges. To achieve this, we develop an algorithm to enumerate all non-isomorphic rooted graphs with the required constraints. The idea of our method is to define a canonical representation of rooted graphs and enumerate all non-isomorphic graphs by generating the canonical representation of rooted graphs. An important feature of our method is that for an integer , it generates all required graphs with n vertices in time per graph and space in total, without generating invalid intermediate structures. We performed some experiments to enumerate graphs with a given cycle rank from which it is evident that our method is efficient. As an application of our method, we can generate tree-like polymer topologies of a given cycle rank with self-loops and no multiple edges.
Keywords
This publication has 17 references indexed in Scilit:
- U1 snRNP regulates cancer cell migration and invasion in vitroNature Communications, 2020
- De novo generation of hit-like molecules from gene expression signatures using artificial intelligenceNature Communications, 2020
- A novel method to construct NSSD molecular graphsOpen Mathematics, 2019
- Scaffold-based molecular design with a graph generative modelChemical Science, 2019
- Efficient enumeration of monocyclic chemical graphs with given path frequenciesJournal of Cheminformatics, 2014
- Small Molecule Identification with MOLGEN and Mass SpectrometryMetabolites, 2013
- OMG: Open Molecule GeneratorJournal of Cheminformatics, 2012
- 970 Million Druglike Small Molecules for Virtual Screening in the Chemical Universe Database GDB-13Journal of the American Chemical Society, 2009
- Enumerating Treelike Chemical Graphs with Given Path FrequencyJournal of Chemical Information and Modeling, 2008
- Topological polymer chemistryProgress in Polymer Science, 2002