Figure 1. (a) Illustration of the framework structure of the zeolite ZSM-5 in the orthorhombic phase with 12 crystallographically unique Si atoms (adapted from Ref. [4]) (b) The corresponding structure graph emphasizing the symmetry or automorphism of the graph. (c) 1D 29Si MAS NMR spectrum and (d) 2D 29Si INADEQUATE spectrum of the zeolite ZSM-5 with adsorbed p-xylene molecules (adapted from Ref. [4]). (e) The corresponding spectrum graph of the 2D correlation spectrum.
In the initial description of this algorithm [5], the possible assignments of each of the peaks were set to all atoms at the start of the algorithm and a branching "tree-search" (breadth-first search) was employed to find all homomorphisms between the structure and spectrum graphs, testing the subgraphs for homomorphisms at each step along the way. In this paper, we present a number of ways to analyze the spectrum and structure graphs prior to the start of the search so that the initial assignments of the peaks are narrowed down from all atoms. By doing this initial analysis, fewer subgraphs need to be analyzed for homomorphisms at each step in the search, potentially leading to a large gain in the efficiency of the peak assignment algorithm.
1. Valencies of vertices. An inspection of the structure graph in Figure 1(b) reveals that 7, 9, 10, and 12 each have valencies of three compared to the remainder of the silicon atoms which have valencies of four. This difference in valency arises from the fact that each of these silicon atoms has a "self-connectivity" (i.e. 7-7, 9-9, 10-10, 12-12, see Figure 1(a)) which cannot be observed in the two-dimensional INADEQUATE experiment since, in most circumstances, it is not possible to observe J-couplings between identical nuclei. An inspection of the spectrum graph in Figure 1(e) reveals that peaks A, B, E, and G have valencies of three, while the other peaks have valencies of four. This simple analysis narrows down the possible assignments of several of the peaks, revealing that peaks A, B, E, and G must each be assigned to one of {7, 9, 10, 12}, while the remainder of the peaks must each be assigned to one of {1, 2, 3, 4, 5, 6, 8, 11} (see column 1 of Table 1).
| 1. Possible peak | 2. Possible peak | 3. Possible peak | 4. Peak | 5. Symmetry | |
|---|---|---|---|---|---|
| Peak | assignments after examining valencies | assignments after examining valencies of adjacent vertices | assignments after symmetry reduction | assignments after search | related assignment |
| A | 7, 9, 10, 12 | 9, 10 | 9 | 9 | 10 |
| B | 7, 9, 10, 12 | 9, 10 | 10 | 10 | 9 |
| CD | 1, 2, 3, 4, 5, 6, 8, 11 | 1, 2, 3, 4, 5, 6 | 1, 2, 3, 4, 5, 6 | 1, 2 | 5, 6 |
| E | 7, 9, 10, 12 | 7, 12 | 7, 12 | 12 | 7 |
| F | 1, 2, 3, 4, 5, 6, 8, 11 | 1, 3, 4, 6 | 1, 3, 4, 6 | 6 | 1 |
| G | 7, 9, 10, 12 | 7, 12 | 7, 12 | 7 | 12 |
| H | 1, 2, 3, 4, 5, 6, 8, 11 | 8, 11 | 8, 11 | 8 | 11 |
| I | 1, 2, 3, 4, 5, 6, 8, 11 | 1, 3, 4, 6 | 1, 3, 4, 6 | 4 | 3 |
| J | 1, 2, 3, 4, 5, 6, 8, 11 | 1, 3, 4, 6 | 1, 3, 4, 6 | 3 | 4 |
| K | 1, 2, 3, 4, 5, 6, 8, 11 | 1, 2, 3, 4, 5, 6 | 1, 2, 3, 4, 5, 6 | 5 | 2 |
| L | 1, 2, 3, 4, 5, 6, 8, 11 | 8, 11 | 8, 11 | 11 | 8 |
2. Valencies of adjacent vertices. It is also useful to examine the valencies of the vertices that are adjacent to a vertex. Such an inspection of the structure graph reveals that the vertices can be further divided into several groups. For example the vertices of valency 3 can be differentiated further as the valencies of the vertices adjacent to each of 9 and 10 are (3, 4, 4), while the valencies of the vertices adjacent to each of 7 and 12 are (4, 4, 4). Similarly, the vertices of valency 4 can be differentiated further into {8, 11}, {1, 3, 4, 6}, and {2, 5} based on the valencies of adjacent vertices being (3, 3, 3, 4), (3, 4, 4, 4), and (4, 4, 4, 4) respectively. Examination of the valencies of adjacent vertices in the spectrum graph and comparison with the analysis of the structure graph narrows down the possible assignments of the peaks even further: peaks A and B must each be assigned to one of {9, 10}, peaks E and G to one of {7, 12}, peaks H and L each to one of {8, 11}, peaks F, I, and J each to one of {1, 3, 4, 6}, and peak K to one of {1, 2, 3, 4, 5, 6} and CD to two of {1, 2, 3, 4, 5, 6} (see column 2 of Table 1).
3. Automorphism of the structure graph. As mentioned above, the structure graph presented in Figure 1(b) has a symmetry or "automorphism". As a consequence of the automorphism of the structure graph for this particular example, there will be a minimum number of two possible peak assignments which will be related by a symmetry which interchanges pairs of vertices: (1 6) (2 5) (3 4) (7 12) (8 11) (9 10). This property of automorphism can be exploited to increase the efficiency of the peak assignment algorithm, since only half of the possible peak assignments need to be searched; the other half can be generated by the symmetry relationship at the end. This is implemented by assigning one of the peaks to half of its possible assignments. For example, peak A can be assigned to silicon atom 9 since 10 will be generated in the end by the symmetry relationship. Consequently peak B is then assigned to atom 10 with atom 9 being generated in the end by symmetry (see column 3 of Table 1).
Table 1 presents the possible assignments of each of the peaks after each stage of this initial analysis of the structure and spectrum graphs. After the initial analysis (columns 1-3), these possible assignments were used as input to the search algorithm described in Ref. [5] to find all possible homomorphisms from the structure graph to the spectrum graph (column 4). At the end of the search, the symmetry related solutions are generated according to the automorphism of the structure graph (column 5). Of these two possible assignments, the second (column 5) can be shown to be the correct assignment as it gives a good correlation between the 29Si chemical shifts and the mean Si-Si distances [6] obtained from the X-ray diffraction structure [7]a.
There is a large gain in efficiency by incorporating this initial analysis of the structure and spectrum graphs. Without any initial analysis, the search algorithm examined 7662 subgraphs for homomorphisms in 4.8 s to find the same two possible peak assignments. Incorporating the symmetry properties of the structure graph led to an increase in efficiency of a factor of two with the search examining 3831 subgraphs for homomorphisms in 2.4 s to find one of the peak assignments, the second being generated by symmetry. When the initial analysis of the valencies in the structure and spectrum graphs was incorporated, the search for peak assignments required only 0.04 s during which only 32 subgraphs were examined for homomorphisms during the various steps of the search algorithm. For this particular example, this is a gain in efficiency of about two orders of magnitude.
As an additional example, we present the peak assignment for the 29Si MAS NMR spectrum of the room-temperature monoclinic phase of the zeolite ZSM-5 [4]. This a very difficult spectrum to assign since there are 24 inequivalent silicon atoms in the structure, many of the peaks are overlapping and there is little direct information outside of the 2D 29Si INADEQUATE spectrum to identify the peaks. This example again illustrates the large gains in efficiency of the peak assignment algorithm that can be achieved by examining the structure and spectrum graphs prior to starting the search for homomorphisms.
The monoclinic ZSM-5 framework is illustrated in Figure 2(a) along with a subgraph of its corresponding structure graph in Figure 2(b) which has been presented to emphasize the short circuits and the automorphism that exist in the graph. The 1D 29Si MAS NMR and 2D 29Si INADEQUATE spectra are presented in Figure 2(c) and Figure 2(d) respectively. The relative intensities of the peaks in the 1D 29Si MAS NMR spectrum indicate that there are 24 unique silicon atoms which is in agreement with the structure. However, only 15 of the 24 resonances are individually resolved from each other and there are two groups of closely overlapping resonances. The spectrum graph (a subgraph of which is shown in Figure 2(e)) therefore consists of 17 vertices. A dashed edge represents uncertainty in the existence of a correlation between two peaks. Since |A| = 24 > |P| = 17, the task of peak assignment in this case will be to find epimorphisms from the structure graph to the spectrum graph.
Figure 2. (a) Illustration of the framework structure of the zeolite ZSM-5 in the monoclinic phase with 24 crystallographically unique Si atoms (adapted from Ref. [4]) (b) A subgraph of the corresponding structure graph emphasizing the automorphism and circuits of lengths 3 and 4. Note that not all of the edges have been drawn. (c) 1D 29Si MAS NMR spectrum and (d) 2D 29Si INADEQUATE spectrum of the zeolite ZSM-5 in the monoclinic phase (adapted from Ref. [4]). (e) A subgraph of the corresponding spectrum graph of the 2D correlation spectrum emphasizing the circuits of length 4. Only the edges which are unambiguously present have been drawn along with a few ambiguous edges (denoted by the dashed edges).
For this particular example, an analysis of the valencies in the structure and spectrum graphs does not provide any additional information about the identity of any of the peaks since all of the valencies are equal as there are no "self-connectivities" in the structure which would give rise to unobserved correlations in the 2D 29Si INADEQUATE spectrum.
However, it is useful to analyze the graphs for circuits of lengths 3 or 4. An examination of the structure graph reveals that there are two circuits of length 3 containing vertices (4, 5, 13) and (16, 17, 1) and five circuits of length 4: (9, 10, 22, 21), (4, 5, 11, 19), (16, 17, 23, 7), (5, 11, 10, 13), and (17, 23, 22, 1). Note that 5, 10, 11, 17, 22, 23 each lie in two circuits of length 4. An examination of the spectrum graph (considering only definite edges between vertices which represent resolved peaks) reveals that there are two circuits of length 4 involving peaks (V, D, W, T) and (V, U, X, S). Therefore, each of peaks V, D, W, T, U, X, S must be assigned to one of {4, 5, 7, 9, 10, 11, 16, 17, 19, 21, 22, 23}. Furthermore, peak V is present in both of these circuits indicating that peak V must be assigned to one of {5, 10, 11, 17, 22, 23}.
Again, it is also useful to take advantage of the symmetry or automorphism of the structure graph (see Figure 2(b)). The possible assignments of peak V can be reduced to one of {5, 10, 11} prior to the start of the search algorithm, with any symmetry related assignments being generated at the end of the search.
In this manner, we have a starting point for the search which consists of only three possibilities compared to 24 if this initial analysis of the structure and spectrum graphs was not performed. Again, this leads to a large gain in efficiency of the algorithm. The previous version of the algorithm [5] required approximately 300 s to search for the possible peak assignments, whereas with the information gleaned from the initial analysis of the structure and spectrum graphs, the search algorithm required only 30 s to search for the possible peak assignments. Of the two possible assignments, only one (shown in Figure 2(c)) gives a strong correlation between 29Si chemical shifts and mean Si-Si distances [6] obtained from a single crystal X-ray diffraction structure [7]b.
DHB acknowledges the Natural Science and Engineering Research Council of Canada for financial support in the form of a Post-Doctoral Research Fellowship.