The Morgan Algorithm

The Morgan Algorithm classifies all the congeneric atoms of a compound and selects invariant-labeled atoms (see Section 2.5.3.1). The classification uses the concept of considering the number of neighbors of an atom (connectivity), and does so in an iterative manner (extended connectivity, EC). On the basis of certain rules. 

Two aspects of tlie Morgan Algorithm play a dominant role for structure coding  

---

Various methods have been developed for a unique and unambiguous numbering of the atoms of a molecule and thus for deriving a canonical code for this molecule [76]. Besides eigenvalues of adjacency matrices [77], it is mainly the Morgan Algorithm that is used [79]. 

Figure 2-42. The Morgan Algorithm generates an unambiguous and unique numbering of phenylalanine (see Tutorial, Section 2,S,J,1).

However, it should not be concealed that in some cases the Morgan Algorithm has problems. In some structures the numbering show oscillatoiy behavior (for an example, sec Figure 2-44). Moreover, although equivalent atoms obtain the same extended connectivity value, it cannot always be concluded that atoms with the same extended connectivity value are equivalent. 

Many variations of the Morgan Algorithm were introduced, because of problems finding the terminating condition of stage 1 (oscillating number of equivalent classes [80]) or special atoms with isospcctral points [81],... 

First, both the skeleton and the ligands at a stereocenter have to be numbered independently of each other. The sites of the skeleton can be numbered arbitrarily but then this numbering has to remain fixed all the time in any further operations. The atoms directly bonded to the stereocenter have to be numbered according to rules such as the CIP rules or the Morgan Algorithm (Figure 2-79). 

The Morgan algorithm 5> is a device used by the Chemical Abstracts Service for assigning indices to the nodes of constitutional formulas whose H-atoms have been omitted, i. e. their reduced graphs. If the indices of all atoms are needed, e.g. for the representation of stereochemistry, an additional procedure is needed for establishing those for the H-atoms. Constitutional symmetry is not indicated directly by Morgan indices. 

In order to obtain a vertex numbering similar to the Morgan algorithm, the convention to associate label 1 to the vertex with the largest coefficient and label A (the number of atoms) to that with the smallest one was established. 

A key factor in chemical data analysis is the choice of chemical descriptors. Recent analyses have shown that extended connectivity fingerprint (ECFP) descriptors-an implementation of circular substructural fingerprints native to Pipeline Pilot software (SciTegic, Accelrys, Inc.) based on the Morgan algorithm (2)-are superior for many tasks. Consequendy, they tend to be employed in our analyses herein. 

The Morgan algorithm was initially developed for the description of chemical structures that are searchable by computers [6], The molecule is treated as a mathematical graph. An ordered list of nodes that refers to the chemical symbols is created. This list contains entries that indicate the bond type and the list entry of atoms attached via these particular bonds. 

The first solution uses some algorithm that transforms any connection table of a molecule into a unique, canonical, form. The best known of these, the Morgan algorithm, chooses the numbering based on the numbers and properties of the neighbors of each atom of the structure. It is the basis of the Chemical Abstracts System Chemical Registry Service. There is also a canonicalization scheme for the SMILES notation of a chemical structure. ... 

Usually the canonicalization and hashing procedures do not distinguish the stereoisomers of a molecule. However, Wipke and Dyott describe the SEMA (Stereochemically Extended Morgan Algorithm), which incorporates information relating to double bonds and tetrahedral stereocenters into the Morgan algorithm. 

Figure 7 Computation of the extended connectivity values with the Morgan algorithm for ethylcyclohexane (diagram a). The level I -4 EC values are presented in diagrams b-e...

The EC value for vertex / computed with the Morgan algorithm is equal to the number of walks of length k starting from vertex /, or to the sum of the row / (or column /) of the th power of the adjacency matrix ... 

The matrix computation of EC values involves many more mathematical operations than the Morgan algorithm, but this relationship gives some insight into the meaning of EC and suggest.s. some ways to increa.se its discriminating power. 

---