On Tue, Jun 22, 2010 at 11:08 PM, Tim Vandermeersch <tim.vandermeer...@gmail.com> wrote: > 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.
There is now a working version (at least for all structures I've tested) in svn trunk. It is based on lemma 1 from the Vismara paper. There is also a proof so I'm hopeful :-) The rings we now have in the LSSR are known as the relevant cycles. The Berger paper also uses this terminology (relevant cycles of graph G = R(G) ) and lists this ring set as one of the 3 best (canonical, ...) candidates. R(G) can be used for general graphs (<-> planar graphs). Another candidate is the Extended SSR (ESSR) but this only works for planar graphs. The final candidate are the beta-rings but I can't say much about it. > 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
