Faulon J.L., Bender A. Handbook of Chemoinformatics Algorithms

Подождите немного. Документ загружается.

Contributors

Tatsuya Akutsu

Institute for Chemical Research

Kyoto University

Uji, Japan

Amy L. Bauer

Theoretical Biology and Biophysics

Group

Theoretical Division, Los Alamos

National Laboratory

Los Alamos, New Mexico

Pablo Carbonell

Institute of Systems and

Synthetic Biology

University of Evry

Evry, France

Robert D. Clark

Biochemical Infometrics and

School of Informatics

Indiana University

Bloomington, Indiana

James R. Faeder

Department of Computational Biology

University of Pittsburgh

School of Medicine

Pittsburgh, Pennsylvania

Jean-Loup Faulon

Department of Biology

University of Evry

Evry, France

Nikolas Fechner

Department of Computer Architecture

University of Tübingen

Tübingen, Germany

Alexander Golbraikh

Division of Medicinal Chemistry and

Natural Products

University of North Carolina

Chapel Hill, North Carolina

Rajarshi Guha

NIH Chemical Genomics Center

Rockville, Maryland

Georg Hinselmann

Department of Computer Architecture

University of Tübingen

Tübingen, Germany

William S. Hlavacek

Theoretical Biology and Biophysics

Group

Theoretical Division, Los Alamos

National Laboratory

Los Alamos, New Mexico

Ovidiu Ivanciuc

Department of Biochemistry and

Molecular Biology

University of Texas Medical Branch

Galveston, Texas

Shawn Martin

Sandia National Laboratories

Albuquerque, New Mexico

Markus Meringer

German Aerospace Center (DLR)

Oberpfaffenhofen, Germany

Milind Misra

Sandia National Laboratories

Albuquerque, New Mexico

xii Contributors

Fangping Mu

Theoretical Biology and Biophysics

Group

Theoretical Division, Los Alamos

National Laboratory

Los Alamos, New Mexico

Diana C. Roe

Department of Biosystems Research

Sandia National Laboratories

Livermore, California

Alexander Tropsha

Division of Medicinal Chemistry and

Natural Products

University of North Carolina

Chapel Hill, North Carolina

Donald P. Visco, Jr.

Department of Chemical Engineering

Tennessee Technological

University

Cookeville, Tennessee

Jörg Kurt Wegner

Integrative Chem-/Bio-Informatics

Tibotec (Johnson & Johnson)

Mechelen, Belgium

Egon L. Willighagen

Department of Pharmaceutical

Biosciences

Uppsala University

Uppsala, Sweden

Representing

Two-Dimensional (2D)

Chemical Structures

with Molecular Graphs

Ovidiu Ivanciuc

CONTENTS

1.1 Introduction........................................................................2

1.2 Elements of Graph Theory........................................................2

1.2.1 Graphs .....................................................................3

1.2.2 Adjacency, Walks, Paths, and Distances .................................5

1.2.3 Special Graphs ............................................................7

1.2.4 Graph Matrices............................................................8

1.2.4.1 Adjacency Matrix...............................................8

1.2.4.2 Laplacian Matrix ...............................................9

1.2.4.3 Distance Matrix...............................................10

1.3 Chemical and Molecular Graphs ...............................................11

1.3.1 Molecular Graphs .......................................................11

1.3.2 Molecular Pseudograph.................................................13

1.3.3 Molecular Graph of Atomic Orbitals...................................13

1.3.4 Markush Structures .....................................................14

1.3.5 Reduced Graph Model ..................................................15

1.3.6 Molecule Superposition Graphs........................................17

1.3.7 Reaction Graphs ........................................................18

1.3.8 Other Chemical Graphs.................................................19

1.4 Weighted Graphs and Molecular Matrices .....................................20

1.4.1 Weighted Molecular Graphs............................................20

1.4.2 Adjacency Matrix .......................................................21

1.4.3 Distance Matrix .........................................................22

1.4.4 Atomic Number Weighting Scheme Z .................................22

1.4.5 Relative Electronegativity Weighting Scheme X ......................23

1.4.6 Atomic Radius Weighting Scheme R ..................................24

1.4.7 Burden Matrix...........................................................24

1.4.8 Reciprocal Distance Matrix ............................................25

1.4.9 Other Molecular Matrices ..............................................27

1.5 Concluding Remarks ............................................................27

References .............................................................................27

2 Handbook of Chemoinformatics Algorithms

1.1 INTRODUCTION

Graphs are used as an efficient abstraction and approximation for diverse chemical

systems, such as chemical compounds, ensembles of molecules, molecular fragments,

polymers, chemical reactions, reaction mechanisms, and isomerization pathways.

Obviously, the complexity of chemical systems is significantly reduced whenever

they are modeled as graphs. For example, when a chemical compound is represented

as a molecular graph, the geometry information is neglected, and only the atom con-

nectivity information is retained. In order to be valuable, the graph representation of

a chemical system must retain all important features of the investigated system and

has to offer qualitative or quantitative conclusions in agreement with those provided

by more sophisticated methods. All chemical systems that are successfully modeled

as graphs have a common characteristic, namely they are composed of elements that

interact between them, and these interactions are instrumental in explaining a property

of interest of that chemical system. The elements in a system are represented as graph

vertices, and the interactions between these elements are represented as graph edges.

In a chemical graph, vertices may represent various elements of a chemical system,

such as atomic or molecular orbitals, electrons, atoms, groups of atoms, molecules,

and isomers. The interaction between these elements, which are represented as graph

edges, may be chemical bonds, nonbonded interactions, reaction steps, formal con-

nections between groups of atoms, or formal transformations of functional groups.

The chapter continues with an overview of elements of graph theory that are impor-

tant in chemoinformatics and in depicting two-dimensional (2D) chemical structures.

Section 1.3 presents the most important types of chemical and molecular graphs,

and Section 1.4 reviews the representation of molecules containing heteroatoms and

multiple bonds with weighted graphs and molecular matrices.

1.2 ELEMENTS OF GRAPH THEORY

This section presents the basic definitions, notations, and examples of graph theory

relevant to chemoinformatics. Graph theory applications in physics, electronics,

chemistry, biology, medicinal chemistry, economics, or information sciences are

mainly the effect of the seminal book Graph Theory of Harary [1]. Several other books

represent essential readings for an in-depth overview of the theoretical basis of graph

theory: Graphs and Hypergraphs by Berge [2]; Graphs and Digraphs by Behzad,

Chartrand, and Lesniak-Foster [3]; Distance in Graphs by Buckley and Harary [4];

Graph Theory Applications by Foulds [5]; Introduction to Graph Theory by West [6];

Graph Theory by Diestel [7]; and Topics in Algebraic Graph Theory by Beineke and

Wilson [8]. The spectral theory of graphs investigates the properties of the spectra

(eigenvalues) of graph matrices, and has applications in complex networks, spectral

embedding of multivariate data, graph drawing, calculation of topological indices,

topological quantum chemistry, and aromaticity. The major textbook in the spectral

theory of graphs is Spectra of Graphs. Theory and Applications by Cvetkovi´c, Doob,

and Sachs [9].An influential book on graph spectra applications in the quantum chem-

istry of conjugated systems and aromaticity is Topological Approach to the Chemistry

of Conjugated Molecules by Graovac, Gutman, and Trinajsti´c [10]. Advanced topics

Representing Two-Dimensional Chemical Structures with Molecular Graphs 3

of topological aromaticity are treated in KekuléStructures in Benzenoid Hydrocarbons

by Cyvin and Gutman [11]; Introduction to the Theory of Benzenoid Hydrocarbons

by Gutman and Cyvin [12]; Advances in the Theory of Benzenoid Hydrocarbons by

Gutman and Cyvin [13]; Theory of Coronoid Hydrocarbons by Cyvin, Brunvoll, and

Cyvin [14]; and Molecular Orbital Calculations Using Chemical Graph Theory by

Dias [15]. The graph theoretical foundation for the enumeration of chemical isomers

is presented in several books: Graphical Enumeration by Harary and Palmer [16];

Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds by Pólya

and Read [17]; and Symmetry and Combinatorial Enumeration in Chemistry by Fujita

[18].A comprehensive history of graph theory can be found in the book Graph Theory

1736–1936 by Biggs, Lloyd, and Wilson [19].

The firstedited book on chemical graphs is Chemical Applications of Graph Theory

by Balaban [20]. Several comprehensive textbooks on chemical graphs are available,

such as Chemical GraphTheory by Trinajsti´c[21], Mathematical Concepts in Organic

Chemistry by Gutman and Polansky [22], and Handbook of Chemoinformatics by

Gasteiger [23]. Applications of topological indices in quantitative structure–activity

relationships (QSAR) are presented in Molecular Connectivity in Chemistry and Drug

Research by Kier and Hall [24], Molecular Connectivity in Structure–ActivityAnalysis

by Kier and Hall [25], Molecular Structure Description. The Electrotopological State

by Kier and Hall [26], Information Theoretic Indices for Characterization of Chemical

Structure by Bonchev [27], and Topological Indices and Related Descriptors in QSAR

and QSPR by Devillers and Balaban [28]. A comprehensive text on reaction graphs is

Chemical Reaction Networks. A Graph-Theoretical Approach by Temkin, Zeigarnik,

and Bonchev [29], and a graph-theoretical approach to organic reactions is detailed in

Synthon Model of Organic Chemistry and Synthesis Design by Koˇca et al. [30]. Graph

algorithms for drug design are presented in Logical and Combinatorial Algorithms

for Drug Design by Golender and Rozenblit [31]. Graph theory concepts relevant to

chemoinformatics are introduced in this section, together with examples of graphs

and graph matrices.

1.2.1 GRAPHS

A graph G(V, E) is an ordered pair consisting of a vertex set V(G) and an edge set

E(G). Each element {i, j} ∈ E (where i, j ∈ V) is said to be an edge joining vertices

i and j. Because each edge is defined by an unordered pair of vertices from V, the

edge from vertex i to vertex j is identical with the edge from vertex j to vertex I,

{i, j}={j, i}. The number of vertices N defines the order of the graph and is equal to

the number of elements in V(G), N =|V(G)|, and the number of edges M is equal to

the number of elements in E(G), M =|E(G)|. Several examples of graphs relevant

to chemistry are shown in Graphs 1.1 through 1.5.

Vertices and edges in a graph may be labeled. A vertex with the label i is indicated

here as v

.An edge may be denoted by indicating the two vertices that define that edge.

For example, the edge connecting vertices v

and v

may be denoted by e

, e

i,j

, {i, j},

or v

. Usually, graph vertices are labeled from 1 to N, V(G) ={v

, v

, ..., v

}, and

graph edges are labeled from 1 to M, E(G) ={e

, e

, ..., e

}. There is no special rule

in labeling graphs, and a graph with N vertices may be labeled in N! different ways.

4 Handbook of Chemoinformatics Algorithms

1.1 1.2 1.3

1.4 1.5

A graph invariant is a number, sequence of numbers, or matrix computed from the

graph topology (information contained in the V and E sets) that is not dependent on the

graph labeling (the graph invariant has the same value for all N! different labelings of

the graph). Two obvious graph invariants are the number of vertices N and the number

of edges M. Other invariants of molecular graphs are topological indices, which are

used as structural descriptors in quantitative structure–property relationships (QSPR),

QSAR, and virtual screening of chemical libraries (cf. Chapters 4 and 5).

Graphs that have no more than one edge joining any pair of vertices are also called

simple graphs.Amultigraph is a graph in which two vertices may be connected by

more than one edge. A multiedge of multiplicity m is a set of m edges that connects

the same pair of distinct vertices. A loop e

∈ E is an edge joining a vertex v

with

itself. A loopgraph is a graph containing one or more vertices with loops.

Simple graphs cannot capture the complexity of real life systems, such as electrical

circuits, transportation networks, production planning, kinetic networks, metabolic

networks, or chemical structures. In such cases it is convenient to attach weights to

vertices or loops, weights that may represent current intensity, voltage, distance, time,

material flux, reaction rate, bond type, or atom type. A graph G(V, E, w) is a weighted

graph if there exists a function w : E →R (where R is the set of real numbers), which

assigns a real number, called weight, to each edge of E. Graph 1.6 has all edge weights

equal to 2, whereas in Graph 1.7 the edge weights alternate between 1 and 2. In the

loopgraph 1.8 all edges have the weight 1 and the loop has the weight 2. Alkanes

and cycloalkanes are represented as molecular graphs with all edges having a weight

equal to 1, whereas chemical compounds containing heteroatoms or multiple bonds

are represented as vertex- or edge-weighted molecular graphs. Section 1.4 reviews in

detail the representation of chemical compounds with weighted graphs.

222

1.6

1.7

1.8

Representing Two-Dimensional Chemical Structures with Molecular Graphs 5

In many graph models, such as those of kinetic, metabolic, or electrical networks,

it is useful to give each edge a direction or orientation. The graphs used to model

such oriented systems are termed directed graphs or digraphs. A graph D(V, A) is an

ordered pair consisting of two sets V(D) and A(D), where the vertex set V is finite

and nonempty and the arc set A is a set of ordered pairs of distinct elements from V.

Graphs 1.9 through 1.12 are several examples of digraphs.A comprehensive overview

of reaction graphs is presented by Balaban [32], and graph models for networks of

chemical reactions are reviewed by Temkin et al. [29].

1.9 1.10 1.11 1.12

1.2.2 ADJACENCY, WALKS, PATHS, AND DISTANCES

Two vertices v

and v

of a graph G are adjacent (or neighbors) if there is an edge e

joining them. The two adjacent vertices v

and v

are said to be incident to the edge

. The neighborhood of a vertex v

is represented by the set of all vertices adjacent

to v

. Two distinct edges of G are adjacent if they have a vertex in common.

The degree of a vertex v

, denoted by deg

, is equal to the number of vertices

adjacent to vertex v

. The set of degree values for all vertices in a graph gives

the vector Deg(G) whose ith element represents the degree of the vertex v

.Ina

weighted graph G(V, E, w), the valency of a vertex v

, val(w, G)

, is defined as

the sum of the weights of all edges e

incident with vertex v

[33,34]. The set of

valencies for all vertices in a graph forms the vector Val(w, G) whose ith element

represents the valency of the vertex v

. From the definition of degree and valency

it is obvious that in simple, nonweighted graphs, the degree of a vertex v

,deg

is identical to the valency of that vertex, val

. Consider the simple labeled graph

1.13. A simple count of the neighbors for each vertex in 1.13 gives the degree vec-

tor Deg(1.13) ={2, 2, 3, 2, 2, 3, 2}. The second example considers a weighted graph

with the labeling given in Graph 1.14 and with the edge weights indicated in 1.15.

The degree vector of 1.14 is Deg(1.14) ={2, 3, 2, 3, 2, 2, 3, 2, 3, 2}, and the valency

vector is Val(1.14) ={1.5, 4, 3, 4, 1.5, 1.5, 4, 3, 4, 1.5}. Both degree and valency are

graph invariants, because their numerical values are independent of the graph

labeling.

1.13

1.14

0.5

1.15

6 Handbook of Chemoinformatics Algorithms

A walk W in a graph G is a sequence of vertices and edges W(G) ={v

, e

, v

, e

, v

, e

, v

, ..., v

, e

, v

, ..., v

, e

, v

} beginning and ending with ver-

tices, in which two consecutive vertices v

and v

are adjacent, and each edge e

incident with the two vertices v

and v

preceding and following it, respectively. A

walk may also be defined as a sequence of vertices W(G) ={v

, v

, ..., v

}in which

two consecutive vertices v

and v

i+1

are adjacent. Similarly, a walk may be defined

as a sequence of edges W(G) ={e

, e

, ..., e

} in which two consecutive edges

and e

are adjacent. In a walk any edge of the graph may appear more than once.

The length of a walk is equal to the total number of edges that define the walk. A walk

in which the initial and the terminal vertices coincide is called a closed walk. A walk

in which the initial and the terminal vertices are different is called an open walk. A

trail is a walk in which no edge is repeated. A certain vertex may appear more than

once in a trail, if the trail intersects itself.A path P is a walk in which all vertices (and

thus necessarily all edges) are distinct. The length of a path in a graph is equal to the

number of edges along the path.

A graph cycle or circuit is a closed walk in which all vertices are distinct,

with the exception of the initial and terminal vertices that coincide. In Graph 1.16

there are three cycles: C

(1.16) ={v

, v

}, with length three; C

(1.16) =

, v

}, with length five; and C

(1.16) ={v

, v

}, with length

four. In Graph 1.17 there are three cycles of length five: C

(1.17) ={v

, v

}, C

(1.17) ={v

, v

}, and C

(1.17) ={v

, v

1.16

1.17

1.18

The cyclomatic number μ represents the number of cycles in the graph, μ = M −

N + 1. For Graph 1.16 we have μ(1.16) = 6 −5 +1 = 2, for Graph 1.17 we have

μ(1.17) = 13 −11 +1 = 3, and for Graph 1.18 we have μ(1.18) = 6 −6 + 1 = 1.

In a simple (nonweighted) connected graph, the graph distance d

between a pair

of vertices v

and v

is equal to the length of the shortest path connecting the two

vertices (i.e., the number of edges of the shortest path). The distance between two

adjacent vertices is 1. The graph distance satisfies the properties of a metric:

a. The distance from a vertex v

to itself is zero:

= 0, for all v

∈ V(G). (1.1)

b. The distance between two distinct vertices v

and v

is larger than 0:

> 0, for all v

, v

∈ V(G). (1.2)

Representing Two-Dimensional Chemical Structures with Molecular Graphs 7

c. The distance between two distinct vertices v

and v

is equal to the distance

on the inverse path, from v

and v

= d

, for all v

, v

∈ V(G). (1.3)

d. The graph distance satisfies the triangle inequality:

≥ d

, for all v

, v

∈ V(G). (1.4)

The eccentricity ecc(v

) of a vertex v

is the maximum distance from the vertex v

to any other vertex v

in graph G, that is, max [35] for all v

∈ V(G). The diameter

diam(G) of a graph G is the maximum eccentricity. If the graph G has cycles, then

the girth of G is the length of a shortest cycle, and the circumference is the length of

a longest cycle.

A graph G may be transformed into a series of subgraphs of G by deleting one or

more of its vertices,or by deleting one or more of its edges. If V(G



) is a subset of V(G),

V(G



) ⊆ V(G), and E(G



) is a subset of E(G), E(G



) ⊆ E(G), then the subgraph



= (V(G



), E(G



)) is a subgraph of the graph G = (V(G), E(G)). A subgraph

G −v

is obtained by deleting from G the vertex v

and all its incident edges. A

subgraph G − e

is obtained by deleting from G the edge e

. Graph 1.19 has four

subgraphs of the type G −v

, 1.20 through 1.23, which are obtained by deleting, in

turn, one vertex and all its incident edges from Graph 1.19.

2 1

1.19

1.20

1.21

1.22

1.23

1.2.3 SPECIAL GRAPHS

A tree,oranacyclic graph, is a connected graph that has no cycles (the cyclomatic

number μ = 0).Alternative definitions for a treeare the following:a tree is a connected

graph with N vertices and N−1 edges; a tree is a graph with no cycles, N vertices, and

N−1 edges. A graph that contains as components only trees is a forest.Ak-tree is a

tree with the maximum degree k. Alkanes are usually represented as 4-trees. A rooted

tree is a tree in which one vertex (the root vertex) is distinct from the other ones.

A graph with the property that every vertex has the same degree is called a reg-

ular graph. A graph G is called a k-regular graph or a regular graph of degree k

if every vertex from G has the degree k. A ring R

with N vertices is a 2-regular

graph with N vertices, that is, a graph with all vertices of degree 2. The cycloalkanes

cyclopropane, cyclobutane, cyclopentane, cyclohexane, cycloheptane, and cyclooc-

tane are examples of 2-regular graphs. The 3-regular graphs, or cubic graphs, 1.24

through 1.27, represent as molecular graphs the polycyclic hydrocarbons triprismane,

tetraprismane (cubane), pentaprismane, and hexaprismane, respectively. Fullerenes

are also represented as cubic graphs.