Slashdot Mirror
Toward a 3D Search Engine
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.
Boobies, extra large please.
liqbase
this could revolutionize pr0n.
Finally I can search for Dodecahedron porn!
Do not look at laser with remaining good eye.
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.
Some drink at the fountain of knowledge. Others just gargle.
Its going to be full of spam in under a year. You cant stop those guys.
Libertarian Leaning Political Discussion Forum.
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?
My turnips listen for the soft cry of your love
couldn't resist
My turnips listen for the soft cry of your love
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.
Comment removed based on user account deletion
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 shapes, and once you have a few from the library, use THOSE as searches for -similar- or combined models. It's actually quite possible, if of questionable use - not to mention your criticism could be thrown back at you by simply saying "What!??! A search engine for sound? That will never work, I'd have to learn how to whistle".
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 find) the one you're looking for. I don't know if their software would work well with this approach, though.
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
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.
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.
We had 3d search engines over a decace ago: http://imdb.com/title/tt0113243/
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.
Well the RCSB Protein Data Bank 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.
EagerEyes.org: Visualization and Visual Communication
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.
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.
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.
Nostalgia's not what it used to be.
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.
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}
Can you be Even More Awesome?!
That's great! Now if you could just do that 750,000 times in the next fifteen seconds, and tell me which shape in the set is most similar to this thing in my pocket...
(cue dick size jokes in 3...2...1)
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
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.
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 similar to each other in shape. Searching by family name or for molecular sub-parts, generally works pretty well, I've found.
But there's a lot more to the chemistry than just the shape of the molecule. When it comes to drugs, you're often looking for something that will bind with a given protein and while shape plays a part in that, the functional groups on the molecule are major drivers in whether or not the molecule will actually do its work.
They don't really give enough specifics in the article to know how valuable this really is.
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 shape of proteins--SAR by NMR analysis. Still concerns remain because the solutions used to lend to NMR analysis are not the same as the heterogenous environment within a cell.
This creates a much larger problem in drug design. The medicinal chemists design molecules to fit active sites of proteins and enzymes but the shape of that active site is only determined from Xray, NMR, or computer generated lowest energy conformations. It is no surprise then that 3/4 of molecules which are advanced to clinical trials fail efficacy studies: in short, they simply do not work. Looking back it's quite logical that they do not work because they were designed to fit a shape that was not a proper representation of the shape which the protein takes within the actual cells, in vivo.
Making note of this was usually received with extreme vitriol by the management.
the NPG electrode was replaced with carbon blac
Just what we need...another dimension to lose things in.
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 "vector " was in my IP release forms) for describing molecules in 3D space based on electronegativity, eletrophilicity, nucleophilicity, entropy (freedom of mation), and bulk (volume).
the NPG electrode was replaced with carbon blac
Although the crystal structure is not the same as the structure in solution, it can't be that far off.
:) Only joking, you may be right. I don't work on drug design, only backbone structure.
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?
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 magazine that these flight simulators were just the beginning, in 5 years (1998) we'd have 3D maps of the whole world. Looking for directions would be a thing of the past, we'd all have programs that could visually tour every nook and cranny of every location in the world.
It's astounding that computers were set to have a virtual earth in 1998. It's 14 years after I read those articles and we're not even close. Google Earth, the closest representation of such a vision, is about 1% of the way towards it.
I'm also reminded of the rise of VRML/3DML back in 1996. There was a site run by Superscape (vwww.com the Virtual World Wide Web), with links to hundreds of 3D web sites. Deployment of the 3D web was imminent! I thought it was the wave of the future, it was just a matter of time and refinement. 11 years later, we've all but tossed VRML/X3D/3DML in the toilet. The progress those technologies have made is absolutely minimal, not what you'd expect as a result of over a decade of work.
So am I excited about a 3D search engine? Not really. I don't even see it happening in my lifetime, never mind the next few years.
nice. he replies to my post, and I get modded down for redundancy. in soviet russia, you mod slashdot -1 redundant!
http://wstewart.php0h.com - the sugarbuzz project blog
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 they're currently playing with, lop off chunks of it, and submit the remaining bit to the search engine to see if they've got anything similar on file. So it's not like anyone's going to have to sit down and drag-n-drop individual atoms until they have their model built up...
Just junk food for thought...
Go to: http://shape.cs.princeton.edu/search.html/ 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?
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 not particularly imaginative, feature vectors empiricall may beat other proposals. Since they only compare it against some ancient ones one can't really decide if these feature vectors are better or if computers got better since 1992.
I knew carbon was unique, but four-way bonding? That's just wrong...
Check out http://www.vizseek.com/
searching a database of 3d objects with hand-sketches... Not a total search solution, but it does well for actual 3d models of objects.
Sorry, but sounds like BS to me. When was the last time in the field of technology something actually went 1500 times faster for any reason.
:P or lacks significant detail. I just ask slashdot readers to realistically fathom how much 1500 times faster would actually be and then reason the statistic possibility of that claim being true. I doubt my Core 2 system is actually 1500 times faster than an NES or perhaps even Atari. It could be for certain uses, but overall I can't see the performance of even 20+ years having created a 1500 times performance leap. Don't bother using FLOPS to estimate such performance however as it a pathetic representation of real world performance. MHZ is pretty useless also, but a basic rule of thumb is that non x86 processor dust x86 processor on a mhz to mhz level. That said it would be realistic to say a Core 2 system is far less than 1500 times as powerful as an NES. While this supposed breakthough was made through software I guess.. I find that even less likely to be true. The search routine they are comparing it too would have to be so badly written to run that much slower it's just ridiculous to think drug companies are really that stupid. They aren't using a search routine that's 1500 times slower. There is just no way that is a realistic claim.
Just once..
Yet... they constantly claim these amazing performance increases. This appears to more practically be one of those cases where the best possible scenario is paraded as the expected average.
The claim that someone writes a program that is realistically 1500 times faster than it's leading competition is more or less ridiculous. Perhaps the problem is in how we measure speed/performance, but such a jump in performance is almost certainly not true in a realistic manner. That for the claim to be reasonably true it would have to come with a stipulation like the technology isn't actually useful for another 10 years.
If it's too good to be true... it's not true. I don't think we've EVER in the history of math or computers seen a 1500 TIMES improvement in anything no less that improvement being overnight. The claim has to be flawed to appear more impressive or just flawed period. Maybe it searches 1500 times faster but doesn't actually find anything
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.
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.