On 23 June 2010 01:37, Tim Vandermeersch <tim.vandermeer...@gmail.com> wrote: > 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.
Sorry to keep nagging, but the remaining test failure seems to be real bug: http://my.cdash.org/testDetails.php?test=2416695&build=76838 It says that babel -ismi -osmi '[nH]1c2ccccc2c2c3C(=O)NCc3c3c4ccccc4[nH]c3c12' gives '[nH]1c2CCCCc2c2c3C(=O)NCc3c3c4ccccc4[nH]c3c12'. If you look at both in Daylight Depict, you will see that aromaticity is lost in a phenyl ring at the end of five conjugated rings. - Noel ------------------------------------------------------------------------------ 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
