On 2013-03-27 22:04, Craig James wrote: > > > Reinis Danne <rei4...@gmail.com <mailto:rei4...@gmail.com>>wrote: > > > I think it was the thread where I mentioned I'm working on > > kekulization algorithm using graph theory (maximum matching). It > > has been quite some time when I last looked at that code and it > > is not yet usable. > > > I don't know if this overlaps with your work, but I spent a fair amount > of time on the aromaticity-detection algorithm and improved it by orders > of magnitude. See the comment in kekulize.cpp around line 887 -- copied > below. > > Craig > > NEW ANALYSIS methods: rely on LSSR methods to only target one ring. > Works much faster on fullerens, graphene, etc. > > Recursive function to find a sensible kekule assignment of single and > double bonds for an aromatic ring system. > > Very large aromatic ring systems can be very computationally difficult. > In theory, there are 2^N ways to try assigning single/double to assign > bonds (where N is the number of bonds in the aromatic system). For > large molecules such as fullerenes, this number (e.g. 2^60) exceeds all > computing power in the world. > > To avoid this, three strategies are used. > > 1. The algorithm proceeds by assigning bonds to each complete ring > from the LSSR, rather than treating the whole aromatic system. > That reduces the complexity to roughly O(2^R) where R is the number > of rings in the LSSR. > > 2. Each time a ring is completed (a trial assignment of > single/double), the whole tentative assignment is checked for > sensibility. If any atom has all of its bonds assigned, but > still has a leftover electron, then the assignment fails before a > lot more work is invested. (Atoms connected to bonds that haven't > been examined yet are ignored during this test.) > > 3. When one ring is finished, the next ring is selected by finding the > one "most connected" to previously-considered rings. Say, for > example, we're working on a fullerene and have just finished one > ring. The second ring will be one that's adjacent to the first > ring (one of its bonds is already assigned). Now for the third > ring, we can pick one that's in a "corner" of the first two, that > is, a ring that has TWO bonds already assigned. > > Strategy #3 means that the completed area of the ring system (the bonds > we've already assigned) will tend to have a "minimal perimeter", and any > atom that has one bond assigned will quickly have all of its bonds > assigned. That means that strategy #2 can be used as early as possible > to detect bond assignments that can never work, long before the entire > aromatic system has been examined. Strategy #1 means that we can > typically assign alternating single/double bonds correctly to any > particular ring on the first try. > > Together, these three strategies together mean that even very large > aromatic systems are typically solved in milliseconds.
Great that a number of solutions are being worked on. At least for Carbon based molecules one can relatively easy filter out errors by counting the sum of bond orders on the bonds to each carbon (although there are pathetic cases like carbon monoxide). I would rather not get bond orders from the algorithm than incorrect ones. It is my impression that the total charge on molecules is not (always) taken into account, even if it is present from e.g. quantum chemistry files. > > > > > ------------------------------------------------------------------------------ > Own the Future-Intel® Level Up Game Demo Contest 2013 > Rise to greatness in Intel's independent game demo contest. > Compete for recognition, cash, and the chance to get your game > on Steam. $5K grand prize plus 10 genre and skill prizes. > Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d > > > > _______________________________________________ > OpenBabel-Devel mailing list > OpenBabel-Devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/openbabel-devel > -- David van der Spoel, Ph.D., Professor of Biology Dept. of Cell & Molec. Biol., Uppsala University. Box 596, 75124 Uppsala, Sweden. Phone: +46184714205. sp...@xray.bmc.uu.se http://folding.bmc.uu.se ------------------------------------------------------------------------------ Own the Future-Intel® Level Up Game Demo Contest 2013 Rise to greatness in Intel's independent game demo contest. Compete for recognition, cash, and the chance to get your game on Steam. $5K grand prize plus 10 genre and skill prizes. Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d _______________________________________________ OpenBabel-Devel mailing list OpenBabel-Devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/openbabel-devel
