Morgan: Unique atom numbering

Algorithm to get a unique numbering for molecules (graphs) [mor65].

Figure 1. Pseudocode for the Morgan labeling algorithm

label each atom with its degree;
labels=count the number of different labels;
hasNTchanged=5;
for all time
  label each atom with sum of label+all neighbor labels;
  actLabels=count the number of different labels;
  if actLabels equal labels then
    decrement hasNTchanged;
    if hasNTchanged is zero break loop;
  fi
rof

The sloppy breaking criteria is necessary, because it's possible that the number of different labels can be constant for only two iterations. But that's not so interesting, let's continue with the renumbering part of the Morgan algorithm. As you can see, it's possible, that 'symmetric' atoms in the molecule will have same labels. Is there now a possibility to solve these 'labeling/renumbering' ties ? Yes, additional informations, like bond order and element number can be used for resolving renumbering ties or the suggested Jochum-Gasteiger canonical renumbering [tc00] informations can be used.

Figure 2. Pseudocode for the Morgan renumbering algorithm

calculate the morgan atom labels;
start breadth first search from this atom;
choose node with the highest label and set new atom index to 1;
repeat
  build deque i of atoms with same BFS traversing number i;
  if deque i contains no equal labels
    renumber atoms in order of decreasing atom labels.
  fi
  else
    try to resolve renumbering tie for the equal labels:
      1. prefer atom with higher bond order for renumbering
      2. prefer atom with higher element number for renumbering
      3. ...
    if tie solved
      renumber atoms in order of decreasing atom labels.
    fi
    else
      show renumbering tie warning;
    esle
  esle
  increment i;
until all atoms are numbered

The uniquely renumbered molecule can be used to calculate molecule hashcodes and canonical/unique SMILES representations (see ).

		Next
		Bibliography