Représentation des structures chimiques bi-dimensionnelles avec les graphes moléculaires

Introduction

Les graphiques sont utilisés comme une abstraction et une approximation efficaces pour divers systèmes chimiques, tels que des composés chimiques, des ensembles de molécules, des fragments moléculaires, des polymères, des réactions chimiques, des mécanismes de réaction et des voies d’isomérisation.
De toute évidence, la complexité des systèmes chimiques est considérablement réduite lorsqu’ils sont modélisés sous forme de graphiques. Par exemple, lorsqu’un composé chimique est représenté sous la forme d’un graphe moléculaire, les informations de géométrie sont négligées et seules les informations de connectivité de l’atome sont conservées.

Pour être utile, la représentation graphique d’un système chimique doit conserver toutes les caractéristiques importantes du système étudié et doit offrir des conclusions qualitatives ou quantitatives en accord avec celles fournies par des méthodes plus sophistiquées. Tous les systèmes chimiques qui ont été modélisés avec succès en tant que graphes ont une caractéristique commune, à savoir qu’ils sont composés d’éléments qui interagissent entre eux, et ces interactions contribuent à expliquer une propriété d’intérêt de ce système chimique.

Les éléments d’un système sont représentés sous la forme de sommets de graphe, et les interactions entre ces éléments sont représentées comme des arêtes de graphe.
Dans un graphe chimique, les sommets peuvent représenter divers éléments d’un système chimique, tels que des orbitales atomiques ou moléculaires, des électrons, des atomes, des groupes d’atomes, des molécules et des isomères. L’interaction entre ces éléments, qui sont représentés comme des arêtes de graphique, peut être des liaisons chimiques, des interactions non liées, des étapes de réaction, des connexions formelles entre des groupes d’atomes ou des transformations formelles de groupes fonctionnels.
Le chapitre se poursuit avec une vue d’ensemble des éléments de la théorie des graphes qui sont importants en chemoinformatique et dans la représentation des structures chimiques bidimensionnelles (2D).
La section 1.3 présente les principaux types de graphes chimiques et moléculaires, et la section 1.4 examine la représentation des molécules contenant des hétéroatomes et des liaisons multiples avec des graphes pondérés et des matrices moléculaires.

Eléments de la théorie des graphes

Cette section présente les définitions de base, les notations et les exemples de théorie des graphes pertinents pour la chémoinformatique. Les applications de la théorie des graphes en physique, électronique, chimie, biologie, chimie médicinale, économie ou sciences de l’information ont vu le jour principalement grâce au livre de Harary « Graph Theory »[1].

Plusieurs autres livres représentent des lectures essentielles pour une vue d’ensemble approfondie de la base théorique de la théorie des graphes:

Graphs and Hypergraphs par Berge [2]
Graphs and Digraphs de Behzad, Chartrand et Lesniak-Foster [3]
Distance in Graphs de Buckley et Harary [4]
Graph Theory Applications par Foulds [5]
Introduction to Graph Theory par West [6]
Graph Theory de Diestel [7]
Topics in Algebraic Graph Theory par Beineke et Wilson [8].

La théorie spectrale des graphes étudie les propriétés des spectres (valeurs propres) des matrices de graphes. Elle a des applications dans les réseaux complexes, l’inclusion spectrale de données multivariées, la représentation de graphes, le calcul d’indices topologiques, la chimie quantique topologique et l’aromaticité.
Le principal manuel sur la théorie spectrale des graphes est « Spectra of Graphs. Theory and Applications » par Cvetkovic, Doob et Sachs [9]. Un des livres des plus influents sur les applications de spectres de graphes dans la chimie quantique des systèmes conjugués et de l’aromaticité. est « Topological Approach to the Chemistry of Conjugated Molecules » par Graovac, Gutman et Trinajstic [10].
Les sujets avancés sur l’aromaticité topologique sont traités dans :

Kekulé Structures in Benzenoid Hydrocarbons

Références

1. Harary, F., Graph Theory. Adison-Wesley: Reading, MA, 1994.
2. Berge, C., Graphs and Hypergraphs. Elsevier: New York, 1973.
3. Behzad, M., Chartrand, G., and Lesniak-Foster, L., Graphs and Digraphs. Wadsworth International Group: Belmont, CA, 1979.
4. Buckley, F. and Harary, F., Distance in Graphs. Adison-Wesley: Reading, MA, 1990.
5. Foulds, L. R., Graph Theory Applications. Springer: New York, 1992.
6. West, D. B., Introduction to Graph Theory, 2nd edition. Prentice-Hall: Englewood Cliffs,
NJ, 2000.
7. Diestel, R., Graph Theory, 3rd edition. Springer: Heidelberg, Germany, 2005.
8. Beineke, L. W. and Wilson, R. J., Topics in Algebraic Graph Theory. Cambridge University Press: Cambridge, UK, 2005.
9. Cvetkovi´c, D. M., Doob, M., and Sachs, H., Spectra of Graphs. Theory and Applications, 3rd edition. Johann Ambrosius Barth Verlag: Heidelberg, Germany, 1995.
10. Graovac, A., Gutman, I., and Trinajsti´c, N., Topological Approach to the Chemistry of
Conjugated Molecules. Springer: Berlin, 1977.
11. Cyvin, S. J. and Gutman, I., Kekulé Structures in Benzenoid Hydrocarbons, Vol. 46. Springer: Berlin, 1988.
12. Gutman, I. and Cyvin, S. J., Introduction to the Theory of Benzenoid Hydrocarbons. Springer: Berlin, 1989.
13. Gutman, I. and Cyvin, S. J., Advances in the Theory of Benzenoid Hydrocarbons, Vol. 153. Springer: Berlin, 1990.
14. Cyvin, S. J., Brunvoll, J., and Cyvin, B. N., Theory of Coronoid Hydrocarbons, Vol. 54. Springer: Berlin, 1991.
15. Dias, J. R., Molecular Orbital Calculations Using Chemical Graph Theory. Springer: Berlin, 1993.
16. Harary, F. and Palmer, E. M., Graphical Enumeration. Academic Press: NewYork, 1973.
17. Pólya, G. and Read, R. C.,Combinatorial Enumeration of Groups, Graphs, and Chemical
Compounds. Springer: New York, 1987.
18. Fujita, S., Symmetry and Combinatorial Enumeration in Chemistry. Springer: Berlin, 1991.
19. Biggs, N. L., Lloyd, E. K., andWilson, R. J., Graph Theory 1736–1936. Clarendon Press: Oxford, 1976.
20. Balaban, A. T., Chemical Applications of Graph Theory. Academic Press: London, 1976.
21. Trinajsti´c, N., Chemical Graph Theory. CRC Press: Boca Raton, FL, 1992.
22. Gutman, I. and Polansky, O. E., Mathematical Concepts in Organic Chemistry. Springer:
Berlin, 1986.
23. Gasteiger, J., Handbook of Chemoinformatics. Wiley-VCH: Weinheim, 2003.
24. Kier, L. B. and Hall, L. H., Molecular Connectivity in Chemistry and Drug Research.
Academic Press: New York, 1976.
25. Kier, L. B. and Hall, L. H., Molecular Connectivity in Structure–Activity Analysis.
Research Studies Press: Letchworth, UK, 1986.
26. Kier, L. B. and Hall, L. H., Molecular Structure Description. The Electrotopological
State. Academic Press: San Diego, CA, 1999.
27. Bonchev, D., Information Theoretic Indices for Characterization of Chemical Structure.
Research Studies Press: Chichester, UK, 1983.
28. Devillers, J. and Balaban, A. T., Topological Indices and Related Descriptors in QSAR
and QSPR. Gordon and Breach Science Publishers: Amsterdam, the Netherlands, 1999.
29. Temkin, O. N., Zeigarnik,A.V., and Bonchev, D.,Chemical Reaction Networks. A GraphTheoretical
Approach. CRC Press: Boca Raton, FL, 1996.
30. Koˇca, J., Kratochvíl, M., Kvasniˇcka, V., Matyska, L., and Pospíchal, J., Synthon Model
of Organic Chemistry and Synthesis Design, Vol. 51. Springer: Berlin, Germany, 1989.
31. Golender, V. E. and Rozenblit, A. B., Logical and Combinatorial Algorithms for Drug
Design, p. 289. Research Studies Press: Letchworth, UK, 1983.
32. Balaban, A. T., Reaction graphs. In: D. Bonchev and O. Mekenyan (Eds), Graph Theoretical
Approaches to Chemical Reactivity, pp. 137–180. Kluwer Academic Publishers:
Amsterdam, the Netherlands, 1994.
33. Ivanciuc, O., Design of topological indices. Part 11. Distance-valency matrices and
derived molecular graph descriptors. Revue Roumaine de Chimie 1999, 44(5), 519–528.
34. Ivanciuc, O., Design of topological indices. Part 14. Distance-valency matrices and structural
descriptors for vertex- and edge-weighted molecular graphs. Revue Roumaine de
Chimie 2000, 45(6), 587–596.
35. Dijkstra, E., A note on two problems in connection with graphs. Numerische Mathematik
1959, 1, 269–271.
36. Ivanciuc, O., Ivanciuc, T., and Balaban, A. T., Vertex- and edge-weighted molecular
graphs and derived structural descriptors. In: J. Devillers and A. T. Balaban (Eds), Topological
Indices and Related Descriptors in QSAR and QSPR, pp. 169–220. Gordon and
Breach Science Publishers: Amsterdam, the Netherlands, 1999.
37. Ivanciuc, O. and Ivanciuc, T., Matrices and structural descriptors computed from molecular
graph distances. In: J. Devillers and A.T. Balaban (Eds), Topological Indices and
Related Descriptors in QSAR and QSPR, pp. 221–277. Gordon and Breach Science
Publishers: Amsterdam, the Netherlands, 1999.
38. Higham, D. J., Kalna, G., and Kibble, M., Spectral clustering and its use in bioinformatics.
Journal of Computational and Applied Mathematics 2007, 204(1), 25–37.
39. Randi´c, M., Random walks and their diagnostic value for characterization of atomic
environment. Journal of Computational Chemistry 1980, 1(4), 386–399.
40. Burdett, J. K., Lee, S., and McLarnan, T. J., The coloring problem. Journal of the
American Chemical Society 1985, 107(11), 3083–3089.
41. Burdett, J. K., Topological control of the structures of molecules and solids. Accounts of
Chemical Research 1988, 21(5), 189–194.
42. Jiang,Y. and Zhang, H., Aromaticities and reactivities based on energy partitioning. Pure
and Applied Chemistry 1990, 62(3), 451–456.
43. Wu, Y., Zhao, H. G., Liu, X., Li, J., Yang, K., and He, H. B., Evaluation of molecular
moments by three methods. International Journal of Quantum Chemistry 2000, 78(4),
237–244.
44. Markovi´c, S., Markovi´c, Z., and McCrindle, R. I., Spectral moments of phenylenes.
Journal of Chemical Information and Computer Sciences 2001, 41(1), 112–119.
45. Schmalz, T. G., Živkovi´c, T., and Klein, D. J., Cluster expansion of the Hückel
molecular energy of acyclics: Applications to pi resonance theory. In: R. C. Lacher
(Ed.), MATH/CHEM/COMP 1987. Proceedings of an International Course and Conference
on the Interfaces Between Mathematics, Chemistry and Computer Science,
Dubrovnik, Yugoslavia, 22–26 June 1987, Vol. 54, pp. 173–190. Elsevier: Amsterdam,
the Netherlands, 1988.
46. Mohar, B., Laplacian matrices of graphs. In: A. Graovac (Ed.), MATH/CHEM/COMP
1988. Proceedings of an International Course and Conference on the Interfaces Between
Mathematics, Chemistry and Computer Sciences, Dubrovnik, Yugoslavia, 20–25 June
1988, Vol. 63, pp. 1–8. Elsevier: Amsterdam, the Netherlands, 1989.
47. Ivanciuc, O., Chemical graph polynomials. Part 3. The Laplacian polynomial of
molecular graphs. Revue Roumaine de Chimie 1993, 38(12), 1499–1508.
48. Trinajsti´c, N., Babi´c, D., Nikoli´c, S., Plavši´c, D.,Ami´c, D., and Mihali´c, Z., The Laplacian
matrix in chemistry. Journal of Chemical Information and Computer Sciences 1994,
34(2), 368–376.
49. Ivanciuc, O., Design of topological indices. Part 26. Structural descriptors computed from
the Laplacian matrix of weighted molecular graphs: Modeling the aqueous solubility of
aliphatic alcohols. Revue Roumaine de Chimie 2001, 46(12), 1331–1347.
50. Klein, D. J. and Randi´c, M., Resistance distance. Journal of Mathematical Chemistry
1993, 12(1–4), 81–95.
51. Ivanciuc, T., Ivanciuc, O., and Klein, D. J., Posetic quantitative superstructure/activity
relationships (QSSARs) for chlorobenzenes. Journal of Chemical Information and
Modeling 2005, 45(4), 870–879.
52. Ivanciuc, T., Ivanciuc, O., and Klein, D. J., Modeling the bioconcentration factors and
bioaccumulation factors of polychlorinated biphenyls with posetic quantitative superstructure/activity
relationships (QSSAR). Molecular Diversity 2006, 10(2), 133–145.
53. Ivanciuc, T., Ivanciuc, O., and Klein, D. J., Prediction of environmental properties for
chlorophenols with posetic quantitative super-structure/property relationships (QSSPR).
International Journal of Molecular Sciences 2006, 7(9), 358–374.
54. Klein, D. J., Ivanciuc, T., Ryzhov, A., and Ivanciuc, O., Combinatorics of reactionnetwork
posets. Combinatorial Chemistry & High Throughput Screening 2008, 11(9),
723–733.
55. Mihali´c, Z., Veljan, D., Ami´c, D., Nikoli´c, S., Plavši´c, D., and Trinajsti´c, N., The distance
matrix in chemistry. Journal of Mathematical Chemistry 1992, 11(1–3), 223–258.
56. Floyd, R. W., Algorithm 97: Shortest path. Communications of the ACM 1962, 5(6), 345.
57. Warshall, S., A theorem on boolean matrices. Journal of the ACM 1962, 9, 11–12.
58. Wiener, H., Structural determination of paraffin boiling points. Journal of the American
Chemical Society 1947, 69, 17–20.
59. Balaban, A. T., Highly discriminating distance-based topological index. Chemical
Physics Letters 1982, 89(5), 399–404.
60. Balaban, A. T. and Ivanciuc, O., FORTRAN 77 computer program for calculating
the topological index J for molecules containing heteroatoms. In: A. Graovac
(Ed.), MATH/CHEM/COMP 1988. Proceedings of an International Course and Conference
on the Interfaces Between Mathematics, Chemistry and Computer Sciences,
Dubrovnik, Yugoslavia, 20–25 June 1988, Vol. 63, pp. 193–211. Elsevier: Amsterdam,
the Netherlands, 1989.
61. Hall, L. H., Mohney, B., and Kier, L. B., The electrotopological state: Structure information
at the atomic level for molecular graphs. Journal of Chemical Information and
Computer Sciences 1991, 31(1), 76–82.
62. Balaban, A. T. and Balaban, T.-S., New vertex invariants and topological indices of
chemical graphs based on information on distances. Journal of Mathematical Chemistry
1991, 8(4), 383–397.
63. Balaban,A. T., Beteringhe,A., Constantinescu, T., Filip, P.A., and Ivanciuc, O., Four new
topological indices based on the molecular path code. Journal of Chemical Information
and Modeling 2007, 47(3), 716–731.
64. Ivanciuc, O., Graph theory in chemistry. In: J. Gasteiger (Ed.), Handbook of Chemoinformatics,
Vol. 1, pp. 103–138. Wiley-VCH: Weinheim, Germany, 2003.
65. Ivanciuc, O., Balaban, T.-S., and Balaban, A. T., Design of topological indices. Part
4. Reciprocal distance matrix, related local vertex invariants and topological indices.
Journal of Mathematical Chemistry 1993, 12(1–4), 309–318.
66. Randi´c, M., Linear combinations of path numbers as molecular descriptors. New Journal
of Chemistry 1997, 21(9), 945–951.
67. Balaban,A. T., Mills, D., Ivanciuc, O., and Basak, S. C., ReverseWiener indices.Croatica
Chemica Acta 2000, 73(4), 923–941.
68. Diudea, M.V.,Wiener and hyper-Wiener numbers in a single matrix. Journal of Chemical
Information and Computer Sciences 1996, 36(4), 833–836.
69. Diudea,M.V., Ivanciuc, O., Nikoli´c, S., and Trinajsti´c, N.,Matrices of reciprocal distance,
polynomials and derived numbers. MATCH Communications in Mathematical and in
Computer Chemistry 1997, 35, 41–64.
70. Diudea, M. V., Indices of reciprocal properties or Harary indices. Journal of Chemical
Information and Computer Sciences 1997, 37(2), 292–299.
71. Ivanciuc, O., Design of topological indices. Part 27. Szeged matrix for vertex- and edgeweighted
molecular graphs as a source of structural descriptors for QSAR models. Revue
Roumaine de Chimie 2002, 47(5), 479–492.
72. Cayley, A., On the mathematical theory of isomers. Philosophical Magazine 1874, 67,
444–446.
73. Gutman, I., Vidovi´c, D., and Popovi´c, L., Graph representation of organic molecules.
Cayley’s plerograms vs. his kenograms. Journal of the Chemical Society, Faraday
Transactions 1998, 94(7), 857–860.
74. Gutman, I. and Vidovi´c, D., Relations between Wiener-type topological indices of
plerograms and kenograms. Journal of the Serbian Chemical Society 1998, 63(9),
695–702.
75. Toropov, A. A. and Toropova, A. P., QSPR modeling of the formation constants for
complexes using atomic orbital graphs.Russian Journal of Coordination Chemistry 2000,
26(6), 398–405.
76. Toropov, A. A. and Toropova, A. P., Prediction of heteroaromatic amine mutagenicity by
means of correlation weighting of atomic orbital graphs of local invariants. Journal of
Molecular Structure (Theochem) 2001, 538, 287–293.
77. Toropov, A. A. and Toropova, A. P., QSAR modeling of mutagenicity based on graphs of
atomic orbitals. Internet Electronic Journal of Molecular Design 2002, 1(3), 108–114.
78. Pogliani, L., From molecular connectivity indices to semiempirical connectivity terms:
Recent trends in graph theoretical descriptors. Chemical Reviews 2000, 100(10), 3827–
3858.
79. Pogliani, L., Algorithmically compressed data and the topological conjecture for the
inner-core electrons. Journal of Chemical Information and Computer Sciences 2002,
42(5), 1028–1042.
80. Pogliani, L., Complete graph conjecture for inner-core electrons: Homogeneous index
case. Journal of Computational Chemistry 2003, 24(9), 1097–1109.
81. Pogliani, L., Encoding the core electrons with graph concepts. Journal of Chemical
Information and Computer Sciences 2004, 44(1), 42–49.
82. Pogliani, L., The evolution of the valence delta in molecular connectivity theory. Internet
Electronic Journal of Molecular Design 2006, 5(7), 364–375.
83. Barnard, J. M., A comparison of different approaches to Markush structure handling.
Journal of Chemical Information and Computer Sciences 1991, 31(1), 64–68.
84. Fisanick, W., The chemical abstracts service generic chemical (Markush) structure storage
and retrieval capability. 1. Basic concepts. Journal of Chemical Information and
Computer Sciences 1990, 30(2), 145–154.
85. Ebe, T., Sanderson, K. A., and Wilson, P. S., The chemical abstracts service generic
chemical (Markush) structure storage and retrieval capability. 2. The MARPAT file.
Journal of Chemical Information and Computer Sciences 1991, 31(1), 31–36.
86. Benichou, P., Klimczak, C., and Borne, P., Handling genericity in chemical structures
using the Markush Darc software. Journal of Chemical Information and Computer
Sciences 1997, 37(1), 43–53.
87. Lynch, M. F., Barnard, J. M., and Welford, S. M., Computer storage and retrieval of
generic chemical structures in patents. 1. Introduction and general strategy. Journal of
Chemical Information and Computer Sciences 1981, 21(3), 148–150.
88. Holliday, J. D., Downs, G. M., Gillet, V. J., Lynch, M. F., and Dethlefsen, W., Evaluation
of the screening stages of the Sheffield research project on computer storage and retrieval
of generic chemical structures in patents. Journal of Chemical Information and Computer
Sciences 1994, 34(1), 39–46.
89. Barnard, J. M., Lynch, M. F., and Welford, S. M., Computer storage and retrieval of
generic chemical structures in patents. 2. GENSAL, a formal language for the description
of generic chemical structures. Journal of Chemical Information and Computer Sciences
1981, 21(3), 151–161.
90. Welford, S. M., Lynch, M. F., and Barnard, J. M., Computer storage and retrieval of
generic chemical structures in patents. 3. Chemical grammars and their role in the manipulation
of chemical structures. Journal of Chemical Information and Computer Sciences
1981, 21(3), 161–168.
91. Barnard, J. M., Lynch, M. F., and Welford, S. M., Computer storage and retrieval of
generic structures in chemical patents. 4. An extended connection table representation
for generic structures. Journal of Chemical Information and Computer Sciences 1982,
22(3), 160–164.
92. Welford, S. M., Lynch, M. F., and Barnard, J. M., Computer storage and retrieval of
generic chemical structures in patents. 5. Algorithmic generation of fragment descriptors
for generic structure screening. Journal of Chemical Information and Computer Sciences
1984, 24(2), 57–66.
93. Holliday, J. D., Downs, G. M., Gillet, V. J., and Lynch, M. F., Computer storage and
retrieval of generic chemical structures in patents. 14. Fragment generation from generic
structures. Journal of Chemical Information and Computer Sciences 1992, 32(5), 453–
462.
94. Holliday, J. D., Downs, G. M., Gillet, V. J., and Lynch, M. F., Computer storage and
retrieval of generic chemical structures in patents. 15. Generation of topological fragment
descriptors from nontopological representations of generic structure components.
Journal of Chemical Information and Computer Sciences 1993, 33(3), 369–377.
95. Barnard, J. M., Lynch, M. F., and Welford, S. M., Computer storage and retrieval of
generic chemical structures in patents. 6. An interpreter program for the generic structure
description language GENSAL. Journal of Chemical Information and Computer
Sciences 1984, 24(2), 66–71.
96. Dethlefsen, W., Lynch, M. F., Gillet, V. J., Downs, G. M., and Holliday, J. D., Computer
storage and retrieval of generic chemical structures in patents. 11. Theoretical aspects
of the use of structure languages in a retrieval system. Journal of Chemical Information
and Computer Sciences 1991, 31(2), 233–253.
97. Gillet, V. J., Welford, S. M., Lynch, M. F., Willett, P., Barnard, J. M., Downs, G. M.,
Manson, G., and Thompson, J., Computer storage and retrieval of generic chemical
structures in patents. 7. Parallel simulation of a relaxation algorithm for chemical substructure
search. Journal of Chemical Information and Computer Sciences 1986, 26(3),
118–126.
98. Gillet, V. J., Downs, G. M., Ling, A., Lynch, M. F., Venkataram, P., Wood, J. V., and
Dethlefsen, W., Computer storage and retrieval of generic chemical structures in patents.
8. Reduced chemical graphs and their applications in generic chemical structure retrieval.
Journal of Chemical Information and Computer Sciences 1987, 27(3), 126–137.
99. Gillet, V. J., Downs, G. M., Holliday, J. D., Lynch, M. F., and Dethlefsen, W., Computer
storage and retrieval of generic chemical structures in patents. 13. Reduced graph generation. Journal of Chemical Information and Computer Sciences 1991, 31(2), 260–270.