4 ms·

What makes 1 billion rows a large search space? What makes 150 billion rows incomprehensibly large? With a molecular weight of 500 we're talking something on

What makes 1 billion rows a large search space? What makes 150 billion rows incomprehensibly large? With a molecular weight of 500 we're talking something on the order of terabytes of data (for 1b molecules)? It certainly sounds like a tractable amount of data. What computer problems are stopping us from generating a compound, computationally testing it for stability, and adding it to the list and then searching?

rodrigosetti 5y ago
Chemical simulation is very hard (involves solving multiple np-complete problems). But that is one of the expected applications of quantum computers (simulate quantum systems).
_ihaque 5y ago
Even at 500Da or less, it's much, much larger than that. You may be interested in the work of Jean-Louis Reymond's group, who have done more or less exactly what you suggest: https://gdb.unibe.ch/downloads/ https://gdb.unibe.ch/downloads/ GDB-11, with 11 heavy atoms, has 26.4M structures (110.9M stereoisomers -- molecules aren't 2D). Going up to 13 gives you 970M molecules. Going up to 17 (still mostly below 250Da) is 166,400M. There's a lot of space up there below 500Da.
- sseagull 5y ago
  Also note that that only includes organic molecules. There's another 85-ish natural elements in the periodic table that could be important, but is much harder to synthesize or compute. Although including heavier elements can blow past 500 Da pretty easily.
  - whatshisface 5y ago
    The heavier elements start acting more like continuous systems and less like quanta legos, as you get more and more states per eV. Transition metals and lanthanides don't get their own combinatoric explosion until literal sticks are stuck on the smooth balls in coordination chemistry.
whatshisface 5y ago
I have learned over time that state space size has nothing to do with problem difficulty. Sorting finds and answer in a space with n! possibilities in n log(n) time. Chemistry is difficult not because of the large number of chemicals but because there hasn't been a lot of structure discovered in them to allow the sort of compounding subcase solving that makes searching a sorted list tractable. The structure that has been discovered can be found in chemistry textbooks and has names like "so-and-so's rule" which can be applied to boroalkanes with between 5 and 12 vertices excepting 6, unless the cage is charged in which case you should treat it like it has one fewer vertex, unless the charge is -2 and the original vertex count is between 8 and 13, in which case... Those rules are much better than a table as measured by information compression but you can't discover them unless you start with the table filled mostly filled out already.
- jpollock 5y ago
  Except, 1 billion isn't typically considered _big_ to even perform full scan searches. It's only big if it's expensive to search all of them, and that problem is very easily parallelizable. Which makes it a $$->time equation? If it costs 1s for 1 machine to check an item, you will need 32 machines to check a billion in a year, or 12000 to search in a day. So, it's the is_match operator that's expensive, rather than data storage? Is the match check minutes long or needing human oversight?
  - whatshisface 5y ago
    Checking a molecule can take years of computer time on a supercomputer, depending on what you are checking for. There is no upper bound to the difficulty of checking because you can always ask for a more complex situation, and you are usually asking for those situations because the simple things are usually already discovered.
rsfern 5y ago
150 billion is the size of a pretty restricted subset. The estimate for general druglike compounds is 10^60
optimalsolver 5y ago
The number of possible chemical compounds (organic and inorganic) far exceeds the number of atoms in the observable universe. The 166 billion number is just a small selection of promising candidates from that space, not the entire set.

rodrigosetti 5y ago

Chemical simulation is very hard (involves solving multiple np-complete problems). But that is one of the expected applications of quantum computers (simulate quantum systems).

_ihaque 5y ago

Even at 500Da or less, it's much, much larger than that. You may be interested in the work of Jean-Louis Reymond's group, who have done more or less exactly what you suggest: https://gdb.unibe.ch/downloads/ https://gdb.unibe.ch/downloads/ GDB-11, with 11 heavy atoms, has 26.4M structures (110.9M stereoisomers -- molecules aren't 2D). Going up to 13 gives you 970M molecules. Going up to 17 (still mostly below 250Da) is 166,400M. There's a lot of space up there below 500Da.

sseagull 5y ago
Also note that that only includes organic molecules. There's another 85-ish natural elements in the periodic table that could be important, but is much harder to synthesize or compute. Although including heavier elements can blow past 500 Da pretty easily.
- whatshisface 5y ago
  The heavier elements start acting more like continuous systems and less like quanta legos, as you get more and more states per eV. Transition metals and lanthanides don't get their own combinatoric explosion until literal sticks are stuck on the smooth balls in coordination chemistry.

whatshisface 5y ago

I have learned over time that state space size has nothing to do with problem difficulty. Sorting finds and answer in a space with n! possibilities in n log(n) time. Chemistry is difficult not because of the large number of chemicals but because there hasn't been a lot of structure discovered in them to allow the sort of compounding subcase solving that makes searching a sorted list tractable. The structure that has been discovered can be found in chemistry textbooks and has names like "so-and-so's rule" which can be applied to boroalkanes with between 5 and 12 vertices excepting 6, unless the cage is charged in which case you should treat it like it has one fewer vertex, unless the charge is -2 and the original vertex count is between 8 and 13, in which case... Those rules are much better than a table as measured by information compression but you can't discover them unless you start with the table filled mostly filled out already.

jpollock 5y ago
Except, 1 billion isn't typically considered _big_ to even perform full scan searches. It's only big if it's expensive to search all of them, and that problem is very easily parallelizable. Which makes it a $$->time equation? If it costs 1s for 1 machine to check an item, you will need 32 machines to check a billion in a year, or 12000 to search in a day. So, it's the is_match operator that's expensive, rather than data storage? Is the match check minutes long or needing human oversight?
- whatshisface 5y ago
  Checking a molecule can take years of computer time on a supercomputer, depending on what you are checking for. There is no upper bound to the difficulty of checking because you can always ask for a more complex situation, and you are usually asking for those situations because the simple things are usually already discovered.

rsfern 5y ago

150 billion is the size of a pretty restricted subset. The estimate for general druglike compounds is 10^60

optimalsolver 5y ago

The number of possible chemical compounds (organic and inorganic) far exceeds the number of atoms in the observable universe. The 166 billion number is just a small selection of promising candidates from that space, not the entire set.