Parallel algorithm for the computation of characteristic polynomials of chemical graphs

A parallel algorithm is developed for the first time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n³) processors whereas the sequential algorithm takes O(n⁴) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens–Householder methods.     

On the evaluation of the characteristic polynomial of a chemical graph

The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n⁴. Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G. Two new algorithms are described which both have the operation count of the order n³. These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λ_i of the adjacency matrix is also considered. An algorithm is described which requires only n(n ? 1)/2 operations for the solution of this problem.     

Computer generation of spectra of graphs: Applications to C60 clusters and other systems

A computer code based on the Givens–Householder matrix diagonalization method is used to calculate the spectra of graphs containing a large number of vertices. The code is most general in that it can handle graphs containing 200 or more vertices. Further, the code can be used to generate the spectra of weighted graphs. The program requires as input only the neighborhood table of the graph. The spectra of many graphs are generated for the first time in less than a few minutes of computer time. Applications to a number of chemical systems including two forms (foot and hand) of the recently synthesized C₆₀ cluster and the effect of bond alternation on these systems are discussed. In addition, the spectra of square and honeycomb lattices and the characteristic polynomials of the foot and hand forms of the C₆₀ cluster are obtained.     

The characteristic polynomial of a chemical graph

We list uses of, and the computational methods for the characteristic polynomial of a (chemical) graph. Pour computational methods are singled out for more detailed presentation. These are the graphical methods of Sachs, the recurrence formulae for several classes of simple graphs, the method based on Ulam subgraphs, and the Le Verrier — Faddeev — Franic recursive method. The latter method appears, at present, to be the most efficient procedure for the computation of the characteristic polynomials of graphs of sizes with up to even a few hundred sites.Dedicated to Dennis H. Rouvray, the friend and one of the foremost popularizers of chemical graph theory in our time.Research supported by the Robert A. Welch Foundation of Houston, Texas, USA.     

Computer enumeration of walks on directed graphs

A vectorized computer code is developed for the enumeration of walks through the matrix power method for directed graphs. Application of this code to several graphs is considered. It is shown that the coefficients in the generating functions for signed graphs are much smaller in magnitude. It is shown that self-avoiding walks on some graphs can be enumerated as a linear combination of walk GFs of directed paths and rooted-directed paths.     

Computer generation of the characteristic polynomials of chemical graphs

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of vertices that are neighbors of a given vertex and with labels smaller than the label of that vertex. The program generates and stores only the lower triangle of the adjacency matrix in canonical ordering in a one-dimensional array. The program is written in integer arithmetic, and it can be easily modified to real arithmetic. The coefficients in the characteristic polynomials of several graphs were generated in less than a few seconds, thus solving the difficult problem of generating characteristic polynomials of graphs. The characteristic polynomials of a number of very complicated graphs are obtained including for the first time the characteristic polynomial of an honeycomb lattice graph containing 54 vertices.     

Characteristic polynomials of organic polymers and periodic structures

It is shown that the Frame's method (also, Le Verrier-Faddeev's method) for characteristic polynomials of chemical graphs can be extended to periodic graphs and structures. The finite periodic structures are represented by cyclic structures in the Born-von Kárman boundary condition which leads to complex matrices. In this article we demonstrate that our earlier computer program (based on Frame's method) can be extended to these periodic networks. The characteristic polynomials of several lattices such as polydiacetylenes, one-dimensional triangular, square, and hexagonal lattices are obtained. These polynomials can be obtained with very little computer time using this method.     

Generating water clusters and other directed graphs

In this paper we will describe an efficient method to generate directed graphs with bounded in- and out-degree. Though developed for the special case of water clusters, which can be modelled as directed graphs with indegree and outdegree at most 2 that have no two directed edges with the same endpoints, the algorithm is also applicable and implemented in the more general context.     

The use of Frame’s method for the characteristic polynomials of chemical graphs

The evaluation of characteristic polynomials of graphs of any size is an extremely tedious problem because of the combinatorial complexity involved in this problem. While particular elegant methods have been outlined for this problem, a general technique for any graph is usually tedious. We show in this paper that the Frame method for the characteristic polynomial of a matrix is extremely useful and can be applied to graphs containing large numbers of vertices. This method reduces the difficult problem of evaluating the characteristic polynomials to a rather simple problem of matrix products. The coefficients in the characteristic polynomial are generated as traces of matrices generated in a recursive product of two matrices. This method provides for an excellent and a very efficient algorithm for computer evaluation of characteristic polynomials of graphs containing a large number of vertices without having to expand the secular determinant of the matrix associated with the graph. The characteristic polynomials of a number of graphs including that of a square lattice containing 36 vertices are obtained for the first time.     

Conformational and spectroscopic investigation of 3-hydroxyflavone-aluminium chelates

3-Hydroxyflavone (3HF), which is the simplest molecule of the flavonol class, possesses chelating properties towards Al(III). Spectrophotometric methods have shown that the 3HF molecule forms an Al(3HF)2 complex in pure methanol. The structure of this complex, obtained by quantum semi-empirical AM1 method, indicated that complexed 3HF adopts a pyronium form. Structural and electronic modifications induced by chelation are illustrated by the important frequency shifts observed between free and complexed 3HF FT-Raman spectra and by the chemical shifts variations in the 13C NMR spectra of the two species. Complexes with the same stoichiometry were formed when AcO- or MeO- are present in the medium. However, in acidic medium the chelate composition is Al2(3HF).     

Semi-quantitative and semi-empirical versions in the quasi-relativistic SCF-MO-LCAO methods: Numerical calculations for (PtCl6)2−

Quasi-relativistic (QR ) versions of the CNDO and Mulliken–Wolfsberg–Helmholz (MWH) semiempirical methods based on the SCF -QR -MO -LCAO method given earlier are worked out. For the CNDO method only the basic formulas and matrix element expressions are given, while for the MWH one, the parametrization as well as the basis functions and group spinor overlap integral calculation were discussed. (PtCl₆)^2? complex was chosen for a test calculation. The energy level values and LCAO coefficients were obtained and compared with the nonrelativistic calculations. One of the results was the occurrence of a very strong reduction of the spin-orbit interaction due to covalency. The calculation proves the semi-empirical versions of the QR -MO -LCAO method to be quite realizable in practice.     

Enumeration of internal rotation reactions and their reaction graphs

Threefold and twofold internal rotation reactions and their reaction graphs are enumerated using the generalized wreath product method developed by the author in an earlier paper. The correspondence between reaction directed graphs (digraphs) and finite topologies on isomers is established. It is shown that the reaction digraphs can be represented by Borel fields. Atropisomerism in polyphenyl compounds is discussed. Applications to spontaneous generation of optical activity and NMR spectroscopy are considered. Borel fields are enumerated by bumping squares of the upper rows of Young diagrams starting from the Young diagram containing just one row.     

On discerning symmetry properties of graphs

A procedure is outlined which allows the symmetry properties of graphs to be systematically and rigorously investigated. It is based on a search for all the automorphisms of a graph and this is accompanied by suitably applying the procedure for recognizing identical graphs. It consists in finding all the distinctive labeling of the vertices of graph associated with the smallest binary code derived by a particular interpretation of the associated adjacency matrix. No prior cognizance of symmetry operations is required which is in contrast to the usual discussions of the symmetry properties of molecules which are based on the knowledge of pertinent symmetry operations. This is important since in graphs it is neither apparent nor generally possible to simply enlist those permutations of labels which leave the connectivity invariant (i.e., do not alter the form of the adjacency matrix). The procedure is applied to the Petersen graphs and the Desargues-Levi graph, both associated with isomerizations of trigonal bipyramidal complex and other chemical transformations. It is shown that these graphs of high symmetry belong to symmetry groups of order 120 and 240 respectively. The approach can also provide a basis for the development of the symmetry properties of non-rigid molecules in which connectivity is preserved.     

Isomer generation: semantic rules for detection of isomorphism

The problem of exhaustive generation of a nonredundant set of structural formulas (graphs) of acyclic alkanes was considered. A technique based on the compressed adjacency matrix (CAM) was proposed. The algorithm generates CAMs, which encode trees numbered according to the Morgan naming algorithm. Out of this set of CAMs those corresponding to the maximal Morgan codes--which in fact are the CAMs of canonically numbered isomers--must be found. CAMs are conceived as "sentences" of a primitive language. Sentences violating the syntactic and semantic rules of this language have to be discarded. In this paper three semantic rules have been proposed. The algorithm devised is efficient, and the decision to retain or to reject the actual structure does not involve any comparison with other structures. It was proved that several subsets of CAMs will not contain any maximal CAM and therefore it is not necessary to generate them. The whole procedure was illustrated by generating CAMs of all acyclic graphs containing nine vertices.     

Critical evaluation of search algorithms for automated molecular docking and database screening

The DOCK program explores possible orientations of a molecule within a macromolecular active site by superimposing atoms onto precomputed site points. Here we compare a number of different search methods, including an exhaustive matching algorithm based on a single docking graph. We evaluate the performance of each method by screening a small database of molecules to a variety of macromolecular targets. By varying the amount of sampling, we can monitor the time convergence of scores and rankings. We not only show that the site point–directed search is tenfold faster than a random search, but that the single graph matching algorithm boosts the speed of database screening up to 60-fold. The new algorithm, in fact, outperforms the bipartite graph matching algorithm currently used in DOCK. The results indicate that a critical issue for rapid database screening is the extent to which a search method biases run time toward the highest-ranking molecules. The single docking graph matching algorithm will be incorporated into DOCK version 4.0. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1175–1189     

A new validated HPLC method for the determination of quercetin: Application to study pharmacokinetics in rats

A simple, accurate, and reproducible high‐performance liquid chromatography (HPLC) method has been developed and validated for the quantification of quercetin (QR) in rat plasma. The method involves a simple protein precipitation procedure to extract both QR and thymoquinone (TQ), the internal standard. The chromatographic analysis was achieved on a Shimadzu LC 20 A HPLC system equipped with a Supelcosil LC‐18 T C₁₈ column and an isocratic mobile phase consisting of 0.3% trichloroacetic acid in water and acetonitrile HPLC‐grade (50:50, v /v) run at a flow rate of 0.9 mL/min for 13 min. The UV detection wavelength was set at 254 nm. The method exhibited good linearity (R ² > 0.994) over the assayed concentration range (0.10–25 μg/mL) and demonstrated good intra‐day and inter‐day precision and accuracy (relative standard deviations and the deviation from predicted values were <20%). This method was also successfully applied for studying the pharmacokinetics of QR in rats following a single oral dose of QR to evaluate its pharmacokinetic parameters in rats.     

Extended connectivity in chemical graphs

The true nature of the extended connectivity, used in Morgan algorithm for the canonical numerotation of points in chemical graphs, is discussed. An alternative method for its calculation based on the number of walks is described and shown to yield results identical to Morgan's method.     

Pattern-based algorithm for peptide sequencing from tandem high energy collision-induced dissociation mass spectra

A new strategy is reported for extracting complete and partial sequence information from collision-induced dissociation (CID) spectra of peptides, CID spectra are obtained from high energy CID of peptide molecular ions on a four-sector tandem mass spectrometer with an electro-optically coupled microchannel array detector, A peak detection routine reduces the spectrum to a list of peak masses and peak heights, which is then used for sequencing, The sequencing algorithm was designed to use spectral data to generate sequence fits directly rather than to use data to test the fit of series of sequence guesses. The peptide sequencing algorithm uses a pattern based on the polymeric nature of peptides to classify spectral peaks into sets that are related in a sequence-independent manner, It then establishes sequence relationships among these sets, Peak detection from raw data takes 10–20 s, with sequence generation requiring an additional 10–60 s on a Sun 3/60 workstation, The program is written in the C language to run on a Unix platform. The principal advantages of our method are in the speed of analysis and the potential for identifying modified or rare amino acids. The algorithm was designed to permit real-time sequencing but awaits hardware modifications to allow real-time access to CID spectra.     

Improved numerical algorithm for exploring block copolymer mesophases

We present an improved algorithm of the self‐consistent mean‐field implementation that has been recently proposed for the calculation of block copolymer self‐assembly. Without requiring prior knowledge of the symmetry of the mesophase segregation, the algorithm is numerically stable and significantly faster than previously proposed methods. These advantages provide a valuable tool for combinatorial screening of novel stable and metastable structural phases of block copolymers. We apply the method and demonstrate complex mesophases in linear, asymmetric triblock copolymer melts. © 2002 Wiley Periodicals, Inc. J Polym Sci Part B: Polym Phys 40: 1777–1783, 2002