Chemoinformatics Curiosities: The Morgan Algorithm

Apologies to one of my favorite chemistry blogs for the title of this series—it just fit too well!

I’ve become very interested in the field of chemoinformatics lately. It’s mind-boggling to think about how chemoinformatics could influence education, as student responses are digitized. It’s a young field with a lot of potential! A series of upcoming posts investigate some of the interesting aspects of chemoinformatics in a general sense (divorced from its most common bedfellow, chemical biology).

Here’s an interesting problem: how can one systematically and uniquely number the atoms of a molecular graph? We might need to do so, for instance, to compare two structures to see if they’re identical.

One solution would be to assign, systematically, a unique number to each atom in a structure based on connectivity. Atoms with identical connectivity are in identical chemical environments anyway, [1] so this procedure would provide us with a nice way to uniquely assign numbers to the atoms of a molecular graph. The toughest aspect of this solution is that little word “systematically.” Procedures that assign unique numbers to atoms must be designed so that the same numbering scheme results every time, irrespective of how the molecule is drawn. In a nutshell, the numbering must depend only on intrinsic properties of the molecular graph itself, and not at all on how it is represented.

Morgan devised an ingenious algorithm that meets this criterion while working for Chemical Abstracts. Let’s begin by numbering each non-hydrogen according to its “non-hydrogen degree,” that is, the number of heavy atoms to which it is attached. Ignore multiple bonds for now.

Morgan Algorithm: Step 1

Next, a weird, iterative addition trick assigns unique numbers to atoms based on their connectivity. For each atom, sum the degrees of each of its neighbors, and give that number to the atom. Rinse and repeat this process until the numbers are unique as possible. For our tyrosine example, this happens after five iterations…I’ll spare you the details, and show only the final result. Suffice it to say, if we repeated this, we wouldn’t introduce any more uniqueness in the numbers.

Morgan Algorithm: Step 2

At this point, most of the atoms have different labels. Begin at the atom with the highest number, and assign it as “1.” Look at atom 1’s neighbors, and assign the highest as 2, second highest as 3, etc. Then move to atom 2, rinse and repeat for any unassigned atoms attached to atom 2. Where ties emerge, assign the atom with higher bond order the lower number. When all is said and done, we get…

Morgan Algorithm: End Result!

In an ideal world, Morgan’s and related “relaxation” algorithms (which iteratively examine the neighbors of atoms) would assign identical numbers to symmetry-equivalent atoms and different numbers to symmetry-inequivalent atoms in all cases. However, there are known examples of molecules with symmetry-inequivalent atoms that cannot be distinguished by Morgan’s algorithm. For some applications of Morgan’s algorithm in the chemical literature, check these out. The alternative proposals to the Cahn-Ingold-Prelog system are particularly intriguing!

[1] Let’s ignore enantiotopic and diastereotopic groups for now… 😀

Advertisements

5 Comments

  1. Hey Mike – not sure how the aromatic carbons of tyrosine are given different numbers according to this algorithm (e.g. 4 and 5). Is there something I’m missing?

    Most importantly, do you think you could write a post outlining a concrete example of how chemoinformatics could influence education? Maybe it’s just me, but I’m not seeing it it, and I’d like to hear your perspective.

    Reply

  2. James—something I forgot to mention: when two carbons appear to tie, as, e.g., carbons 4 and 5 in tyrosine, the smaller number goes to the carbon with greater bond order with the “issuing point.” The “issuing point” for carbons 4 and 5 is carbon 2, and since carbon 4 is doubly bound while carbon 5 is singly bound, carbon 4 gets the higher priority.

    I will definitely write a full post on my thoughts on chemoinformatics + chem ed in the future, but here’s the condensed version:

    I teach a very large class. Short of spending my entire life evaluating students and providing feedback, it’s difficult to understand how students are doing before exams arrive…and by then, if something’s wrong, it’s too late! To help address this problem, I use technology—students submit answers using ACE Organic online, and I periodically check to see how students are doing. Problems can then be addressed in class or via our course wiki.

    What does all this have to do with chemoinformatics? Well, the answers students submit are machine-readable structures, so there may be a way to use the organizing power of chemoinformatics to shed more light on the “broad picture” of student responses. Think of the age-old process of grading an assignment and realizing that, e.g., every student is SN2’ing at tertiary halides (an extreme, but run with me here). In theory, machines could make identification of these widepread mistakes much easier by grouping responses by similarity or looking for common structural errors.

    These ideas are very different from the way chemical biology has used chemoinformatics, but I think that at the intersection of chemical education and technology, chemoinformatics can be a powerful ally…especially in large courses, where individual attention is tough to provide.

    Reply

  3. Thanks for clarifying, I can see how that would be valuable information. I’ve written about this before, but I’ve been stunned at how much difficulty students can have with just identifying which bonds are broken and formed in each reaction. In my own teaching I’m trying to hammer this point home as much as possible – anecdotally I can tell you it seems to be making a big difference.

    Reply

  4. Something is wrong in the numbering within the second image (and then the last one). Maybe the iterative steps were ignored and the numbering were made randomly for the second one. But if you try to do each step, you should find the same final numbering as the example from Chemoinformatics: A Textbook, J. Gasteiger.

    Sincerely

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s