A couple of different sources pointed me to a paper by Dehof et al (Bioinformatics, 2011; doi: 10.1093/bioinformatics/btq718) about bond order assignment by various methods. One of them is the A*-algorithm, which finds paths. Not in the molecule graph, but in a kind of tree of possible bond combinations. Precisely, the tree has a layer for each decision, and a leaf for each combination of decisions.

with the tree shown below. If we pick a particular path through the tree - say to leaf 5 - we get the sequence of colors in the box in the upper center of the image. This corresponds to the assignment on the upper right. Clearly, it has too many double bonds to be carbon skeleton, but still.

For example, here is the usual example of a square four-cycle (G):

with the tree shown below. If we pick a particular path through the tree - say to leaf 5 - we get the sequence of colors in the box in the upper center of the image. This corresponds to the assignment on the upper right. Clearly, it has too many double bonds to be carbon skeleton, but still.

So, it's a nice, simple way to represent the set of solutions. Well, it could be even simpler but representing it as a tree lets the paper authors assign weights to the edges based on the chemical rules outlined in work they reference (Wang et al, 2006). What happens if you don't have any weights? Here are all the assignments from the tree:

## Comments