summaryrefslogtreecommitdiff
path: root/java/docs/algo/Morgan.html
blob: 0a20be36f42f93bc9fcb2ff877a6700730390298 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
<HTML
><HEAD
><TITLE
></TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
REL="NEXT"
TITLE="Bibliography"
HREF="bibliography.html"></HEAD
><BODY
CLASS="ARTICLE"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="ARTICLE"
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="JOELIB.ALGORITHMS.MORGAN"
></A
>Morgan: Unique atom numbering</H1
><P
>Algorithm to get a unique numbering for molecules (graphs) [<A
HREF="bibliography.html#MOR65"
>mor65</A
>].
<DIV
CLASS="FIGURE"
><A
NAME="JOELIB.ALGORITHMS.MORGAN.LABELING.PSEUDOCODE"
></A
><P
><B
>Figure 1. Pseudocode for the Morgan labeling algorithm</B
></P
><PRE
CLASS="PROGRAMLISTING"
>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</PRE
></DIV
>
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 [<A
HREF="bibliography.html#TC00"
>tc00</A
>] informations can be used.
<DIV
CLASS="FIGURE"
><A
NAME="JOELIB.ALGORITHMS.MORGAN.RENUMBERING.PSEUDOCODE"
></A
><P
><B
>Figure 2. Pseudocode for the Morgan renumbering algorithm</B
></P
><PRE
CLASS="PROGRAMLISTING"
>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</PRE
></DIV
>
The uniquely renumbered molecule can be used to calculate molecule
hashcodes and canonical/unique SMILES representations (see ).</P
></DIV
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="bibliography.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Bibliography</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>