COMPUTATIONAL CHEMICAL GRAPH THEORY COMPUTATIONAL CHEMICAL GRAPH THEORY Edited by Dennis H. Rouvray Nova Science Publishers New York Nova Science Publishers, Inc. 283 Commack Road Suite 300 Commack, New York 11725 Library of Congress C Data available upon request ISBN 0-941743-84-5 Graphic Design by Elenor Kallberg and Peggy Harvey Printed in the United States of America 1 CONTENTS Preface SECTION A CODIFICATION AND DESCRIPTION OF MOLECULAR SPECIES Chapter 1: Computer-Oriented Molecular Codes J.V. Knop, W.R. Muller, K. Szymanski, S. Nikolic, N. Trinajstic 1.1 Introduction 10 1.2 The N-Tuple Code 11 1.3 The Boundary Code 15 1.4 The Binary Boundary Code 16 1.5 The DAST Code 17 1.6 The Wiswesser Code 20 1.7 The Compact Codes 23 1.8 Some Unsolved Problems 28 1.9 Concluding Remarks 29 Chapter 2: The Problems of Computing Molecular Complexity D. Bonchev 2.1 Introduction 34 2.2 Information Content of a Chemical Compound 35 2.2.1 General Formalism 35 2.2.2 Molecular Information-Theoretic Indices 38 2.3 Topological Components of Molecular Complexity 43 2.4 Complexity of Molecular Electronic Structure 47 2.5 General Molecular Complexity Measures 49 2.6 Developmental of the Superindex 52 2.7 Hierarchical Complexity Measures 54 2.8 Concluding Remarks 59 SECTION B ENUMERATIVE PROCEDURES AND COUNTING POLYNOMIALS Chapter 3: Recent Chemical Applications of Computational Combinatorics and Graph TTieoiy K. Balasubramanian 3.1 Introduction 68 3.2 Computational Algorithms for Edge Groups and Edge Colorings for Graphs 68 3.3 The Algorithms of Liu and Balasubramanian 71 3.4 Outline of Polya's Theorem 75 3.5 Nuclear Magnetic Resonance Graphs 77 3.6 Computer Generation of Character Tables of Symmetric Groups (SJ 78 3.7 Reduced Cycles Indices and Their Applications to Enumeration of NMR Signals and Equivlance Classes 93 2 3.8 Characteristic Polynomials of Spirographs 96 3.9 Conclusions 102 Chapter 4: Some Recent Advances in Counting Polynomials in Chemical Graph Theory H. Hosoya 4.1 Counting Polynomials 106 4.2 Definition and properties of PG(x) and Mc(x) 109 4.3 The Operator Technique 112 4.4 Transfer Matrix for Generating MG(x) and PG(x) 116 4.5 Associated Edge Weighted Directed Graphs 122 4.6 A General Strategy 124 Chapter 5: Conjugated Circuit Computations for Conjugated Hydrocarbons D.J. Klein, W.A. Seitz, T.G. Schmalz 5.1 Introduction 128 5.2 The Model 129 5.3 Core Computational Scheme 130 5.4 Repeating Units and Symmetry 132 5.5 Transfer Matrix Method 135 5.6 Conjugated Circuit Counts 137 5.7 Applications 138 5.8 Extended Polymers 141 5.9 Prospects 144 SECTION C THE CHARACTERIZATION OF MOLECULAR SHAPE Chapter 6: Indexes of Molecular Shape from Chemical Graphs L.B. Kier 6.1 Introduction 132 6.2 Steric or Shape Influence 152 6.3 Shape Quantization Methods 153 6.3.1 Quantization of Influence on Properties 153 6.3.2 Geometric Models 154 6.3.3 Object models 154 6.3.4 Topology/Graph Theory Structure Description 155 6.4 Graph Model of Molecular Shape 156 6.4.1 The General Model 156 6.4.2 First-Order Shape Attribute 157 6.4.3 Second-Order Shape Attribute 158 6.4.4 Third-Order Shape Attribute 159 6.4.5 A Shape Index from Zero-Order Paths 160 6.5 The Shape Information in the Kappa Values 160 6.6 Encoding Atom Differences 162 6.6.1 Modified Atom Count 162 6.6.2 Effect of Alpha Inclusion in Kappas 163 6.7 Values for Small Molecules 165 6.8 Molecular Shape Quantization 166 3 6.8.1 A General Model 166 6.8.2 Higher Order Indexes 166 6.8.3 Additivity 166 6.9 General Applications 167 6.9.1 Shape Similarity 167 6.9.2 Cavity Definition 168 6.9.3 Molecular Flexibility 169 6.10 Specific Applications 170 6.10.1 Pitzer's Acentric Factor 170 6.10.2 Taft Steric Parameter 171 6.10.3 Enzyme Inhibitors 171 6.10.4 Toxicity Analysis 172 6.11 Conclusion 172 Chapter 7: The Topology of Molecular Surfaces and Shape Graphs P.G. Mezey 7.1 Introduction 176 7.2 Shape Graphs Based on Subdivisions of Molecular Surfaces 177 7.3 Selection of the Domains 181 7.4 The Use of Shape Graphs 182 7.5 An Example: Shape Graphs of the Isodensity Contour Surfaces of Chloroethene 184 7.6 Seeing Graphs of Isodensity Contour Surfaces 186 7.7 A Diagrammatic Representation of the Shapes of (Fused Spheres) van der Waals Surfaces 189 7.8 Summary 194 SECTION D THE ROLE OF TOPOLOGICAL INDICES Chapter 8: Computational Aspects of Molecular Connectivity and its Role in Structure- Property Modeling L.N. Hall 8.1 Introduction 202 8.2 Background 203 8.3 Structure Considerations 205 8.3.1 Consideration 1: Atom Electronic Character 206 8.3.2 Consideration 2: Structure-Property Information 206 8.3.3 Consideration 3: Structure Information 208 8.4 Molecular Connectivity Approach 207 8.5 Molecular Cavity Method 210 8.5.1 Order Zero: °X 212 8.5.2 Order One: *X 213 8.5.3 Higher Order Chi Indexes: mXt and mxtv 214 8.6 SAR Applications of Molecular Connectivity Chi Indexes 215 8.6.1 Heat of Atomization of Hydrocarbons and Alcohols 215 8.6.2 Ionization Potential 217 8.6.3 Molar Refraction 218 8.6.4 Chromatographic Retention 219 8.6.5 Phenol Toxicity to Fathead Minnows 220 4 8.6.6 Antiviral Activity of Benzimidazoles Against Flu Virus 221 8.6.7 Bioconcentration Factor for Phenyl and Biphenyl Compounds 222 8.7 Physical significance of Molecular Connectivity Indexes 223 8.8 Characterization of Skeletal Atoms, the Topological State 224 8.9 Conclusions 228 Chapter 9: Recent Developments in the Characterization of Chemical Structure Using Graph-Theoretic Indices S.C. Basak, G.J. Niemi, G.D. Veith 9.1 Introduction 236 9.2 Graphs in Chemistry 237 9.3 Graph Invariants in Chemistry 241 9.4 Graph Invariants in Structure-Activity Relationships (SAR) 242 9.5 Definition and Computation of Parameters 245 9.5.1 Topological Indices 245 9.5.2 Hydrogen Bonding Parameter (HBj) 248 9.5.3 Solvatochromic Parameters 248 9.6 Statistical Analysis 266 9.7 Discussion 268 SECTION E MOLECULAR OPTIMIZATION AND DESIGN TECHNIQUES Chapter 10: Computer-Assisted Studies of Molecular Structure and Olfactory Properties P.C. Jurs, P.A. Edwards 10.1 Introduction 280 10.2 Experimental Procedures 282 10.3 Results Obtained 288 10.4 Discussion of Results 291 10.5 Regression Analysis of Odor Intensity 293 10.6 Discriminant Analysis of Enzyme Activity 294 10.7 Points of Commonality Between the Two Analyses 295 10.8 Conclusions 296 Chapter 11: Molecular Similarity-Based Methods for Selecting Compounds for Screening M.S. Lajiness 11.1 Pharmaceutical Lead Finding 300 11.2 Selection of Compounds for Screening 301 11.3 The Basak Method 305 11.4 Substructural Fragment Methods 306 11.5 Dissimilarity Selection Methods 306 11.6 Computational Efficiency 310 11.7 An Illustrative Example 310 11.8 Conclusions and Summary 312 SUBJECT INDEX 317 5 PREFACE The chapters forming this book are for the most part considerably expanded versions of papers delivered at a special Symposium held during the 1988 Fall Meeting of the American Chemical Society in Los Angeles. This Symposium, which was entitled Computational Graph Theory and Combinatorics, was organized under the auspices of the Division of Computers in Chemistry of the American Chemical Society. The Symposium generated a certain amount of excitement because, for the first time, it had been recognized that chemical graph theory and chemical combinatorics represented a suitable theme for incorporation into the proceedings of an American Chemical Society Meeting. This marked something of a milestone in the development of chemical graph theory and chemical combinatorics, as it signalled that the area has now gained such widespread acceptance among the chemical community at large that it could be said to have come of age. It was thus a great privilege for me to have been asked to organize this symposium, an opportunity that I was delighted to accept. The Symposium, which took place on September 27, 1988, consisted of eleven presentations, each of which was delivered by a key worker in the field. All lecturers had been asked to present their material in the form of an overview as well as to discuss their latest results. It is gratifying to note here that all fulfilled both requests admirably. The outcome is this book which contains eleven chapters describing work carried out in chemical graph theory and chemical combinatorics over the past several years. Because the book comprises a representative collection of such work, it affords a very useful resource for those coming new to our field and for those interested in an authoritative survey of this rapidly growing area. The number of scientific papers appearing in this area has increased at an annual rate of around 25% over the past two decades and is now approaching 700 per year. We believe therefore that this book is a timely addition to the literature on chemical graph theory, and one that is likely to be welcomed by both connoisseurs and neophytes. Although graph theory is becoming an increasingly important tool in many areas of science, its major area of application is in the chemical sciences. Graph theory can trace its origins back to precisely the year 1736 when the mathematician Leonhard Euler solved a celebrated problem of his age known as the Konigsberg bridges problem. Euler's solution was also the first application of graph theory, for it demonstrated that it would be impossible to cross all of the seven bridges spanning the Pregel river in Konigsberg just once without 6 retracing one's footstepsfl]. The earliest chemical applications of graph theory are almost as old. In 1758 graphs were first used to depict the various interactions occurring between sets of molecules undergoing double decomposition reactions [2]. The first use of combinatorics in the chemical context dates from 1871 when Flavitsky [3] made use of recursion formulas for the enumeration of members of the alcohol homologous series. This work was followed in 1875 by Cayley [4] who first enumerated members of the alkane series. In more recent times, computations based on graph-theoretical or combinatorial techniques have become increasingly sophisticated, especially since the advent of the supercomputer. The development of powerful main­ frame computers has enabled computations to be performed which would have been quite unthinkable only thirty years ago. With so much computing power now at their disposal, it is hardly surprising that many chemists have become accomplished programmers in their own right. Interest in computer programs and computer algorithms is thus at an all-time high. This provides yet another reason for our coverage of the methods and techniques currently in use in our area of computational chemistry. To facilitate the reading of this book, we have decided to group together related areas of computation in separate sections. We now briefly outline the contents of each of our five sections. In Section A the somewhat neglected but vitally important topic of classification and codification of molecular species is addressed by Knop et al. This topic deserves wider coverage in contemporary chemical literature, for there is now a real need for the systematic development of a general code applicable to all chemical structures. The problem is greatly exacerbated by the current production of some 400,000 new chemical compounds every year . Existing systems, such as the Chemical Abstracts Service ONLINE system and the International Union of Pure and Applied Chemistry coding system, are based on sets of informally expressed rules which can lead to ambiguities in the coding of molecular structures. The development of codes which satisfy all of Read’s [5] stringent rules is overviewed by Knop et al. and a new code is introduced for polyhex species. In Chapter 2 the fascinating topic of complexity is examined by Bonchev. Complexity, like size, shape, and similarity, is one of a number of terms frequently used by chemists which lacks a precise definition. Graph-theoretical and combinatorial concepts are being increasingly used to make such definitions more rigorous. Here, Bonchev discusses many of the definitions of complexity which have been advanced to date and presents some of his own based on a hierarchical ordering of the components of chemical systems, which may well provide a suitable basis for further developments. In Section B a variety of different enumerative procedures are outlined and the use of counting polynomials is addressed. In Chapter 3, Balasubramanian reviews many of the combinational techniques that have been evolved for the solution of numerous chemical problems ranging from the enumeration NMR signal patterns to the computer generation of chemical isomers. He also describes recent developments in the computation of the characteristic and matching polynomials of specific classes of graphs. The subject of counting polynomials is the principal theme of Chapter 4 by Hosoya.