Re: [Cdk-devel] [ cdk-Feature Requests-1181323 ] Test for very slow fingerprints

[Nina J. <ni...@ac...>]

Hi Chris,

Christoph Steinbeck <c.s...@un...> wrote:

> Hi Nina, and others,
> 
> thanks a lot for this nice analysis.
> 
> cdk.AllRingsFinder has two problems:
> 1. The algorithm might be slow by design in some cases.

yes, it is, but finding all possible rings IS a hard problem

> 2. My implementation might be sub-optimal.

haven't checked :)

> We can ignore point 2 for now :-), because clearly the combinatorial 
> problem underlying point 1 will catch us anyway above a certain number 
> of rings in the molecule.

exactly

> 
> In the case of the cdk.Fingerprinter, AllRingsFinder is used as a 
> preprocessing step to aromaticity detection.
> Marking bonds as aromatic clearly is a crucial step in fingerprint 
> calculation. Since we are thus not interested in all rings but only 
> those who are likely to be aromatic, we might be able to come up with a 
> better solution, which does it without AllRingsFinder.

btw, some algorithms consider finding "relevant" cycles in the graph, I
particularly found this one quite appealing in theory (and used in a chemistry
context)

http://www.combinatorics.org/Volume_4/PostScriptfiles/v4i1r9.ps



> 
> One idea that we recently had was to make the SmallestSetOfSmallestRings 
> (SSSR), which is fast even for C60, and to produce the SetOfAllRings by 
> a linear combination of the SSSR rings.
> Clearly, this will not help in all cases, especially when the whole ring 
> system is aromatic.
> Then again, doing the aromaticity detection just based on the SSSR will 
> work.
> 
> Ultimately, I think, we cannot do without a decent heuristic, where we 
> evaluate some statistics on the number of expected aromatic rings vs. 
> number of all rings, and then apply the best suited Ring Detection 
> Algorithm.
> 
> Some of you might have noticed that virtually not literature is 
> available on the aromaticity perception problem.
> I just found this:
> (1)	Rooskozel, B. L.; Jorgensen, W. L. Computer-Assisted Mechanistic 
> Evaluation of Organic-Reactions .2. Perception of Rings, Aromaticity, 
> and Tautomers. Journal of Chemical Information and Computer Sciences 
> 1981, 21, 101-111.
> 
> and I will try to get a copy and see what they did.
> 
> > If anybody interested in code / statistics, please let me know. 
> 
> Oh, yes, please. We would be very interested in that.
> It could go into a theory manual, which we urgently need to start.

yes, I've already agreed I will write a summary to be included in the next CDK
news

Best,
Nina