Computer generation of acyclic graphs based on local vertex invariants and topological indices. Derived canonical labelling and coding of trees and alkanes

A new procedure (GENLOIS) is presented for generating trees or certain classes of trees such as 4-trees (graphs representing alkanes), identity trees, homeomorphical irreducible trees, rooted trees, trees labelled on a certain vertex (primary, secondary, tertiary, etc.). The present method differs from previous procedures by differentiating among the vertices of a given parent graph by means of local vertex invariants (LOVIs). New graphs are efficiently generated by adding points and/or edges only to non-equivalent vertices of the parent graph. Redundant generation of graphs is minimized and checked by means of highly discriminating, recently devised topological indices based either on LOVIs or on the information content of LOVIs. All trees onN + 1 (N + 1 < 17) points could thus be generated from the complete set of trees onN points. A unique cooperative labelling for trees results as a consequence of the generation scheme. This labelling can be translated into a code for which canonical rules were recently stated by A.T. Balaban. This coding appears to be one of the best procedures for encoding, retrieving or ordering the molecular structure of trees (or alkanes).Dedicated to Professor Alexandru T. Balaban on the occasion of his 60th anniversary.     

Analysis of molecular chirality using the lattice model of spatial structure

A lattice model of the spatial structure of a molecule is suggested. A broken line is constructed to characterize atoms and molecular fragments. The line is a spiral (left or right) embracing the whole lattice containing the molecule. The mutual arrangement of molecular fragments along the broken line is described by a molecular code. The code contains all the necessary information about molecular conformation and configuration in compressed form. Comparing the codes makes it possible to evaluate the structural similarity and dissimilarity of molecules. For example, one can easily estimate the chirality level for enantiomers. Using this approach is demonstrated on various model structures. A. V. Bogatskii Physicochemical Institute, Ukrainian Academy of Sciences. Odessa State University. Translated fromZhurnal Strukturnoi Khimii, Vol. 39, No. 3, pp. 541–546, May–June, 1998. This work was supported by INTAS grant INTAS-UA 95-0060.     

On decompositions of leapfrog fullerenes

It is shown that given a fullerene F with the number of vertices n divisible by 4, and such that no two pentagons in F share an edge, the corresponding leapfrog fullerene Le(F) contains a long cycle of length 3n − 6 missing out only one hexagon.     

Lattice sum calculations for 1/rp interactions via multipole expansions and Euler summation

A method is developed here for doing multiple calculations of lattice sums when the lattice structure is kept fixed, while the molecular orientations or the molecules within the unit cells are altered. The approach involves a two‐step process. In the first step, a multipole expansion is factored in such a way as to separate the geometry from the multipole moments. This factorization produces a formula for generating geometry constants that uniquely define the lattice structure. A direct calculation of these geometry constants, for all but the very smallest of crystals, is computationally impractical. In the second step, an Euler summation method is introduced that allows for efficient calculation of the geometry constants. This method has a worst case computational complexity of O(( log N)²/N), where N is the number of unit cells. If the lattice sum is rapidly converging, then the computational complexity can be significantly less than N. Once the geometry constants have been calculated, calculating a lattice sum for a given molecule becomes computationally very fast. Millions of different molecular orientations or molecules can quickly be evaluated for the given lattice structure. © 2000 John Wiley & Sons, Inc. J Comput Chem 22: 208–215, 2001     

Excitation spectrum of Hubbard model with infinite electron repulsion on strip‐type triangular lattices

The estimations of the stability region of the lattice ferromagnetic ground state in the space of model parameters are found. For the triangular lattice strip formed by L segments with the total number of electrons N=L+1 we derived the effective Hamiltonians describing the low‐energy states of the strips and obtained the analytical estimations for above stability region. The possibility of the magnetic transition with the jump of the ground‐state spin between minimal and maximal values has also been shown. For the strip with N=L and an alternating value of the one‐site potential energy, we have obtained the exact relation between electron parameters, which provides the ferromagnetic character of the lattice ground state. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 253–259, 2001     

Effect of Bulkiness on Reversible Substitution Reaction at MnII Center with Concomitant Movement of the Lattice DMF: Observation through Single‐Crystal to Single‐Crystal Fashion

The porous coordination polymer ({[Mn(L)H₂O](H₂O)_1.5(dmf)}_n, 1 ) (DMF=N,N‐dimethylformamide) exhibits variety of substitution reactions along with movement of lattice DMF molecule depending upon bulkiness of the external guest molecules. If pyridine or 4‐picoline is used as a guest, both lattice and coordinated solvent molecules are simultaneously substituted (complexes 6 and 7 , respectively). If a bulky guest like aniline is used, a partial substitution at the metal centers and full substitution at the channels takes place (complex 8 ). If the guest is 2‐picoline (by varying the position of bulky methyl group with respect to donor N atom), one Mn^II center is substituted by 2‐picoline, whereas the remaining center is substituted by a DMF molecule that migrates from the channel to the metal center (complex 9 ). Here, the lattice solvent molecules are substituted by 2‐picoline molecules. For the case of other bulky guests like benzonitrile or 2,6‐lutidine, both the metal centers are substituted by two DMF molecules, again migrating from the channel, and the lattice solvent molecules are substituted by these guest molecules (complex 10 and 11 , respectively). A preferential substitution of pyridine over benzonitrile (complex 12 ) at the metal centers is observed only when the molar ratio of PhCN:Py is 95:5 or less. For the case of an aliphatic dimethylaminoacetonitrile guest, the metal centers remain unsubstituted (complex 13 ); rather substitutions of the lattice solvents by the guest molecules take place. All these phenomena are observed through single crystal to single crystal (SC–SC) phenomena.     

The first and second largest Merrifield–Simmons indices of trees with prescribed pendent vertices

The Merrifield–Simmons index of a graph G is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent-vertex sets of G. By T(n,k) we denote the set of trees with n vertices and with k pendent vertices. In this paper, we investigate the Merrifield–Simmons index for a tree T in T(n,k). For all trees in T(n,k), we determined unique trees with the first and second largest Merrifield–Simmons index, respectively.     

Structural data representation and search for structural analogs in molecular spectroscopy databases

A method for encoding structural formulas of organic compounds using two varieties of the tree code is suggested. The tree code is a sequence of symbols, each corresponding to an edge of a molecular graph traced around in width or in depth. The deep tree code provides compact storage of structural formulas and rapid substructure search. The wide tree code is a basis for a structure collection classifier providing quick access to structurally related compounds. Three techniques for selecting structural analogs of the compound using the classifier are proposed. Databases on mass and¹³C NMR spectra serve as illustrations. Novosibirsk Institute of Organic Chemistry, Siberian Branch, Russian Academy of Sciences. Translated fromZhurnal Strukturnoi Khimii, Vol. 37, No. 6, pp. 1129–1139, November–December, 1996. Translated by L. Smolina     

Nucleic acid sequence design via efficient ensemble defect optimization

We describe an algorithm for designing the sequence of one or more interacting nucleic acid strands intended to adopt a target secondary structure at equilibrium. Sequence design is formulated as an optimization problem with the goal of reducing the ensemble defect below a user‐specified stop condition. For a candidate sequence and a given target secondary structure, the ensemble defect is the average number of incorrectly paired nucleotides at equilibrium evaluated over the ensemble of unpseudoknotted secondary structures. To reduce the computational cost of accepting or rejecting mutations to a random initial sequence, candidate mutations are evaluated on the leaf nodes of a tree‐decomposition of the target structure. During leaf optimization, defect‐weighted mutation sampling is used to select each candidate mutation position with probability proportional to its contribution to the ensemble defect of the leaf. As subsequences are merged moving up the tree, emergent structural defects resulting from crosstalk between sibling sequences are eliminated via reoptimization within the defective subtree starting from new random subsequences. Using a Θ(N³) dynamic program to evaluate the ensemble defect of a target structure with N nucleotides, this hierarchical approach implies an asymptotic optimality bound on design time: for sufficiently large N, the cost of sequence design is bounded below by 4/3 the cost of a single evaluation of the ensemble defect for the full sequence. Hence, the design algorithm has time complexity Ω(N³). For target structures containing N ∈{100,200,400,800,1600,3200} nucleotides and duplex stems ranging from 1 to 30 base pairs, RNA sequence designs at 37°C typically succeed in satisfying a stop condition with ensemble defect less than N/100. Empirically, the sequence design algorithm exhibits asymptotic optimality and the exponent in the time complexity bound is sharp. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2011     

A flexible triangulation method to describe the solvent-accessible surface of biopolymers

A relatively simple protein solvent-accessible surface triangulation method for continuum electrostatics applications employing the boundary element method is presented. First, the protein is placed onto a three-dimensional lattice with a specified lattice spacing. To each lattice point, a box is assigned. Boxes located in the solvent region and in the interior of the protein are removed from the set. Improper connections between boxes and the possible existence of cavities in the interior of the protein which would destroy the proper connectivity of the triangulated surface are taken care of. The remaining set of boxes define the outer contour of the protein. Each free face exposed to the solvent of the remaining set of boxes is triangulated after the surface defined by the free faces has been smoothed to follow the shape of the macromolecule more accurately. The final step consists of a mapping of triangle vertices onto a set of surface points which define the solvent-accessible surface. Normal vectors at triangle vertices are obtained also from the free faces which define the orientation of the surface. The algorithm was tested for six molecules including four proteins; a dipeptide, a helical peptide consisting of 25 residues, calbindin, lysozyme, calmodulin and cutinase. For each molecule, total areas have been calculated and compared with the result computed from a dotted solvent-accessible surface. Since the boundary element method requires a low number of vertices and triangles to reduce the number of unknowns for reasons of efficiency, the number of triangles should not be too high. Nevertheless, credible results are obtained for the total area with relative errors not exceeding 12% for a large lattice spacing (0.30 nm) while close to zero for a smaller lattice spacing (down to 0.16 nm). The output of the triangulation computer program (written in C++) is rather simple so that it can be easily converted to any format acceptable for any molecular graphics programs.     

Computer generation of matching polynimials of chemical graphs and lattices

A computer program in Pascal is developed for computing the matching polynomials of graphs and lattices. This program is based on the recursive relation for matching polynomials outlined by Hosoya [Bull. Chem. Soc. Jpn., 44 , 2332 (1971)], Gutman and Hosoya [Theor. Chim. Acta, 48 , 279 (1978)], and others. The graph whose matching polynomial is of interest is reduced recursively until the graph reduces to several trees. The characteristic polynomial of a tree is the same as the matching polynomial. The characteristic polynomials of resulting trees are computed using the computer program based on Frame's method developed by Balasubramanian [Theor. Chim. Acta, 65 , 49 (1984)]; J. Comput. Chem., 5 , 387 (1984). The resulting polynomials are then assembled to compute the matching polynomial of the initial graph. The program is especially useful in generating the matching polynomials of graphs containing a large number of vertices. The matching polynomials thus generated are potentially useful in several applications such as lattice statistics (dimer covering problem), aromaticity, valence bond methods (enumeration of perfect matchings) in the calculation of grand canonical partition functions, in the computation of thermodynamic properties of saturated hydrocarbons, and in chemical documentation.     

Hindered rotation of the dimethylamino and dimethylthioamide groups in two ortho substituted N,N-dimethylthiobenzamides

Hindered rotation in two o-substituted N,N-dimethylthiobenzamides was investigated by variable temperature ¹H NMR spectroscopy. For one compound, the enthalpies and entropies of activation for (i) thioamide group rotation around the Ar? C bond and (ii) dimethylamino group rotation around the C? N bond were obtained by full line shape analysis; a possible coupling between the two processes is discussed. A new simple method has also been applied to the analysis of dimethylamino exchange and results are in complete agreement with the full line shape analysis with somewhat better precision.     

The simplest coronoids: Hollow hexagons

Hollow hexagons form a subclass of primitive coronoid systems. The macrocyclic aromatic hydrocarbon kekulene corresponds to a hollow hexagon. The hollow hexagons for given numbers of hexagonal units (h) were enumerated by computer aid, but also an analytical solution for the numbers of hollow hexagons was achieved. For the Kekulé structure counts (k) of a hollow hexagon a general formula is reported. Also the maximum and minimumK numbers are considered.This article is Part VI of the series Enumeration and Classification of Coronoid Hydrocarbons. For Part V, see ref. [36].     

Hamiltonian circuits,Hamiltonian paths and branching graphs of benzenoid systems

A benzenoid systemH is a finite connected subgraph of the infinite hexagonal lattice with out cut bonds and non-hexagonal interior faces. The branching graphG ofH consists of all vertices ofH of degree 3 and bonds among them. In this paper, the following results are obtained:

1. A necessary condition for a benzenoid system to have a Hamiltonian circuit.
2. A necessary and sufficient condition for a benzenoid system to have a Hamiltonian path.
3. A characterization of connected subgraphs of the infinite hexagonal lattice which are branching graphs of benzenoid systems.
4. A proof that if a disconnected subgraph G of the infinite hexagonal lattice given along with the positions of its vertices is the branching graph of a benzenoid system H, then H is unique.

     

On the enumeration of phase diagrams

The topological isomorphism of polyhedra with trivalent vertices and solid-liquid diagrams of three-component systems allows the problem of constructing the complete set of the topological types of diagrams with a given set of characteristics to be reduced to the problem of the generation of marked cubic graphs, which are the Schlegel projections of polyhedra. The problem of the enumeration of possible topological types of melting diagrams containing M binary and N ternary stoichiometric congruently melting compounds is considered. Relations between the topological characteristics of such diagrams are given. The total number of topologically different types of melting diagrams with one binary and one ternary congruently melting compounds was found to be 64.     

Folding Lattice HP Model of Proteins Using the Bond‐Fluctuation Model

In this paper, we find ‘good’ amino acid sequences that fold to a desired “target” structure as a ground state conformation of lowest accessible free energy using the modified bond‐fluctuation lattice model. In our protein lattice model, bond lengths are set to vary between one and √2 in three dimensions. Our results agree well with the native state energies E_N. Comparisons with the “putative native state” (PNS) energy E_PNS and the “hydrophobic zippers” (HZ) energy E_HZ are made. For every sequence, the global energy minimum is found to have multiple degeneracy of conformations, which is the same result as for the constraint‐based hydrophobic core construction (CHCC) method. The interior conformations of the ground states are also discussed.     

Thermo-sensitive colloidal crystals of silica spheres in the presence of large spheres with poly (N-isopropyl acrylamide) shells

Thermo-sensitive colloidal crystals are prepared simply by mixing colloidal silica spheres and large thermo-sensitive gel spheres. The thermo-reversible change in the lattice spacing of colloidal crystals of monodisperse silica spheres (CS82, 103 nm in diameter) depends on the size of the admixed temperature-sensitive gel spheres. For spheres with sizes less and greater than that of the silica spheres, the lattice spacing upon temperature increase above the lower critical solution temperature of poly(N-isopropyl acrylamide) decreases (cf. Okubo et al. Langmuir 18:6783, 2002) and increases, respectively. A mechanism, which is able to explain these experimental findings, is proposed. Moreover, crystal growth rates and the rigidities of the thermo-sensitive colloidal crystals are studied.     

Maximum Randić index on Trees with <Emphasis Type="Italic">k</Emphasis>-pendant Vertices

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertices u and v in G. Let T be a tree with n vertices and k pendant vertices. In this paper, we give a sharp upper bound on Randić index of T.     

Isorpectral multitrees

We examined trees with one multiple edge (of multiplicityk) and report all isospectral graphs found when the number of vertices was n < 9. Tile search for isospectrul multitrees was carried out systematically by constructing the characteristic polynomials of all trees having one weighted edge. For all multitrees havingn < 7 vertices, we tabulated the coefficients of the characteristic polynomial. We restricted the analysis to trees with Me maximal valencyd = 4. The number of graphs considered exceeds 300. The smallest pair of isospectral multitrees (i.e. trees with a multiple edge) hasn = 6 vertices, There is a pair of trees whenn = 7, three pairs whenn = 8, and five pads whenn = 9. In all cases, whenk = I is assumed, isospectral multitrees reduce to the same tree. Whenk = 0 is assume(], isospectral trees produce either the same disconnected graph, or an isospectral forest.Dedicated to Basil E. Gillam, Professor emeritus of the Department of Mathematics and Computer Science at Drake University.Reported in part at the 1986 International Congress of Mathematicians, Berkeley, California, USA.Operated for the U.S. Department of Energy by the Iowa State University under Contract No. W-7405-Eng-82. This work was supported in part by the Office of R.S. Hansen, Director.