Structure isomorphism problems

Brief analysis of the internal relationships between the structure isomorphism, SSS, and MSCC problems can help us understand these problems better. The MCSS problem is that of determining all possible maximal common substructures of two (or more) given structures. If the detected maximal common substructure is isomorphic to the smaller of the two given structures, this kind of MCSS problem is, in fact, a substructure isomorphism problem. If the maximal common substructure found is isomorphic to both of the given structures, such a problem belongs to the structure isomorphism problem. Therefore the structure and substructure isomorphism problems are only two special cases of the more general MCSS problem (see also Fig. 1). 

Structure isomorphism problems for general structures are not easy to solve, but substructure isomorphism problems are, however, much more complicated than structure isomorphism problems. In fact, it has been proven that substructure isomorphism problems belong to a set of well-known difficult problems called NP-... 

Because of limitations of space, the structure isomorphism problem will not be further discussed. This chapter will focus on the discussion of the major algorithms and methodologies for solving substructure and maximal common substructure problems and their applications. 

Detection of structure isomorphism. For structure isomorphism problems, the algorithm is used to generate atom-atom correspondences between two chemical structures. In this case, as soon as one MCSS has been detected the search terminates immediately. 

For structure isomorphism problems, the atom-atom correspondence of the two isomorphic structures is calculated from a pair of starting atoms. One starting atom is chosen from the first structure in such a way that it shares the fewest identical EV values with other atoms of the same structure. The other starting atom is chosen from the second structure so that... 

For the structure isomorphism problem, the total number of bonds of one structure is used as the terminating condition. The MCSS candidate that contains the same number of bonds as the query structure does represent the final solution. 

Figure 2 40. To illustrate the isomorphism problem, phenylalanine is simplified to a core without representing the substituents. Then every core atom is numbered arbitrarily (first line). On this basis, the substituents of the molecule can be permuted without changing the constitution (second line). Each permutation can be represented through a permutation group (third line). Thus the first line of the mapping characterizes the numbering of the atoms before changing the numbering, and the second line characterizes the numbering afterwards. In the initial structure (/) the two lines are identical. Then, for example, the substituent number 6 takes the place of substituent number 4 in the second permutation (P2), when compared with the reference molecule.

If the phasing model is not isomorphous with the desired structure, the problem is more difficult. The phases of atomic structure factors, and hence of molecular structure factors, depend upon the location of atoms in the unit cell. In order to use a known protein as a phasing model, we must superimpose the structure of the model on the structure of the new protein in its unit cell and then calculate phases for the properly oriented model. In other words, we must find the position and orientation of the phasing model in the new unit cell that would give phases most like those of the new protein. Then we can calculate the structure factors of the properly positioned model and use the phases of these computed structure factors as initial estimates of the desired phases. 

For substructure isomorphism problems, the atom having the largest number of neighbors within the query structure is chosen to comprise starting pairs with all those atoms from the other structure, each of which has at least the same number of neighbors as that of the query starting atom. 

For the substructure isomorphism problem, the number of atoms of the smaller query structure is used as terminating condition. 

X-Ray diffraction from single crystals is the most direct and powerful experimental tool available to determine molecular structures and intermolecular interactions at atomic resolution. Monochromatic CuKa radiation of wavelength (X) 1.5418 A is commonly used to collect the X-ray intensities diffracted by the electrons in the crystal. The structure amplitudes, whose squares are the intensities of the reflections, coupled with their appropriate phases, are the basic ingredients to locate atomic positions. Because phases cannot be experimentally recorded, the phase problem has to be resolved by one of the well-known techniques the heavy-atom method, the direct method, anomalous dispersion, and isomorphous replacement.1 Once approximate phases of some strong reflections are obtained, the electron-density maps computed by Fourier summation, which requires both amplitudes and phases, lead to a partial solution of the crystal structure. Phases based on this initial structure can be used to include previously omitted reflections so that in a couple of trials, the entire structure is traced at a high resolution. Difference Fourier maps at this stage are helpful to locate ions and solvent molecules. Subsequent refinement of the crystal structure by well-known least-squares methods ensures reliable atomic coordinates and thermal parameters. 

The problem of a priory assessment of stable structure formation is one of the main problems of chemical physics and material science. Its solution, in turn, is directly linked with the regularities of isomorphism, solubility and phase-formation in general. Surely, such problems can be cardinally solved only based on fundamental principles defining the system of physical and chemical criteria of a substance and quantum-mechanical concepts of physics and chemistry of a solid suit it. 

The addition of one or more heavy atoms to a macromolecule introduces differences in the diffraction pattern of the derivative relative to that of the native. If this addition is truly isomorphous, these differences will represent the contribution from the heavy atoms only thus the problem of determining atomic positions is initially reduced to locating the position of a few heavy atoms. Once the positions of these atoms are accurately determined, they are used to calculate a set of phases for data measured from the native crystal. Although, theoretically, one needs only two isomorphous derivatives to determine the three-dimensional structure of a biological macromolecule, in practice more than two are needed. This is due to errors in data measurement and scaling and in heavy-atom positions, as well as lack of isomorphism. 

---