9
$\begingroup$

I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News. One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could. On the other hand, perhaps more theoretical algorithms would be too hard to implement. It seems like a potential open area, though.

So here's my question:

Is there an overview (or a small handful of references) that discusses theory and implementation (hopefully) of algorithms of databases of graphs with metric information? (Each edge is a distance, and each vertex has a volume.) A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.

$\endgroup$
  • $\begingroup$ how important is it that the database has metric information ? there's tons of work on graph database searching, even in the bio realm, but I don't know about the volume/distance label issue $\endgroup$ – Suresh Venkat Sep 10 '10 at 4:20
  • $\begingroup$ I'll know the answer to your question in a week or two. The similarities to and differences with bioinformatics problems are not clear to me yet. $\endgroup$ – Aaron Sterling Sep 10 '10 at 12:22
2
$\begingroup$

This seems to be related to the subgraph isomorphism problem which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in certain cases, though.

If chemo- is anything like bioinformatics you will probably be interested in approximation algorithms in order to deal with noise, anyway. Also, given database lookup as application, there might be clever ideas for preprocessing that give you good amortised runtimes.

Found (not read) those:

http://www.springerlink.com/content/4751121q3575v041/

http://bioinformatics.oxfordjournals.org/content/23/2/232.full

http://portal.acm.org/citation.cfm?id=1368898

Disclaimer: Again, sorry for comment-style answer; I am not yet allowed to comment.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.