I don't believe that there is a better way to eliminate duplicates apart from using canonical forms (e.g. InChI or canonical SMILES, though InChI also changes the structure so use with care). You can quickly eliminate some duplicates using canonical SMILES or a matrix comparison as you suggest, but to actually be sure you will still have to use a canonical form.
I'm not sure exactly what you're doing but another idea would be to avoid generating some structures in the first place using graph symmetry (available in OB). For example, don't apply the same reaction to symmetry equivalent atoms. - Noel On Fri, 2 Nov 2018 at 18:08, Xianghai Sheng <xsh...@ucmerced.edu> wrote: > Hi Andrew and Noel, > > Thank you for the inspiring answers! > > Andrew: Sorry I didn't make it clear, but 1/2 of the time is only for a > random job I tested and I don't know the scaling of it. Its cost may grow > faster than the searching algorithm. I think it is beneficial to know the > formal time complexity in this sense. But I agree that it is mostly useful > when thinking about large N. I may have to just measure the actual scaling > and deal with it. > > Noel: That's a brilliant idea! I do think most of the time is wasted on > canonicalizing the same graph in my code. I will give it a try. On another > note, the purpose of canonicalization in my code is to eliminate duplicates > in my reaction path network. Is there a better way to do it? Molecules in > my code are represented by bond-electron matrix. A naive approach would be > to sort rows in both matrices and compare them row by row. (I think this > takes O(N^2*logN)) > > Best, > Xianghai > > On Fri, Nov 2, 2018 at 3:31 AM Noel O'Boyle <baoille...@gmail.com> wrote: > >> First of all, I'd recommend using the development code rather than the >> latest release. Also, ensure that hydrogens are suppressed. You may also >> consider trying to avoid multiple canonicalisations of the same graph by >> just writing out a non-canonical SMILES, and only at the end collating them >> and canonicalising. >> >> While I agree with Andrew, it is also true that Open Babel's >> canonicalisation implementation is slow. This is partly due to the fact >> that we calculate all of the graph invariants up-front rather than lazily >> to split ties. In particular, we calculate the pairwise distance of every >> atom from every other atom (as far as I remember). This is O(N**2). >> >> >> Regards, >> - Noel >> >> On Fri, 2 Nov 2018 at 08:02, Andrew Dalke <da...@dalkescientific.com> >> wrote: >> >>> On Nov 2, 2018, at 01:33, Xianghai Sheng <xsh...@ucmerced.edu> wrote: >>> > I am trying to figure out the time complexity (Big O) of converting >>> from OBMol to canonical smiles. >>> >>> I don't think that's a useful way to think about your problem. >>> >>> Graph canonicalization is "at least as computationally hard as the graph >>> isomorphism problem." https://en.wikipedia.org/wiki/Graph_canonization >>> , and graph isomorphism is believed to be quasi-polynomial. >>> >>> That said, I believe the actual algorithm Open Babel uses may have >>> exponential time for some graphs. >>> >>> However, most molecular graphs don't reach the worst-time behavior. >>> >>> Furthermore, time complexity is mostly useful when thinking about large >>> N. Molecules typically have small N, and there may be lower-order terms >>> which dominate the times for small N. >>> >>> If you are interested in the topic of graph canonicalization algorithms >>> in general, you might start with the nauty papers; see >>> http://pallini.di.uniroma1.it/ >>> >>> > I want to know this because getting canonical smiles takes up half of >>> the running time of my reaction path searching program. >>> >>> How would knowing the time complexity help you? >>> >>> While this may be obvious, if canonicalization takes 1/2 the time, then >>> you'll only get 2x speedup even if that time goes to 0. How much work are >>> you willing to do for a 2x speedup? >>> >>> Might it be possible to do about the same amount of work to parallelize >>> your algorithm? For example, if your reaction path search generates a set >>> of nodes which must all be canonicalized in order to evaluate them, then >>> you can do all of those canonicalizations in parallel. >>> >>> Cheers, >>> >>> Andrew >>> da...@dalkescientific.com >>> >>> >>> >>> >>> _______________________________________________ >>> OpenBabel-discuss mailing list >>> OpenBabel-discuss@lists.sourceforge.net >>> https://lists.sourceforge.net/lists/listinfo/openbabel-discuss >>> >>
_______________________________________________ OpenBabel-discuss mailing list OpenBabel-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/openbabel-discuss
