Blog

Enumerating Molecules – Summary of 2 papers

We read:

Faulon, Jean‐Loup, Donald P. Visco, and Diana Roe. “Enumerating Molecules.” Reviews in Computational Chemistry, Volume 21: 209-286.

and

Meringer, Markus. “Structure enumeration and sampling.” Handbook of chemoinformatics algorithms (2010): 233-267.

——

There are 3 main topics in enumeration molecules:
1) Counting (which produces a number)
2) Enumeration (which produces a list of molecular graphs)
3) Sampling (which produces a random molecular graph)

1) Counting

The most important tool in this area is “Polya’s counting method”. It can be used to count derivatives of benzene, by not double counting molecules which can be turned into each other through a rotation.

In general, you identify the similar components of your molecule which you want to label by something. You then work out the subgroup of the symmetric group that acts on these components. Afterwards, the cycle types give rise to some variables and added together to create a polynomial called Z.
Finally, substituting into Z gives a polynomial C, whose coefficients describe how many different graphs exist with the labels corresponding to the variables in the term.

If the number of labels is substitutes instead of the labels in polynomial form, then one obtains the sum of the coefficients directly.

The reason Polya counting works can be understood, by looking at Burnsides lemma, which states that the number of orbits (e.g number of different molecules) equals the average number of fixed points.

Another application of Polya’s counting method comes from applying it to counting series themselves (meta level warning) – this idea gives a counting series for the number of Alkynes (rooted carbon trees). Many variations of Alkynes with other molecules attached can be counted with the initial result. Ironically, Alkanes, which usually seems simpler than alkynes, is one such example, but it is way more complicated to count them.

Faulon suggests that further progress in this direction might lead to a solution of counting isomers in general, which is not currently possible in a closed form way. The closest is by Wang, Li, Wang, which found a counting series for C_iH_{2i+2}O_j, with some further restrictions, which is far from all molecular formulas, but still quite general.

It is, of course, possible to brute-force the problem by constructing all the molecular graphs, which brings us to the second topic.

2) Enumeration

When it comes to enumeration, the “equivalent of Polya counting” in this area is orderly enumeration. It basically consists of having an ordering on the graphs, which allows for the notion of canonical. The best software seems to be McKay’s nauty for enumerating graphs.

The idea is the following:

a) Nodes have an order
b) This induces a lexicographical order on the edges
c) This induces a partial order on the graphs, by letting A be smaller than B if B contains A or B equals A up to a point and then has a larger edge.

If one is interested in particular graphs, rather than all graphs on n nodes:
If the criteria are “consistent” (meaning graphs fail if their subgraphs fail), then it can be incorporated into the algorithm in a natural way (since both the generation and the criteria are “bottom-up”)

An interesting comment on why Goldberg’s theoretical result on enumeration, that runs in polynomial time per outputs cannot be directly implemented (An assumption is made, that the number of (n,q)-graphs is not necessarily greater than the number of (n,q-1)-graphs).

3) Sampling

Dixon and Wilf have a cool and simple algorithm. The main idea is this:
a) Pick a random permutation in S_n, where n is the number of atoms.
b) Then let the permutation act on the edges (a,b) by acting on the nodes a,b individually – compute the cycles of this edge-permutation.
c) For each cycle, let all the edges exist or none of them.
This produces a random graph.

 

Several expansions have been made, such as Goldberg and Jerrums algorithm, which shows that it is theoretically possible to sample molecules in polynomial time. This is peculiar since both the enumeration and enumeration computational complexities are open problems.

Simulated annealing sampling and a “genetic” algorithm are also mentioned.

According to Faulon, the sampling problem lack really strong tools which compare to Polya counting or ordered enumeration.

 

Our thoughts:
These 2 reviews are very similar and if you only read one, then we would recommend the first.

These predate the work of Reymond and the GDB-17 databases of all small molecules organic molecules with 17 non-hydrogen atoms or fewer.

One thing, that is not mentioned in the papers is chemical filters – it seems to this reader, that molecular graphs, such as 4 oxygen-atoms all bound together (O1OOO1) satisfies the mathematical rules, but not the chemical ones. Another example of unreasonable molecular graphs can be found in the creation of Reymond’s GDB-17 databases there were a series of filters applied, which came from chemical considerations of reasonability and not any theory mentioned in this review.

If this example points to a deeper problem, then all the enumeration and counting are merely supersets and upper bounds to the molecules, which would explain why mathematicians are often more interested in these problems than chemists.

Overall, these papers are worth reading.

THE GREAT GOLDEN

He will talk on an correlation model for RNA evolution 3.30PM in the lower floor of Department of Statistics. The slides can be seen here: https://goo.gl/e6r4gx I spoke a week ago on the work I did in Israel: https://tinyurl.com/longisrael

CSML talk: Probabilistic Inference of Nucleotide Coevolution

Michael Golden will be presenting “Probabilistic Inference of Nucleotide Coevolution” at the Computational Statistics and Machine Learning seminar today at 15:30 in the Department of Statistics. His slides are available here.

Abstract 

Pairs of nucleotide positions within biologically functional nucleic acid secondary structures often exhibit evidence of coevolution that is consistent with base-pairing. PICNIC is a probabilistic sequence evolution model that assesses rates of mutation at base-paired sites in alignments of DNA or RNA sequences. PICNIC is able to fully account for an unknown secondary structure, and in doing so can be used to predict a secondary structure shared amongst an alignment of sequences. PICNIC was used to infer rates of coevolution associated with GC, AU (AT in DNA), and GU (GT in DNA) dinucleotides in non-coding RNA alignments, and single-stranded RNA and DNA virus alignments. Strong evidence was found for GU dinucleotides being selectively favoured at base-paired sites in non-coding RNA and RNA virus alignments, with marginal evidence for GT dinucleotides being selectively favoured at base-paired sites in DNA virus alignments. The strength of coevolution at base-paired sites in a SHAPE-MaP-determined HIV-1 NL4-3 RNA secondary structure and a corresponding alignment containing large numbers of HIV group 1M sequences was also measured, finding that the PICNIC-inferred degrees of coevolution were more strongly correlated with experimentally-determined SHAPE-MaP pairing scores than degrees of coevolution measured using three mutual information methods that do not take into account phylogenetic dependencies.

Four Topics in Computational Biology

I will be giving a course with these lecture in TH18 at a advanced undergraduate course at the Department of Statistics

1 Enumeration in Phylogenetics
2. Tree Generating Processes
3. Compatibility
4. Statistical Alignment

5 Physics of Molecules: QM and MM
6 Integrators and Approximations
7 Applications I: Reactions
8 Applications II: Protein Folding

9 Small Molecules
10 Polya Enumeration
11 Graph Grammars and Reaction Prediction
12 3D Prediction from Graphs

13 Modeling the Evolution of Complex Objects: Languages, Patterns, Movements
14 The Comparative Method
15 Example I: Proteins
16 Example II: Networks

They will appear on this page as I finish them:

https://heingroupoxford.com/learning-resources/lectures/

Skype Book Discussion Group in “Computational Complexity of Sampling”

The present version can be found here:

Click to access ComputationalComplexityOfCountingAndSampling.pdf

The author – Istvan Miklos – believes he will always be ahead of the readers in writing. We would then write a review that would be published about the same time as the book was published and we put an extended report on this page:

https://heingroupoxford.com/learning-resources/lectures/

We also give a summarizing lecture when we have finished the book. Earlier when we did this, we met every 2nd day doing about 20 pages each time, but it can depend on the individual book. We did a similar thing to Mike Steels 2016-book, which I believe was beneficial to both authors and readers.

The ideal number of participants in such a group is 3-5. It would have to be online since I will be Israel. I like to choose a time that is either starting or ending of working day so it interpheres minimally with work. If you know somebody interested in participating in this, please tell me. If it proves a crappy book, we will stop reading, but that is not what I expect.