Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
×
Biotech Databases Programming Software IT Science

Toward a 3D Search Engine 83

Plasma Droid writes "NewScientistTech has a story about a 3D molecular search engine that is over 1,500 times faster than anything previously developed. The researchers, from Oxford University, developed a lightning-fast way to quickly match 3D shapes mathematically. This could not only speed up searches for new drugs, but lead to 3D search engines, for finding objects uploaded to platforms such as Google Earth, they say." The problem will be in jump-starting the supply of 3D data about molecules and everything else.
This discussion has been archived. No new comments can be posted.

Toward a 3D Search Engine

Comments Filter:
  • by LiquidCoooled ( 634315 ) on Thursday March 08, 2007 @12:32PM (#18278126) Homepage Journal
    Boobies, extra large please.

  • WOO HOO! (Score:3, Funny)

    by Lumpy ( 12016 ) on Thursday March 08, 2007 @12:37PM (#18278204) Homepage
    Finally I can search for Dodecahedron porn!
  • by goombah99 ( 560566 ) on Thursday March 08, 2007 @12:37PM (#18278216)
    It's pretty easy to geometrically hash or construct reduced feature vectors for matching. People (like me) have been doing this for years. It's much harder to know if a molecule will fit into a crevice or negative space. THe latter is probably more important to drug design. the reduced feature vectors let you know quickly if two molecules are simmmilar in shape. Which is the title given to the article. But then this is discussed in the context of drug targets. A harder problem. What maybe new or clever here is that they found a very useful set of feature vectors.
    • by Anonymous Coward on Thursday March 08, 2007 @12:44PM (#18278320)
      It's pretty easy to geometrically hash or construct reduced feature vectors for matching. People (like me) have been doing this for years

      I bet you have to beat the chicks away with a stick.
    • by gr8_phk ( 621180 )
      OK, so would it be helpful to do a 3D FFT of the density of the space containing the molecule centered at the CG ?? The frequency content is invariant under rotation, and the lowest spatial frequencies should be representative of the overall shape of the molecule. Just asking if you've tried this and how well it worked. It's just off the top of my head, but very old-school for image processing. I also suspect it may have some usefulness in matching molecules with the inverse space of other molecules.
      • Quick answer: yes variations on FFT have been tired out the wazoo. they are inded very successful for kinds of docking problems.
    • While it is fairly easy to predict the geometric shape of a small molecule the more difficult question is one of alignment. If an entire set of molecules, typified as more than one hundred, is considered then how are all of them aligned in 3D space such that they can be properly fit into the target active site?

      I'm disappointed that I cannot read the actual article. While at Abbott (informally) and while at Battelle (in formal intellectual property documentation), I proposed that a vector (the term "
    • Crappy reasearch (Score:1, Interesting)

      by Anonymous Coward
      Okay I just read the original research article in the royal society. I'm struck by three things 1) the guys who did this are big players in the bussiness 2) the work is startlingly unoriginal and seems to have no reading outside their narrow community in other areas where geometric hashing on moments is routine. 3) They don't even seem to appreciate what is interesting about their own work (the speed--no, all geometric hashes are that fast). But rather the only interesting thing is why their ad hoc, and n
  • Its going to be full of spam in under a year. You cant stop those guys.
    • Re: (Score:2, Funny)

      by Bat Country ( 829565 )
      Great, I can finally search for the chemical formula for C14L11S, which honestly has been puzzling me for some time. Apparently it affects the molecule P3N1S.
  • by Mateo_LeFou ( 859634 ) on Thursday March 08, 2007 @12:40PM (#18278272) Homepage
    I've always been of two minds about whether the drug industry was a good example of patents being cost-effective, because I suspect that very good technology will soon emerge that makes pharma R&D less expensive, by making it primarily a data-processing (esp. simulation) issue. Seems like this tech might be the first piece of that puzzle?
    • Re: (Score:3, Insightful)

      by ThosLives ( 686517 )

      The problem isn't that it takes a while to find new stuff. The problem is the barriers to entry are so high that sufficient competition can't take place, hence there is no pressure to work quickly. Basically the medical industry is *not* a free market.

      Now, I don't think the barriers need to be removed, because most of the high barrier is to ensure that treatments are effective without nasty side effects. About the only part of the barrier I can see being removed is somehow changing the liability laws, but

      • Re: (Score:3, Insightful)

        by Red Flayer ( 890720 )

        The problem is the barriers to entry are so high that sufficient competition can't take place, hence there is no pressure to work quickly.

        Except the barriers to entry are mostly not regulatory in nature. As with most advanced R&D-based industries, the barriers are brainpower and equipment. There's plenty of capital out there to handle the hit-and-miss nature of drug design, and the regulatory restrictions on drug production and marketing are not barriers to entry for research.

        IMO, what is truly limi

        • Re: (Score:3, Interesting)

          by ponos ( 122721 )

          IMO, what is truly limiting the pharma industry is profit incentive. Big pharma researches the things that will make them the most money -- which, BTW, are not cures for diseases, but rather treatments for conditions.

          This is not entirely accurate. From a business standpoint, if you sell a cure and your competitor sells a "treatment", you'll erase them from the map. So they would definitely like to "cure" things. However, most of the rich, western people do not suffer from diseases per se, but from "risk

          • FDA approval is a regulatory barrier and demands very lengthy, very expensive and time consuming pre-clinical and clinical testing.

            But it's not a barrier to entry, since established companies must also comply with FDA regulations. Barriers to entry imply that only new entrants face the the barrier.

            Take Merck and Vioxx for example.

            That is exactly what I was referring to with the COX2 inhibitors... Vioxx is the specific example.

            From a business standpoint, if you sell a cure and your competitor sells a

  • by filthWisard ( 1015523 ) on Thursday March 08, 2007 @12:43PM (#18278302)
    This is a really cool advance when working with molecules you already know the shape of, but it still doesn't get around the problem of what shape a molecule is in the first place. A protein molecule will naturally collapse into the shape with the lowest energy. If there are 100 atoms in the main chain, that's 99 different angles that it could have, that's 99 degrees of freedom. I hear that genetic algorithms are pretty good at finding the most lightly shape though, so this may not be as big a problem as it used to be.
    • by GMO ( 209499 )
      It's not a protein search engine, it's for small molecules.

      Also, the search space for polypeptides is more restricted than that. There are only so many allowed torsion angles.
    • Re: (Score:2, Interesting)

      by picob ( 1025968 )
      Usually the aminoacid sequence is known, and you can find structures of similar aminoacid sequences in databases using a BLAST (search algorithms). If that doesn't give a structure of which the structure (preferably from a crystal, otherwise NMR) was determined you can try to predict the protein structure: proteins have domains, small subsequences of which the shape is known. Many domains are known that have a particular shape. If you have determined a few of these then it becomes a lot more easy to determi
    • by illerd ( 579494 )
      Sequence similiarity tends to imply structural similarity. Find another protein with a similar peptide sequence and a known structure, use this structure as your search query, and you've got a pretty good guess of what your protein might look like. Better yet, you've got a good starting point for your hackish protein folding method (monte carlo, genetic algorithm, neural networks, whatever)
    • Proteins are typically characterized through X-ray crystallography. The drawback with X-ray analysis is that the protein must be in a crystallized form--this typically means that millions of occurences of the same protein are crystallized together. The shape that a protein takes such that it can form a crystal may not be the shape that the crystal takes when in the heterogenous solution of a cell. Fesik, at Abbott Laboratories, made ground breaking advances in the realm of solution phase study of the sha
      • really? (Score:2, Insightful)

        by GMO ( 209499 )
        Although the crystal structure is not the same as the structure in solution, it can't be that far off.

        Crystals are pretty watery, much like the cell. Unless packing contacts are altering the active site, they are unlikely to be much different.

        Also, the bulk of the structure is there to keep the active site residues in a particular orientation.

        Perhaps management vitriol was partially justified? :) Only joking, you may be right. I don't work on drug design, only backbone structure.
        • The particular 3D crystalline form can differ even from one recrystallization solvent to another. In extreme cases a different configuration at even one rotatable center may significantly affect the shape of the rest of the protein.

          The hope is that a given protein remains within a particular probability space and that the shape of the active site, refined gradually over millions of years, is highly stable. When 3/4 of drugs entering phase I clinical trials fail efficacy, though, the numbers speak for them
    • by tfoss ( 203340 )
      I hear that genetic algorithms are pretty good at finding the most lightly shape though, so this may not be as big a problem as it used to be.

      They may be *better* at predicting structure, but they are still a shit long way from being any good. Remember that whole big Blue Gene deal, building the biggest baddest computer out there, that was done pretty much to be able to predict protein structure, and (last i heard) they still aren't even close. Every so many years a new technique for prediction comes out

  • Comment removed (Score:4, Insightful)

    by account_deleted ( 4530225 ) on Thursday March 08, 2007 @12:47PM (#18278358)
    Comment removed based on user account deletion
    • Re: (Score:3, Insightful)

      by LordPhantom ( 763327 )
      No, that will be a problem. Once you have the database, what exactly am I supposed to input for searching? Will I need to learn how to create a 3D model in order to search for similar objects?
      The rest of your comments are pretty valid, however in this case that would seem to be aside the point. Searching objects in this fashion would be as simple as metadata that is appropriate for 3d model searches. Rather than provide a base model, you could search the metadata supplied with/for/generated for shape
      • fine, hum then. the union of {people who can whistle} and {people who can hum} is quite large. Even if you only consider the subset of each who {would like to find random songs from vague recollections}
    • No, that will be a problem. Once you have the database, what exactly am I supposed to input for searching? Will I need to learn how to create a 3D model in order to search for similar objects?

      Even if you do, you can use a sketching tool (like google sketchup... mmm, sketchup) to whip out a basic 3d model.

      Also, it could be done through a tree-selection process - where you pick from perhaps 9 images the model that looks the most like the one you want, and you continue in this vein until you find (or don't f

      • Re: (Score:2, Interesting)

        by GMO ( 209499 )
        Hmmm. Maybe it depends on whether you can convert from internal coordinates to a 3D structure. What you seem to be suggesting is moving through structure space, matching as you go along.

        So at any point, you have to generate images of the 'neighbours' of the current structure. It could work. Maybe.
    • No, that will be a problem. Once you have the database, what exactly am I supposed to input for searching? Will I need to learn how to create a 3D model in order to search for similar objects?

      Depends. Did you have to learn how to spell in order to use a text search engine?

      The people who are going to be using this sort of database are going to already have tools available to create their models. People have been creating MOL and PDB files for quite awhile now, and if there isn't a file converter/importer then I'm sure there will be soon. Plus, researchers often want to just search for things that are similar to something they're already looking at. So what they'll do is take whatever model t

  • by wsherman ( 154283 ) * on Thursday March 08, 2007 @12:57PM (#18278468)

    NewScientistTech has a story about a 3D molecular search engine that is over 1,500 times faster than anything previously developed.

    The implication both from the summary and from the article itself is that this new search is just as thorough as other search methods but much faster. To prove thoroughness they would have had to show that anything found by other search methods will also be found by their new, much faster, search method. I doubt very much that they were able to do prove this rigorously.

    That's not to say that the problem of matching 3D molecular shapes is not important or that their research is not valuable. I would say, though, that it is misleading to claim that they have solved the 3D search problem with a much faster algorithm. There are many different measure of 3D similarity and, for many measures of similarity, the only way to guarantee an optimum match is by exhaustive search.

    Note that, in general, every search will be exhaustive in the sense that the query must be compared to every entry in the database. The problem is that many measures of similarity have additional parameters that must be optimized by exhaustive enumeration for each comparison. The classic example is a measure of 3D similarity that pairs each atom in the query with an atom from the structure in the database. In the general case, all possible pairings must be tried through an exhaustive enumeration.

    • In the general case, all possible pairings must be tried through an exhaustive enumeration.

      Why should that be true? We are able to categorize textual content and build indexes based on word structure. Why couldn't we do the same thing with 3d objects, and thus be able to discard a large number of comparisons up front?

      • In the general case, all possible pairings must be tried through an exhaustive enumeration.

        Why should that be true?

        For some measures of 3D similarity there are shortcuts and for other measures there aren't shortcuts. For example, what happens if part of our query molecule is very similar to part of a molecule in the database we are searching? Does that count as a match or not? If the answer is that it does not count as a match, then we could sort our search database by number of atoms - only those molecul

    • by illerd ( 579494 )

      The implication both from the summary and from the article itself is that this new search is just as thorough as other search methods but much faster. To prove thoroughness they would have had to show that anything found by other search methods will also be found by their new, much faster, search method. I doubt very much that they were able to do prove this rigorously.

      ...the only way to guarantee an optimum match is by exhaustive search...

      I haven't read the paper, but I don't think this (a thorough comparison) is as hard as you think it is. The bioinformatics community is pretty good about sharing datasets and software. There are benchmarks datasets that researchers use for comparing shape-matching techniques. Pick, say, 100 query molecules and a database of 10,000 molecules. Search the database for each query, 1,000,000 queries, multiplied by the number of techniques you're comparing. Not that much work. Throw in Kabsch-style cRMS match

      • I haven't read the paper, but I don't think this (a thorough comparison) is as hard as you think it is.

        What I was referring to was guaranteeing that a particular search method can find the best match. If I understand what you're saying, it may not be that important to guarantee a best match - which is a good point.

        With respect to guaranteeing that a search has found a best match, there are two problems. The first problem is that the search method may not reflect what is actually desired. If you want to fin

  • by oohshiny ( 998054 ) on Thursday March 08, 2007 @12:58PM (#18278480)
    Currently, the most common way to find the 3D shape of a particular molecule within a database is to superimpose a candidate over the query molecule and see how much of it overlaps. But this is time consuming, partly because it requires both molecules to be precisely aligned.

    Yes, that's currently "the most common way" because at least you can tell what you're getting: when you get a match, you can actually say how close the different shapes are to one another.

    The new technique uses a different approach. It analyses the position of the different atoms within a molecule to understand its shape. These relative positions can be mapped and stored a molecular database.

    That's actually not a "new technique", it's an old technique. It's what people used to do before they tried to overlay 3D shapes accurately. They used to do that because computers used to be too slow to do the accurate comparison.

    As the article points out, there is only limited 3D shape information available at all. Few people need to do 3D queries right now, and there is little data to do them on, so optimizing speed is the wrong thing to do; we need to optimize accuracy and scientific relevance.
  • by Anonymous Coward
    We had 3d search engines over a decace ago: http://imdb.com/title/tt0113243/ [imdb.com]
  • by ajax142 ( 69131 ) <MEjjhelmusREMOVE AT mtu DOT edu> on Thursday March 08, 2007 @01:00PM (#18278504)
    The author lists an apparent problem of this 3D search as a lack of molecular structures and calls for a "jump start" in the supply of 3D data, I call BS on this claim. A quick look at the Cambridge Structural Database [cam.ac.uk] shows 400,977 strucutures of 363,931 different molecules. There are another 89,064 structures of inorganic molecules in the Inorganic Crystal Structure Database [fiz-karlsruhe.de]. On the biological side there are 3,425 structures of Nucleic Acids in the NDB [rutgers.edu] as well as 42,082 structures of proteins and polypeptides in the PDB [rcsb.org]. If that still isn't enough for the authors, fire up any number [univie.ac.at] of ab initio [ameslab.gov] quantum [gaussian.com] chemistry [turbomole.com] programs [molpro.net] and in a short time you can create a library of good guesses for the structure of small molecules.

    I tend to think the authors of the article are refering to the problems of a "useable form" for the structures and easy access of many of these databases. The first problem is mearly a problem of converting between the various structural file formats out there, something a good programmer (or grad student) can solve is a few weeks or less. The second is a bureaucrat issue and not a scientific one.

    • No, completely wrong, I'm afraid :). The context here is virtual screening in drug discovery: you either have a protein cavity of known shape or you have a known inhibitor of a protein in an (either known or modelled) bound conformation. The question is "Which other molecules could fit the cavity?". The problem is that molecules are flexible. The average drug-size molecule has 6-10 rotatable bonds, and anywhere from 50 to several thousand different plausible 3D shapes. Crystallographic data from the CSD do
  • The problem will be in jump-starting the supply of 3D data about molecules and everything else.

    Well the RCSB Protein Data Bank [rcsb.org] would be a start, and there are tons of molecule data bases with 3D data that are only waiting to be thoroughly mined. The pharmaceutical companies have them, and there are free ones too.

    In fact, the motivation for this research undoubtedly was the abundance of data that is out there but can't/could not be searched efficiently.

    • Firstly, only some families of proteins have any x-ray structural data about them: there are whole families that are effectively uncrystallisable.

      Secondly, the protein's 3D shape is only half the battle. Small molecules are generally highly flexible, so to search them in 3D you need to enumerate their potential shapes first. That's not trivial for large sets of compounds.

  • Quite interesting (Score:3, Interesting)

    by excelsior_gr ( 969383 ) on Thursday March 08, 2007 @01:14PM (#18278672)

    This is quite an interesting achievement. The tools that I am familiar with can only search for 2D structures like functional groups (alcohol groups, aromatic rings, etc). At their best, they might give the ability to search for R- and S- stereoisomers, but that is it. This is pretty enough for tasks like solvent design that are quite frequent in the chemical process industry, but in the pharmaceutical R&D they need more powerful tools.

    I will give a simple example of an enzyme: These nice molecules catalyze reactions of vital importance in the modern pharmaceutical industry by providing a chemical "lock" where the "keys" (i.e. the reacting molecules) will dock on. This enables them to react and form a new molecule that will then undock from the enzume leaving the "lock" free for the next pair.

    These "locks" are actually 3D structures of appropriately aligned molecules. This is where this search ability comes in: The chemist suspects how the appropriate lock would look like for catalyzing his reaction (3D alignment of functional groups), much like someone suspects what the right keywords for a Google search are. Then he feeds the data to the machine and gets the molecules that are likely to be of assistance in his work. After that, he can make experiments testing these enzymes to see if they actually work.

    This should speed things up very much in biochemical research. It means less literature research and less failed experiments.

  • So the summary says it's 1500 times faster. OK then, if i double the number of items in the database and compare again, is it still 1500 times faster? What if we do a million times the number of items?
  • So now whenever I search for information about caves or black holes, I'll get sent to goatse.
  • related problem (Score:3, Interesting)

    by smellsofbikes ( 890263 ) on Thursday March 08, 2007 @01:32PM (#18278908) Journal
    It's nice to know what shape a molecule is. It would be even nicer to be able to make a molecule in a particular shape. If you map an enzyme's active site -- its topology, charge distribution over the surface, possibility for organometallic or hydrogen bonding -- you have a much better chance of finding some interesting analog to the enzyme's substrate that'll make the system do something new. Even better, you could take an existing molecule that you *want*, and form an enzyme surface so that two cheap molecules, exposed to your new enzyme surface, will find it thermodynamically favorable to become the molecule you want, and suddenly you're in a very profitable business: you can breed chemical engineering factories rather than having to build them.

    This poses a problem, similar to the (unstated) problem posed by the molecular printers in Neal Stephenson's Diamond Age: what happens when this sort of stuff starts to become widely available and people start engineering enzymes or instructing their printers to produce, say, heroin, or TNT? With molecular printers, presumably the first versions would only be able to produce structural stuff: printing bicycles, not martinis. But if we get to the point where we can design enzymes for a desired substrate -> product reaction, we have a real problem because it's all wet chemistry and there isn't an obvious hardware/firmware way to block people making anything their inventive, twisted little minds can come up with.

    Mind you, I think that's great. I miss the days where I could order almost any chemical I wanted without having to wade through masses of paperwork, tracking, and laws intended to ban any drug analog that might have pharma activity. But it is going to have some very exciting side-effects.
  • by MercBoy ( 756722 )
    This makes me wonder if this could evolve to more general purpose 3-D searches, such as facial recognition, searching for a specific shape of car, suspect identification in a crowd based upon a combination of body shape, face, etc.
    • I suppose yes. After all, in the article it says that they are looking at the position of specific points in the general 3D structure and check their geometrical characteristics (skewness, relative distances, etc). This is what face-recognition software does in 2D right?

  • I guess what's unclear is what kinds of molecules they're trying to match. I work part-time in a university lab doing drug research. We synthesize variants of existing molecules and test them for efficacy in various diseases, though we do mostly work on cancer-related drugs. Some of the molecules we work with are very large and very complex. But finding what else is out there isn't genereally that difficult. Molecules are divided into a number of families and families of molecules are generally pretty simil
  • Just what we need...another dimension to lose things in.
  • It's announcements like these that cause me to ponder just how far behind we are in terms of software development progress.

    Back in 1993 I had a whole suite of MS Flight Simulator programs. (different cities were packaged separately. To the best of my recollection, I had Chicago, New York, LA, and Paris). Obviously the game detail was limited, this was before 3D accelerators, but the buildings were still 3D and key locations had fairly accurate roads. I remember reading in more than one computer magazin

  • Go to: http://shape.cs.princeton.edu/search.html/ [princeton.edu] and select "Protein Database" from the drop down list, and enter "random" as the keyword. Next, the "find similar shape" links do full 3D feature vector matching against a database of 16900 protein molecule models, in a fraction of a second. But apparently this new method is "1500 faster than anything previously developed"? Maybe the authors never checked the current 3D shape matching literature?
    • The link is http://shape.cs.princeton.edu/search.html [princeton.edu] (without the trailing slash)
    • The Oxford group's technique is looking at a different problem: small molecule 3D shape matching. Surprisingly, this is actually harder than protein shape matching: proteins have a defined 3D shape, but small molecules are flexible and can a variety of shapes. So, you either need to have a flexible fitting method, or you need to enumerate 'example' shapes for each molecule you want to search against.

      Compare your search against ~17K protein structures to a search across the roughly 4 million commercially-a

  • One thing more important and easier to do than 3d mesh matching is musical pattern matching---like searching on consecutive notes or chords or rythmes. It would be really easy to find a song with relative tone, and music is easy to index and search by interfacing over midi. Is google listening to us, musicians? Simon.
  • For robots (Score:1, Insightful)

    by Anonymous Coward
    Great for robot AI technology. With a couple cameras and some laser equipment, get a good 3D representation of what it's looking at, then run it through the list and find a match.

One person's error is another person's data.

Working...