EuroMUG '04: GENSMI: Exhaustive Enumeration of Simple Graphs

EuroMUG '04 -- 4 - 5 Nov, 2004

GENSMI: Exhaustive Enumeration of Simple Graphs

Michael A. Kappler
Daylight CIS, Inc.

ABSTRACT

An algorithm has been created to generate all possible simple graphs (no atom or bond types). Topological indices are used to characterize frameworks and select "drug-like" scaffolds. As a result of processing a massive data set, Daylight tools have improved.

Motivation

At EuroMUG '03, a challenge was offered ``to construct all possible compounds containing carbon, nitrogen, and oxygen with a molecular weight between 150 and 250.'' Such a challenge arises from the exploratory nature of drug discovery endeavors such as the "Screensaver Lifesaver" project, a community effort aimed at discovery of new drug candidates and involves over a 2.5 million computers, 3.5 billion molecules and 16 protein targets. Motivation stems from the implied fact that the challenge hasn't been done before, and the possibility to suggest new "drug-like" candidates. To rise to the challenge of the latter, a collaboration was initiated between people at Daylight and the University of New Mexico School of Medicine.

Introduction

Counting

Enumeration of molecules has been studied for over a century and continues to be an active area of research.
Initial efforts involved determining the number molecules that satisfy a set of constraints, referred to as counting.
The notion of a tree opened the door to the first solutions in counting of paraffin structures. Advances have lead to mathematical equations still in use today.

Enumerating

Advances in computer technology have enabled explicitly naming of molecules, referred to as enumerating.
Early efforts involved exhaustive generation of small organic isomers given an empirical formula, such as C₆H₆ and C₆H₆O.
As technology advanced, larger acyclic, cyclic, and mixed compounds were enumerated.
More recent work included generating isomers from fragments, using constraints during generation and specific handling of certain compound classes, such as spiro compounds and polyhex and fusene hydrocarbons.
The typical approach to enumerating chemical structures has been based on constructive assembly.
Other approaches include forming a hypergraph followed by destructive reduction or a combination of assembly and reduction.
A relatively new method uses a convergent approach to enumeration.
All approaches ultimately face the same reality: chemical space is vast.

Sampling

In order to explore the realm of possibilities, stochastic algorithms have been used to survey chemical space, referred to as sampling.
Enumeration techniques have involved simulated annealing genetic programming, and symmetry information.
Certainly, there has been much work in the field of counting, enumerating, and sampling chemical space.
For a more complete description of the field of enumerating molecules, the authors direct the reader to a current review.

Duplication

Enumeration has unavoidably involved duplication. So, a canonical structural notation has been an important and necessary convention for identifying isomorphic graphs, and removing them. Without such a notation, the majority of generated compounds, especially cyclic compounds, will be redundant.
A landmark algorithm for canonical coding was a graph-based description and was extended for stereochemistry.
Various other techniques for isomorphic identification exist.

Applications

A common application of enumeration algorithms have been aimed at structure elucidation, and this is changing.
Given technology advances in the last decade, we're seeing the role of the computer become more prevalent in all aspects of drug discovery.
Specifically, enumerations algorithms have been aimed at creating new ideas of potential pharmaceutical interest. Efforts have involved constraints to bias results toward ``lead-like'' or ``drug-like'' molecules.
Enumeration of small molecules appear positioned to serve as a resource and mitigate the estimated $897M required to bring a new medicine into the market, especially when used in conjunction with prediction of properties, evaluation of complexity, and selectivity, virtually screening, and synthetic accessibility.

Goals

Exhaustively enumerating small molecules by treating them as simple graphs. A simple graph is a nonempty set of elements, called vertices, and a set of distinct pairs of elements, called edges. The translation of simple graphs into chemistry is acyclic and cyclic hydrocarbons.
Perform "Stress Testing" of Daylight tools by processing a huge dataset.
Characterize the graphs and compare to existing databases.
Select graphs for promotion to multigraphs (bond orders, unsaturation) and colored graphs (atom types, molecules).

Methods

A constructive algorithm was developed to assemble simple graphs by adding (and removing) one vertex and one edge at a time, called orderly generation. The algorithm proceeds as follows:


 1 Routine: Main
 2 G <- NewGraph(1,0)
 3 Output(G)
 4 Enumerate-Vertices(G,1)
 5 done
 6
 7 Routine: EnumerateVertices(G,k)
 8 set <- SelectVertices(G,k)
 9 for i <- set[1], ... set[m]
10   if AcceptableVertex(G,i)
11     G <- AddVertex(G,i)
12     if GraphIsUnique(G)
13       Output(G)
14       EnumerateEdge(G,i)
15       EnumerateVertices(G,i)
16     end
17     G <- RemoveVertex(G,i)
18   end
19 end
20 return
21
22 Routine: EnumerateEdges(G,k)
23 setA <- SelectVertices(G,k)
24 setB <- SelectVertices2(G,k)
25 for i <- setA[1], ... setA[m]
26   for j <- setB[1], ... setB[n]
27     if AcceptableEdge(G,i,j)
28       G <- AddEdge(G,i,j)
29       if GraphIsUnique(G)
30         Output(G)
31         EnumerateEdges(G,i)
32       end
33       G <- RemoveEdge(G,i,j)
34     end
35   end
36 end
37 return

Algorithm Description

Graphs are enumerated by systematic assembly of acyclic graphs, and as they are constructed, each one is used to enumerate cyclic graphs. The algorithm begins by connecting a vertex to a graph in all possible ways, resulting in a set of acyclic graphs, one of which is G. As each acyclic graph is constructed, an edge is added in all possible ways resulting in set of monocyclic graphs. As each monocyclic graph is constructed, an edge is added in all possible ways resulting in a set of bicyclic graphs, and so on, until constraints are violated. Eventually, the algorithm enumerates all cyclic graphs based on G. Then, another vertex is connected in all possible ways, resulting in a new set of acyclic graphs, one of which is G'. As each G' is constructed, it is treated as G and the process recurs until constraints are violated. Eventually, the algorithm enumerates all acyclic graphs based on G. This implementation enumerates acyclic branched graphs before linear ones. For example, neopentane and 2,2-dimethylbutane occur early in the enumeration and n-pentane and n-hexane occur late.

Use of Symmetry

The algorithm utilizes symmetry classification of vertices to avoid generating duplicates by operating on only one vertex of a class.
For example, a graph with 2 vertices and 1 edge has one unique vertex. Both vertices have the same symmetry classification, therefore, one is arbitrarily selected and the other is discarded.
Perception of graph symmetry avoids duplication unless a graph is asymmetric.

Order of Vertices and Edges

The algorithm uses the lexicographic order of operations to avoid generating duplicates.
For example, it is equivalent to add a vertex, one to i then j, as it is to add to j then i.
For example, it is equivalent to connect vertex i to j as it is to connect j to i.

Use of Constraints

The number of edges attached to a vertex defines the degree of the vertex.
Interest is in vertices of degree 1 to 4.
The number of times an edge occurs in a graph defines the multiplicity of an edge.
All edges in a simple graph have multiplicity 1.
Further, interest is in graphs that are connected, in other words, in one piece.
There is no interest in graphs that contain a loop edge, namely an edge connecting a vertex to itself.

From Graph Theory to Chemistry

Using these constraints, a simple graph may be represented as a molecule.
The vertex degree corresponds to the valence of carbon.
The edge multiplicity corresponds to a single bond.
The connected graph corresponds to one component, in other words, no mixtures.
The loop edge corresponds to a radical or charged species.
Given these translations, an algorithm was created using the Daylight Toolkit and output the names using the SMILES Language.

Results and Discussion

Table 1: Number of Simple Graphs with a Given Vertex and Cycle Count Exhaustive Enumeration
Cycles 0 1 2 3 4 5 6 7 8 1 1 2 1 3 1 1 4 2 2 1 1 5 3 5 5 4 2 1 1 6 5 12 17 18 14 8 3 1 V 7 9 29 56 79 79 59 31 9 2 e 8 18 73 182 326 430 427 298 134 35 r 9 35 185 573 1,278 2,161 2,768 2,616 1,714 707 t 10 75 475 1,792 4,875 10,162 16,461 20,346 18,436 11,477 i 11 159 1,231 5,533 17,978 45,282 90,111 140,605 167,702 146,427 c 12 355 3,232 16,977 64,720 192,945 460,699 880,737 1,327,242 1,530,906 e 13 802 8,506 51,652 227,842 790,849 2,222,549 5,082,279 9,372,118 13,663,758 s 14 1,858 22,565 156,291 787,546 3,138,808 10,216,607 27,402,524 60,319,259 15 4,347 60,077 470,069 2,678,207 12,116,550 45,076,266 139,571,729 16 10,359 160,629 1,407,264 8,982,754 45,675,153 17 24,894 430,724 4,193,977 29,761,361 18 60,523 1,158,502 12,451,760 97,557,854 19 148,284 3,122,949 36,838,994 20 366,319 8,437,289 102,733,261 Total=834,181,624

Table 1: Number of Simple Graphs with a Given Vertex and Cycle Count
Exhaustive Enumeration


                                                         Cycles
             0          1            2           3           4           5          6            7         8

    1        1
    2        1
    3        1          1
    4        2          2            1           1
    5        3          5            5           4           2           1           1
    6        5         12           17          18          14           8           3          1
V   7        9         29           56          79          79          59          31          9          2
e   8       18         73          182         326         430         427         298        134         35
r   9       35        185          573       1,278       2,161       2,768       2,616      1,714        707
t  10       75        475        1,792       4,875      10,162      16,461      20,346     18,436     11,477
i  11      159      1,231        5,533      17,978      45,282      90,111     140,605    167,702    146,427
c  12      355      3,232       16,977      64,720     192,945     460,699     880,737  1,327,242  1,530,906
e  13      802      8,506       51,652     227,842     790,849   2,222,549   5,082,279  9,372,118 13,663,758
s  14    1,858     22,565      156,291     787,546   3,138,808  10,216,607  27,402,524 60,319,259
   15    4,347     60,077      470,069   2,678,207  12,116,550  45,076,266 139,571,729
   16   10,359    160,629    1,407,264   8,982,754  45,675,153
   17   24,894    430,724    4,193,977  29,761,361
   18   60,523  1,158,502   12,451,760  97,557,854
   19  148,284  3,122,949   36,838,994
   20  366,319  8,437,289  102,733,261

 Total=834,181,624

Table 2: Number of Simple Graphs with a Given Vertex and Cycle Count World Drug Index 2004.2 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 0 1 113 2 120 3 78 3 4 109 0 0 0 5 183 13 0 0 0 0 0 6 215 48 0 0 0 0 0 0 V 7 199 71 3 0 0 0 0 0 0 e 8 200 151 5 0 0 0 0 0 0 0 r 9 209 219 18 1 0 0 0 0 0 0 t 10 236 324 83 3 0 0 0 0 0 0 i 11 248 428 146 11 0 0 0 0 0 0 c 12 196 518 215 13 1 0 0 0 0 0 e 13 171 500 294 42 0 0 0 0 0 0 s 14 207 526 448 105 1 0 0 0 0 0 15 145 508 482 168 3 0 0 0 0 0 16 151 514 579 307 13 1 0 0 0 0 17 111 439 748 380 34 0 0 0 0 0 18 87 387 812 515 91 1 0 0 0 0 19 113 330 765 672 121 5 0 0 0 0 20 127 306 791 770 200 25 0 1 0 0 21+ 1335 3051 7146 11568 10773 6133 2746 1562 874 1509 Total=64073 Subset(20/8)=17376 (27.1%)

Table 2: Number of Simple Graphs with a Given Vertex and Cycle Count
World Drug Index 2004.2 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0       0
    1     113
    2     120
    3      78       3
    4     109       0       0       0
    5     183      13       0       0       0       0       0
    6     215      48       0       0       0       0       0       0
V   7     199      71       3       0       0       0       0       0       0
e   8     200     151       5       0       0       0       0       0       0       0
r   9     209     219      18       1       0       0       0       0       0       0
t  10     236     324      83       3       0       0       0       0       0       0
i  11     248     428     146      11       0       0       0       0       0       0
c  12     196     518     215      13       1       0       0       0       0       0
e  13     171     500     294      42       0       0       0       0       0       0
s  14     207     526     448     105       1       0       0       0       0       0
   15     145     508     482     168       3       0       0       0       0       0
   16     151     514     579     307      13       1       0       0       0       0
   17     111     439     748     380      34       0       0       0       0       0
   18      87     387     812     515      91       1       0       0       0       0
   19     113     330     765     672     121       5       0       0       0       0
   20     127     306     791     770     200      25       0       1       0       0
   21+   1335    3051    7146   11568   10773    6133    2746    1562     874    1509

 Total=64073 Subset(20/8)=17376 (27.1%)

Table 3: Number of Simple Graphs with a Given Vertex and Cycle Count MedChem 2003 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 0 1 14 2 43 3 64 4 4 167 11 0 0 5 311 58 2 0 0 0 0 6 485 145 3 0 0 0 0 0 V 7 585 338 7 2 1 0 0 0 0 e 8 568 678 22 3 0 0 0 0 0 0 r 9 524 1089 68 1 0 0 0 0 0 0 t 10 460 1316 233 9 0 0 0 0 0 0 i 11 395 1451 512 10 0 0 0 0 0 0 c 12 313 1423 728 18 0 0 0 0 0 0 e 13 268 1204 714 62 0 0 0 0 0 0 s 14 222 1089 905 143 0 0 0 0 0 0 15 195 1019 906 217 8 0 0 0 0 0 16 150 841 956 311 9 0 0 0 0 0 17 118 692 992 353 38 0 0 0 0 0 18 88 567 1032 456 51 2 0 0 0 0 19 72 471 947 527 73 12 0 0 0 0 20 72 385 825 643 127 18 0 0 0 0 21+ 490 1537 4455 5820 4147 1723 499 143 79 42 Total=48776 Subset(20/8)=29841 (61.2%)

Table 3: Number of Simple Graphs with a Given Vertex and Cycle Count
MedChem 2003 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0       0
    1      14
    2      43
    3      64       4
    4     167      11       0       0
    5     311      58       2       0       0       0       0
    6     485     145       3       0       0       0       0       0
V   7     585     338       7       2       1       0       0       0       0
e   8     568     678      22       3       0       0       0       0       0       0
r   9     524    1089      68       1       0       0       0       0       0       0
t  10     460    1316     233       9       0       0       0       0       0       0
i  11     395    1451     512      10       0       0       0       0       0       0
c  12     313    1423     728      18       0       0       0       0       0       0
e  13     268    1204     714      62       0       0       0       0       0       0
s  14     222    1089     905     143       0       0       0       0       0       0
   15     195    1019     906     217       8       0       0       0       0       0
   16     150     841     956     311       9       0       0       0       0       0
   17     118     692     992     353      38       0       0       0       0       0
   18      88     567    1032     456      51       2       0       0       0       0
   19      72     471     947     527      73      12       0       0       0       0
   20      72     385     825     643     127      18       0       0       0       0
   21+    490    1537    4455    5820    4147    1723     499     143      79      42

 Total=48776 Subset(20/8)=29841 (61.2%)

Table 4: Number of Simple Graphs with a Given Vertex and Cycle Count National Cancer Institute 2000 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 0 1 4 2 41 3 62 2 4 134 7 0 0 5 301 50 0 0 0 0 0 6 545 184 7 0 0 0 0 1 V 7 845 467 22 1 0 0 0 0 0 1 e 8 1099 1030 82 10 0 1 0 0 0 0 r 9 1254 1766 227 9 4 1 0 0 0 0 t 10 1302 2482 646 34 4 7 0 0 0 0 i 11 1212 3219 1299 85 10 6 1 1 0 3 c 12 1196 3903 2008 113 6 16 1 0 0 3 e 13 1000 3753 2360 246 19 12 9 2 0 16 s 14 946 3752 2830 561 22 11 7 0 0 13 15 684 3188 3289 905 44 7 8 0 0 14 16 687 2670 3813 1367 88 21 12 3 0 11 17 543 2052 3951 1722 214 14 6 0 2 9 18 437 1718 4071 2337 382 33 8 1 0 12 19 349 1218 3564 2518 586 41 11 2 1 15 20 352 1091 3195 2857 764 76 14 3 0 20 21+ 1950 4168 13553 20117 16934 6661 3610 1149 735 998 Total=162148 Subset(20/8)=92156 (56.8%)

Table 4: Number of Simple Graphs with a Given Vertex and Cycle Count
National Cancer Institute 2000 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0       0
    1       4
    2      41
    3      62       2
    4     134       7       0       0
    5     301      50       0       0       0       0       0
    6     545     184       7       0       0       0       0       1
V   7     845     467      22       1       0       0       0       0       0       1
e   8    1099    1030      82      10       0       1       0       0       0       0
r   9    1254    1766     227       9       4       1       0       0       0       0
t  10    1302    2482     646      34       4       7       0       0       0       0
i  11    1212    3219    1299      85      10       6       1       1       0       3
c  12    1196    3903    2008     113       6      16       1       0       0       3
e  13    1000    3753    2360     246      19      12       9       2       0      16
s  14     946    3752    2830     561      22      11       7       0       0      13
   15     684    3188    3289     905      44       7       8       0       0      14
   16     687    2670    3813    1367      88      21      12       3       0      11
   17     543    2052    3951    1722     214      14       6       0       2       9
   18     437    1718    4071    2337     382      33       8       1       0      12
   19     349    1218    3564    2518     586      41      11       2       1      15
   20     352    1091    3195    2857     764      76      14       3       0      20
   21+   1950    4168   13553   20117   16934    6661    3610    1149     735     998

 Total=162148 Subset(20/8)=92156 (56.8%)

Table 5: Number of Simple Graphs with a Given Vertex and Cycle Count Wombat 2004.1 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 0 1 0 2 0 3 0 0 4 0 0 0 0 5 4 0 0 0 0 0 0 6 10 4 0 0 0 0 0 0 V 7 15 17 0 0 0 0 0 0 0 e 8 20 45 2 0 0 0 0 0 0 0 r 9 32 60 6 0 0 0 0 0 0 0 t 10 37 70 15 0 0 0 0 0 0 0 i 11 33 111 49 1 0 0 0 0 0 0 c 12 29 161 134 9 0 0 0 0 0 0 e 13 31 219 246 55 0 0 0 0 0 0 s 14 37 230 325 117 0 0 0 0 0 0 15 30 234 432 178 0 0 0 0 0 0 16 35 214 489 327 6 0 0 0 0 0 17 22 176 583 528 25 0 0 0 0 0 18 22 181 631 707 81 0 0 0 0 0 19 31 168 566 877 137 3 0 0 0 0 20 29 183 590 1092 293 20 0 0 0 0 21+ 503 1864 6438 16471 16628 8089 2438 800 161 160 Total=64566 Subset(20/8)=11014 (17.1%)

Table 5: Number of Simple Graphs with a Given Vertex and Cycle Count
Wombat 2004.1 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0       0
    1       0
    2       0
    3       0       0
    4       0       0       0       0
    5       4       0       0       0       0       0       0
    6      10       4       0       0       0       0       0       0
V   7      15      17       0       0       0       0       0       0       0
e   8      20      45       2       0       0       0       0       0       0       0
r   9      32      60       6       0       0       0       0       0       0       0
t  10      37      70      15       0       0       0       0       0       0       0
i  11      33     111      49       1       0       0       0       0       0       0
c  12      29     161     134       9       0       0       0       0       0       0
e  13      31     219     246      55       0       0       0       0       0       0
s  14      37     230     325     117       0       0       0       0       0       0
   15      30     234     432     178       0       0       0       0       0       0
   16      35     214     489     327       6       0       0       0       0       0
   17      22     176     583     528      25       0       0       0       0       0
   18      22     181     631     707      81       0       0       0       0       0
   19      31     168     566     877     137       3       0       0       0       0
   20      29     183     590    1092     293      20       0       0       0       0
   21+    503    1864    6438   16471   16628    8089    2438     800     161     160

 Total=64566 Subset(20/8)=11014 (17.1%)

Table 6: Number of Simple Graphs with a Given Vertex and Cycle Count Spresi 1995 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 21 1 152 2 624 3 1198 15 4 1792 61 5 2 5 3152 326 21 2 0 0 0 6 4751 1346 59 6 1 0 0 0 V 7 7555 3610 221 32 5 0 1 0 0 e 8 10342 7929 865 116 21 3 0 0 0 0 r 9 13440 14276 2175 268 63 10 0 0 0 0 t 10 15316 21917 5431 660 123 32 4 0 0 0 i 11 16412 29705 10626 1171 195 51 5 0 0 0 c 12 16129 37335 17728 2201 324 119 16 1 0 0 e 13 15590 40557 25484 3635 402 137 29 1 0 0 s 14 14078 42871 34280 7036 577 194 50 9 2 0 15 12091 41193 41966 11044 820 174 47 6 3 1 16 10742 38391 48140 16681 1453 229 63 16 3 5 17 9537 33254 51497 21981 2399 224 94 18 1 5 18 7781 29445 53497 29108 4308 410 104 38 4 6 19 6770 24307 51201 34060 6183 601 80 41 3 0 20 6035 20558 48724 38578 9272 961 143 53 10 21 21+ 42037 92696 278555 388071 288685 121001 51728 20218 10836 19719 Total=2462825 Subset(20/8)=1149220 (46.7%)

Table 6: Number of Simple Graphs with a Given Vertex and Cycle Count
Spresi 1995 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0      21
    1     152
    2     624
    3    1198      15
    4    1792      61       5       2
    5    3152     326      21       2       0       0       0
    6    4751    1346      59       6       1       0       0       0
V   7    7555    3610     221      32       5       0       1       0       0
e   8   10342    7929     865     116      21       3       0       0       0       0
r   9   13440   14276    2175     268      63      10       0       0       0       0
t  10   15316   21917    5431     660     123      32       4       0       0       0
i  11   16412   29705   10626    1171     195      51       5       0       0       0
c  12   16129   37335   17728    2201     324     119      16       1       0       0
e  13   15590   40557   25484    3635     402     137      29       1       0       0
s  14   14078   42871   34280    7036     577     194      50       9       2       0
   15   12091   41193   41966   11044     820     174      47       6       3       1
   16   10742   38391   48140   16681    1453     229      63      16       3       5
   17    9537   33254   51497   21981    2399     224      94      18       1       5
   18    7781   29445   53497   29108    4308     410     104      38       4       6
   19    6770   24307   51201   34060    6183     601      80      41       3       0
   20    6035   20558   48724   38578    9272     961     143      53      10      21
   21+  42037   92696  278555  388071  288685  121001   51728   20218   10836   19719

 Total=2462825 Subset(20/8)=1149220 (46.7%)

Table 7: Number of Simple Graphs with a Given Vertex and Cycle Count ChemNavigator 2004 Database
Cycles 0 1 2 3 4 5 6 7 8 9+ 0 223 1 40 2 52 3 102 2 4 242 6 0 1 5 420 55 0 0 0 0 0 6 703 200 2 0 0 0 0 0 V 7 1010 667 8 3 1 0 0 0 0 e 8 1384 1769 43 3 0 0 0 0 0 0 r 9 1543 3328 199 5 1 0 0 0 0 0 t 10 1854 5529 858 26 2 0 0 0 0 1 i 11 1858 7825 2166 90 1 1 0 0 0 0 c 12 2066 10641 4360 212 6 11 1 0 0 0 e 13 1948 12790 7474 552 18 17 0 0 0 0 s 14 1954 15770 12350 1363 28 24 2 0 0 1 15 1668 18696 19647 2751 87 19 8 0 0 0 16 1589 21709 28996 5344 199 24 14 0 0 0 17 1284 23867 42812 9666 551 10 16 0 0 0 18 1147 25806 62743 17053 1130 38 15 3 0 0 19 891 26254 87480 29058 2469 68 12 3 0 0 20 853 26497 115160 47718 5287 165 23 3 1 2 21+ 4845 116773 1759394 4212968 3986746 1972355 503728 65068 9067 2713 Total=13366081 Subset(20/8)=732420 (5.5%)

Table 7: Number of Simple Graphs with a Given Vertex and Cycle Count
ChemNavigator 2004 Database


                                         Cycles
            0       1       2       3       4       5       6       7       8       9+

    0     223
    1      40
    2      52
    3     102       2
    4     242       6       0       1
    5     420      55       0       0       0       0       0
    6     703     200       2       0       0       0       0       0
V   7    1010     667       8       3       1       0       0       0       0
e   8    1384    1769      43       3       0       0       0       0       0       0
r   9    1543    3328     199       5       1       0       0       0       0       0
t  10    1854    5529     858      26       2       0       0       0       0       1
i  11    1858    7825    2166      90       1       1       0       0       0       0
c  12    2066   10641    4360     212       6      11       1       0       0       0
e  13    1948   12790    7474     552      18      17       0       0       0       0
s  14    1954   15770   12350    1363      28      24       2       0       0       1
   15    1668   18696   19647    2751      87      19       8       0       0       0
   16    1589   21709   28996    5344     199      24      14       0       0       0
   17    1284   23867   42812    9666     551      10      16       0       0       0
   18    1147   25806   62743   17053    1130      38      15       3       0       0
   19     891   26254   87480   29058    2469      68      12       3       0       0
   20     853   26497  115160   47718    5287     165      23       3       1       2
   21+   4845  116773 1759394 4212968 3986746 1972355  503728   65068    9067    2713

 Total=13366081 Subset(20/8)=732420 (5.5%)

Table 8: Characterization of Databases All Compounds
Database nCmpds AMU nAtom Brnch Cycli nChir nHdon nHacc nRots nRing sRing WDI 2004.2 64,073 380.82 26 2.47 1.09 0 2 9 4 3 6 (552.86) (38.77) (0.25) (0.33) (6.92) (9.81)(23.38) (6.86) (2.17) (2.33) MedChem 2003 48,766 265.35 18 2.40 1.00 n/a 1 6 2 2 6 (140.24) (9.57) (0.22) (0.37) (1.89) (5.16) (4.03) (1.40) (1.05) NCI 2000 162,148 281.26 19 2.41 1.00 n/a 1 6 3 2 6 (154.37) (10.56) (0.22) (0.36) (1.97) (5.67) (3.91) (1.73) (1.11) Wombat 2004.1 64,566 401.48 28 2.40 1.09 0 2 8 3 3 6 (215.06) (15.29) (0.14) (0.17) (2.68) (4.01) (8.82) (3.94) (1.42) (1.12) Spresi 1995 2,462,825 313.31 21 2.41 1.00 0 1 6 3 2 6 (194.35) (12.85) (0.24) (0.34) (2.25) (2.06) (6.83) (4.98) (1.78) (1.29) ChemNav 2004 13,366,081 455.41 31 2.41 1.00 n/a 1 9 2 3 6 (96.71) (6.56) (0.12) (0.09) (1.01) (3.60) (3.14) (1.27) (0.53)
`Notes: median values standard deviation in parenthesis Key: nCmpds - number of compounds Avg MW - average molecule weight Brnch - number of bonds per non-terminal atom (branching) Cycli - number of cycles per ring atom (cyclization) nChir - number of chiral center per molecule nRots - number of rotatable bonds nRing - number of cycles per molecule sRing - size of cycles n/a - not applicable`

Table 8: Characterization of Databases
All Compounds


Database           nCmpds    AMU    nAtom  Brnch  Cycli  nChir  nHdon  nHacc  nRots  nRing  sRing

WDI 2004.2         64,073  380.82   26      2.47   1.09   0      2      9      4      3      6
                          (552.86) (38.77) (0.25) (0.33) (6.92) (9.81)(23.38) (6.86) (2.17) (2.33)

MedChem 2003       48,766  265.35   18      2.40   1.00   n/a    1      6      2      2      6
                          (140.24)  (9.57) (0.22) (0.37)        (1.89) (5.16) (4.03) (1.40) (1.05)

NCI 2000          162,148  281.26   19      2.41   1.00   n/a    1      6      3      2      6
                          (154.37) (10.56) (0.22) (0.36)        (1.97) (5.67) (3.91) (1.73) (1.11)

Wombat 2004.1      64,566  401.48   28      2.40   1.09   0      2      8      3      3      6
                          (215.06) (15.29) (0.14) (0.17) (2.68) (4.01) (8.82) (3.94) (1.42) (1.12)

Spresi 1995     2,462,825  313.31   21      2.41   1.00   0      1      6      3      2      6
                          (194.35) (12.85) (0.24) (0.34) (2.25) (2.06) (6.83) (4.98) (1.78) (1.29)

ChemNav 2004   13,366,081  455.41   31      2.41   1.00   n/a    1      9      2      3      6
                           (96.71)  (6.56) (0.12) (0.09)        (1.01) (3.60) (3.14) (1.27) (0.53)


Notes:
  median values
  standard deviation in parenthesis

Key:
  nCmpds  - number of compounds
  Avg MW  - average molecule weight
  Brnch   - number of bonds per non-terminal atom (branching)
  Cycli   - number of cycles per ring atom (cyclization)
  nChir   - number of chiral center per molecule
  nRots   - number of rotatable bonds
  nRing   - number of cycles per molecule
  sRing   - size of cycles
  n/a     - not applicable

Table 9: Characterization of Databases Compounds With 20 Vertices and 8 Cycles or Less
Database nCmpds AMU nAtom Brnch Cycli nChir nHdon nHacc nRots nRing sRing WDI 2004.2 17,376 236.07 16 2.43 1.00 0 2 6 2 2 6 (67.01) (4.38) (0.40) (0.46) (1.20) (1.66) (3.38) (2.53) (1.16) (0.82) MedChem 2003 29,841 204.26 14 2.40 1.00 n/a 1 5 2 1 6 (68.07) (4.08) (0.25) (0.43) (1.39) (3.14) (2.34) (0.97) (0.66) NCI 2000 92,156 224.28 15 2.40 1.00 n/a 1 5 2 2 6 (62.55) (3.63) (0.24) (0.41) (1.48) (3.01) (2.42) (1.09) (0.76) Wombat 2004.1 11,014 249.32 18 2.40 1.13 0 1 5 2 2 6 (47.39) (3.01) (0.14) (0.25) (1.02) (1.69) (2.80) (1.98) (0.95) (0.64) Spresi 1995 1,149,220 236.39 16 2.40 1.00 0 0 5 2 2 6 (63.32) (3.55) (0.29) (0.42) (0.84) (1.44) (2.86) (2.56) (1.10) (0.85) ChemNav 2004 732,420 267.33 18 2.38 1.00 n/a 1 5 2 2 6 (52.17) (2.78) (0.15) (0.21) (1.14) (2.57) (1.78) (0.78) (0.67)
`Notes: median values standard deviation in parenthesis Key: nCmpds - number of compounds Avg MW - average molecule weight Brnch - number of bonds per non-terminal atom (branching) Cycli - number of cycles per ring atom (cyclization) nChir - number of chiral center per molecule nRots - number of rotatable bonds nRing - number of cycles per molecule sRing - size of cycles n/a - not applicable`

Table 9: Characterization of Databases
Compounds With 20 Vertices and 8 Cycles or Less


Database           nCmpds    AMU    nAtom  Brnch  Cycli  nChir  nHdon  nHacc  nRots  nRing  sRing

WDI 2004.2         17,376  236.07   16      2.43   1.00   0      2      6      2      2      6
                           (67.01)  (4.38) (0.40) (0.46) (1.20) (1.66) (3.38) (2.53) (1.16) (0.82)

MedChem 2003       29,841  204.26   14      2.40   1.00   n/a    1      5      2      1      6
                           (68.07)  (4.08) (0.25) (0.43)        (1.39) (3.14) (2.34) (0.97) (0.66)

NCI 2000           92,156  224.28   15      2.40   1.00   n/a    1      5      2      2      6
                           (62.55)  (3.63) (0.24) (0.41)        (1.48) (3.01) (2.42) (1.09) (0.76)

Wombat 2004.1      11,014  249.32   18      2.40   1.13   0      1      5      2      2      6
                           (47.39)  (3.01) (0.14) (0.25) (1.02) (1.69) (2.80) (1.98) (0.95) (0.64)

Spresi 1995     1,149,220  236.39   16      2.40   1.00   0      0      5      2      2      6
                           (63.32)  (3.55) (0.29) (0.42) (0.84) (1.44) (2.86) (2.56) (1.10) (0.85)

ChemNav 2004      732,420  267.33   18      2.38   1.00   n/a    1      5      2      2      6
                           (52.17)  (2.78) (0.15) (0.21)        (1.14) (2.57) (1.78) (0.78) (0.67)


Notes:
  median values
  standard deviation in parenthesis

Key:
  nCmpds  - number of compounds
  Avg MW  - average molecule weight
  Brnch   - number of bonds per non-terminal atom (branching)
  Cycli   - number of cycles per ring atom (cyclization)
  nChir   - number of chiral center per molecule
  nRots   - number of rotatable bonds
  nRing   - number of cycles per molecule
  sRing   - size of cycles
  n/a     - not applicable

Table 10: Number of Simple Graphs with a Given Vertex and Cycle Count Exhaustive Enumeration Within Constraints
Cycles 0 1 2 3 4 5 6 7 8 1 0 2 0 3 1 0 4 2 0 0 0 5 2 1 0 0 0 0 0 6 5 2 0 0 0 0 0 0 V 7 8 6 1 0 0 0 0 0 0 e 8 17 15 6 1 0 0 0 0 0 r 9 31 45 28 8 0 0 0 0 0 t 10 73 124 115 56 0 0 0 0 0 i 11 146 351 449 337 50 0 0 0 0 c 12 346 970 1,650 1,785 691 0 0 0 0 e 13 798 2,711 5,802 8,544 6,083 208 0 0 0 s 14 1,821 7,433 19,593 37,306 41,017 3,463 0 0 15 4,326 20,615 64,475 152,299 232,931 42,982 0 16 10,184 56,130 205,565 586,821 1,168,284 17 24,790 154,750 647,676 2,158,602 18 59,680 419,620 2,000,657 7,662,010 19 147,722 1,152,845 6,077,679 20 362,008 3,147,135 17,261,193 Total=43,963,080 Subset(enumeration)=5.3%
`Constraints: Molecular Weight: 0-282 # of atoms: 0-20 branching: 2.00-3.23 cyclization: 0.00-1.92 # of cycles: 0-8 size of cycles: 5-7`

Table 10: Number of Simple Graphs with a Given Vertex and Cycle Count
Exhaustive Enumeration Within Constraints


                                                         Cycles
             0          1            2           3           4           5           6            7         8

    1        0
    2        0
    3        1          0
    4        2          0            0           0
    5        2          1            0           0           0           0           0
    6        5          2            0           0           0           0           0          0
V   7        8          6            1           0           0           0           0          0          0
e   8       17         15            6           1           0           0           0          0          0
r   9       31         45           28           8           0           0           0          0          0
t  10       73        124          115          56           0           0           0          0          0
i  11      146        351          449         337          50           0           0          0          0
c  12      346        970        1,650       1,785         691           0           0          0          0
e  13      798      2,711        5,802       8,544       6,083         208           0          0          0
s  14    1,821      7,433       19,593      37,306      41,017       3,463           0          0
   15    4,326     20,615       64,475     152,299     232,931      42,982           0
   16   10,184     56,130      205,565     586,821   1,168,284
   17   24,790    154,750      647,676   2,158,602
   18   59,680    419,620    2,000,657   7,662,010
   19  147,722  1,152,845    6,077,679
   20  362,008  3,147,135   17,261,193

 Total=43,963,080 Subset(enumeration)=5.3%


Constraints:
  Molecular Weight: 0-282
  # of atoms:       0-20
  branching:        2.00-3.23
  cyclization:      0.00-1.92
  # of cycles:      0-8
  size of cycles:   5-7

Findings

Chemical space is vast.
Redundancy rate during enumeration is high.
Duplicates are dramatically reduced by using ordering, symmetry, graph isomorphism, and pruning.
About 20-60% of frameworks in drug database have been enumerated.
Kier-like topology indices appear relevant for characterization.
Topogical overlap of enumerated frameworks and existing databases is small.
Millions of "drug-like" scaffolds have been produced quickly.
A very large database of information has been created.
Fingerprints and clustering methods are not particularly useful.
Information and performance problems, some fundamental, have been uncovered and solved.

Conclusion

Phase I of this project, enumeration of simple graphs, has lead to a huge amount of information. Characterization of frameworks using topological indices has lead to a selection of "drug-like" scaffolds. Daylight tools have improved as a result of the shear magnitude of generating and processing this massive data set.

Future Direction

Phase I: Simple Graphs - publication is progress (J. Chem. Inf. Comp. Sci.)
Phase II: Multigraphs - Enumerate bond orders and select "drug-like" patterns.
Phase III: Colored Graphs - Enumerate atom types and select "drug-like" candidates.
Phase IV: Accessibility - Enumerate reaction transformations and select synthetic pathways.
Continue to stress test Daylight tools, discover limitations and deficiencies, and solve such problems.

Acknowledgements

Special recognition is given to Tudor Oprea at the University of New Mexico (U-NM) for involvement in this collaboration, especially discussions on "drug-likeness".
Thanks to Tharun Kumar Allu (U-NM) for characterization of the ChemNavigator database and analysis of molecular complexity.
Thanks to Christian Bologa (U-NM) for findings on fingerprints.
Thanks to Laurel Sillerud (U-NM) for generously provided computer time on node proton, a high capacity machine at the Office of Biocomputing.
Thanks to John MacCuish (Mesa Analytics, LLC) for discussions on graph isomorphism.
Thanks to staff of Daylight CIS, Inc. and Metaphorics, LLC for input on various aspects of this project.
Part of this work was supported through the New Mexico Tobacco Settlement funds.

Daylight Chemical Information Systems, Inc.
[email protected]