3 ms·

> A startling percentage of their compound backbones consisted of three- and four-membered rings concatenated into structures that no one can be sure are even s

by aazaa 5y ago

> A startling percentage of their compound backbones consisted of three- and four-membered rings concatenated into structures that no one can be sure are even stable, and are certainly beyond the current powers of organic synthesis. Adding those in would make the compound set many orders of magnitude larger, since only 0.005% of the original compound graphs were even considered as starting points. ... Some may question what's so hard about a few billion entries. The thing to keep in mind is that enumeration like GDB necessarily yields a combinatorial explosion of molecules. Every molecule that gets passed to the next step can generate many millions or more children. Isomeric forms make the problem even more challenging. It's worth noting the very limited repertoire of elements: "C, N, O, S, and halogens." This excludes, for example, phosphates, which are part of the DNA and RNA backbone, and phospholipids, although even oligonucleotides and many medium-sized lipids are too large to be part of GDB-17. Each atom added pushes the enumeration further away from feasibility. Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), although GDB's low node count mitigates the problem. There are ways to deal with the combinatorial explosion so that you can search a vast molecular space without actually enumerating all of the molecule products. But to compile statistics like those in the paper that Lowe was writing about, you need to enumerate to some degree. https://pubs.acs.org/doi/10.1021/ci300415d https://pubs.acs.org/doi/10.1021/ci300415d

actually_a_dog 5y ago
> Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), although GDB's low node count mitigates the problem. It's not just the low vertex count that makes this an easier problem than general GI. The state of the art GI algorithm for general graphs runs in quasipolynomial time 2^{O((log n)^c)}, with c=3 claimed. [0] However, structural constraints implied by chemical plausibility should (probably[1]) usefully limit the class of graphs that need be considered to those of bounded treewidth. A polynomial time GI algorithm was recently published for graphs of bounded treewidth. [2] [0]: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#State_of_the_art https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Stat... [1]: If nothing else, maximum degree restrictions imposed by chemical valence should impose a useful upper bound on treewidth. Although I (somewhat surprisingly) can't find a paper offhand stating such an explicit bound for treewidth in terms of maximum degree, I did find one stating an asymptotic bound of (1 - C * exp (-4.06√d)|V| for sufficiently large max degree d, and some constant C, which lends some plausibility to this line of thought: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0120880 https://journals.plos.org/plosone/article?id=10.1371/journal... [2]: https://arxiv.org/abs/1803.06858 https://arxiv.org/abs/1803.06858

by aazaa 5y ago

actually_a_dog 5y ago

> Then there's the problem of figuring out if you've already enumerated a molecule. That problem has no known polynomial-time solution (graph isomorphism), although GDB's low node count mitigates the problem. It's not just the low vertex count that makes this an easier problem than general GI. The state of the art GI algorithm for general graphs runs in quasipolynomial time 2^{O((log n)^c)}, with c=3 claimed. [0] However, structural constraints implied by chemical plausibility should (probably[1]) usefully limit the class of graphs that need be considered to those of bounded treewidth. A polynomial time GI algorithm was recently published for graphs of bounded treewidth. [2] [0]: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#State_of_the_art https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Stat... [1]: If nothing else, maximum degree restrictions imposed by chemical valence should impose a useful upper bound on treewidth. Although I (somewhat surprisingly) can't find a paper offhand stating such an explicit bound for treewidth in terms of maximum degree, I did find one stating an asymptotic bound of (1 - C * exp (-4.06√d)|V| for sufficiently large max degree d, and some constant C, which lends some plausibility to this line of thought: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0120880 https://journals.plos.org/plosone/article?id=10.1371/journal... [2]: https://arxiv.org/abs/1803.06858 https://arxiv.org/abs/1803.06858