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