On Tue, Jun 22, 2010 at 9:59 PM, Greg Landrum <greg.land...@gmail.com> wrote: > Hi Tim, > > On Tue, Jun 22, 2010 at 9:34 PM, Tim Vandermeersch > <tim.vandermeer...@gmail.com> wrote: >> >> On the openbabel devel mainling list there was discussion about the >> Largest Set of Smallest Rings (LSSR). RDKit calls this symmetric SSSR >> I think. Craig proposed an algorithm to directly select this LSSR from >> the found rings. This doesn't work for all cases though >> >> Most of these extensions (e.g. ESSR, RDKit, ...) to the SSSR start >> from the SSSR itself. I know how to compute this LSSR from the SSSR >> but is it possible to compute this LSSR without the SSSR? > > we do it from the SSSR, since that's also useful information to have.
Yes, since the number of rings in the SSSR is known, you can exit quickly and you could also avoid searching for larger rings etc. > I suspect, though I haven't done more than sketch something on a piece > of paper just now, that it's possible to find the LSSR using a BFS > where, unlike usual BFS algorithms, you keep track of the predecessor > at each node. > > Maybe I'll play around with this a bit tomorrow. At first I thought it was possible but I have tried various "settings" and there always remain problematic cases. You don't have to try anything if you don't have time. I was just wondering if this was a conscious choice in RDKit. Do you have any references for the implementation in RDKit? I'm currently using these papers: Berger et.al., Counterexamples in Chemical Ring Perception, 2008 http://en.scientificcommons.org/43518654 (pdf: http://www.bioinf.uni-leipzig.de/Publications/PREPRINTS/03-012.pdf) Vismara, Union of all the minimum cycle bases of a graph, 1996 http://www.emis.de/journals/EJC/Volume_4/PostScriptfiles/v4i1r9.ps (GPLv2+ source code: http://www.tbi.univie.ac.at/~pmg/cycdeco/ ) The first gives a good overview and references the second paper as the simplest canonical ring set. Still have to go through the details to see how this might compare to what is done in RDKit. Tim > -greg > ------------------------------------------------------------------------------ ThinkGeek and WIRED's GeekDad team up for the Ultimate GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the lucky parental unit. See the prize list and enter to win: http://p.sf.net/sfu/thinkgeek-promo _______________________________________________ OpenBabel-Devel mailing list OpenBabel-Devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/openbabel-devel
