Metric graph theory database search algorithms
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.