Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Ca sa traiesti o viata sanatoasa. principii și metode ale fizicii, procesele biologice, transmiterea impulsurilor nervoase

Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Biofizica


Index » educatie » » biologie » Biofizica
» Topologia Moleculara - Grafuri


Topologia Moleculara - Grafuri



Introducere in Topologia Moleculara

Teoria grafurilor aplicata in studiul structurilor moleculare se constituie ca ramura interdisciplinara numita Topologie Moleculara. Caracterizarea topologica a structurilor chimice permite ordonarea acestora dupa criterii de simetrie si similaritate.  

Din studii comparate, asupra unui set de molecule, topologia moleculara descifreaza factorii structurali implicati in relatia structura-proprietate/activitate biologica. Partitionarea unor proprietati moleculare si recompunerea lor, prin modele aditive, cu ajutorul descriptorilor moleculari si a analizei statistice, ca si modelarea de noi structuri, cu proprietati dorite, reprezinta unul din obiectivele topologiei moleculare. Inainte de detalierea problemelor specifice toplogiei moleculare vor fi prezentate cateva definitii1 de baza ale teoriei grafurilor.

1.1.  Grafuri

Graf:  G = G(V, E), este o pereche a doua multimi V = V(G),  unde V este o multime finita si nevida, iar E = E(G),  reprezinta o relatie binara definita pe multimea V. Graful, obisnuit, este vizualizat reprezentand elementele multimii V prin puncte si unind fiecare pereche de puncte (vi, vj) sau, mai simplu (i, j) cu o linie, ei,j,  daca si numai daca (i,j)IE(G). Daca perechea de varfuri (i, j)  este neordonata, graful G este neorientat; punctele se cheama varfuri iar liniile se numesc muchii. Numarul varfurilor in G se noteaza cu v si este egal cu |V| (cardinalitatea multimii V(G)) iar numarul muchiilor cu e, care egaleaza |E| (cardinalitatea multimii E). Graful G(v, e) are ordinul v si dimensiunea e. Daca doua laturi distincte sunt incidente intr-un punct, ele se numesc laturi adiacente. Daca perechea de varfuri (i, j) este ordonata, graful G se cheama orientat; elementele multimii E  se cheama linii directe sau arce.1 Termenul de graf a  fost introdus de Sylvester.2 Exista numeroase tipuri de grafuri, unele dintre ele fiind mentionate mai jos.

Intr-un multigraf  doua puncte pot fi unite prin mai mult de o linie. Figura 1.1 arata cele trei tipuri de grafuri mentionate mai inainte.

Figura 1.1.                   Graf                                   Digraf                     Multigraf

O cale P (path) este un lant (catena) neramnificat(a). Un arbore T (tree), este o structura ramnificata. O stea (star) este un set de varfuri unite cu un varf comun si se noteaza Sv' , cu v' = v-1. Un ciclu C este un lant care pleaca si revine in unul si acelasi varf. (Figura 1.2).

Figura 1.2.                 Cale                               Arbora                         Stea                        Ciclu

Un graf complet, Kv, este un graf cu oricare doua varfuri adiacente. Numarul laturilor intr-un graf complet este  v(v-1)/2. In Figura 1.3, sunt prezentate  grafuri complete de la v=1 pana la 5.

           

Figura 1.3.              K1             K2                K3                   K4                     K5

Un graf bipartit  este graful al carui set de varfuri V poate fi impartit in doua subseturi: V1 È V2 =V; V1 Ç V2 = Æ astfel incat orice latura (i,j) I E(G) uneste  V1 cu V2.1,3 Un graf este bipartit daca si numai daca toate ciclurile sale sunt pare.4 Daca oricare varf  iIV1 este adiacent cu fiecare varf  jIV2, atunci G este un graf bipartit complet si este simbolizat Km,n, cu m = |V1|  si n = |V2|. O stea este un graf bipartit complet K1,n. Este evident ca Km,n  are m ´ n laturi. Figura 1.4 prezinta cateva grafuri bipartite.

   

Figura 1.4.       Graf bipartit               K1.3                                 K2.3                                       K3.3

Un graf marcat, este garful in care heteroatomul sau atomul de carbon cu un electron neamperechiat este matcat.5,6(Figura 1.5)

Figura 1.5. Grafuri marcate

Un graf homeomorf este graful obtinut prin inserarea  unor varfuri de valenta 2 pe muchiile unui graf G. (Figura 1.6)3

Figura 1.6.  Grafuri homeomorfe ale tetraedrului

Un graf planar este graful care poate fi desenat in plan, astfel incat oricare doua laturi se intersecteaza cel mult in punctele  lor terminale.7 Regiunile definite  de un graf planar se numesc fete, f, regiunea nemarginita fiind fata exterioara1(e.g., f4  in Figura 1.7). Pentru orice poliedru sferic cu |V| varfuri, |E| laturi si  |F| fete este valabila formula lui Euler:8 . Un graf este planar daca si numai daca nu are subgrafuri homeomorfe cu K5 sau K3,3 (teorema lui Kuratowski).9

           

Figura 1.7. Un graf planar si fetele sale

           Un graf-linie L(G) al grafului G se construieste punand cate un punct pe liniile lui G si unind doua astfel de puncte daca liniile corespunzatoare in G sunt incidente intr-un punct comun. Figura 1.8 ilustreaza aceasta derivata a grafului.

Figura 1.8. Un graf si graful-linie corespunzator

Un graf complementar al unui graf G = (V, E) este graful   = (V, ), avand acelasi set de varfuri  unite prin legaturi daca si numai daca ele nu exista  in G. Valenta fiecarui varf  in  este egala cu diferenta dintre valenta varfului in graful complet  Kv si varful corespunzator in G7 (Figura 1.9).

Figura 1.9. Un graf si complementul lui

        Un graf G se cheama indexat (labeled), G(Lb),  cand punctele sale sunt indicate diferit de acelea ale grafului abstract corespunzator.10 Exista v! posibilitati de numerotare a unui graf de ordin v, G(Lbi); i = 1,2,v!

       Doua grafuri G=(V, E) si H=(V1, E1) sunt izomorfe, G @ H, daca exista o functie  f : V        V1 care sa respecte conditiile:7,11,12

            (1) f  este bijectiva

            (2) pentru oricare doua varfuri  i, jIV; (i,j)IE « (f(i), f(j))IE1.

  Functia f se numeste izomorfism. In grupul izomorfismelor, exista cel putin o numerotare H(Lb),  care pastreaza adiacenta din G: H(Lb) = G(Lb).  

Figura 1.10.  Doua grafuri izomorfe

Un subgraf al unui graf G= (V, E) este un graf H = (V1, E1), unde V1 Ì V si E1 Ì E reprezinta toate muchiile care au ambele extremitati in V1. Altfel spus, un subgraf H al lui G se obtine din G eliminand anumite varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase. (Figura 1.11).

Figura 1.11.  Un graf si un subgraf al sau

Un arbore de deschidere (spanning tree) este un subgraf conex G1 = (V, E1) continand toate varfurile lui G dar E1 Ì E (Figura 1.12.).

Figura 1.12. Un graf si cativa dintre arborii lui de deschidere

Un graf G este conex daca intre oricare doua varfuri ale sale exista o cale.11 (Figura 1.13).

Figura 1.13. Graf conex

1.2.  Drumuri

Drum (walk) w: este o secventa alternanta de varfuri si muchii, w(1,n) = (v1, e1, v2, e2, , vn-1, em, vn), vi I V(G ), ei I E(G ), m ³  n - 1, parcursa astfel incat oricare doua muchii succesive sunt adiacente: (vi-1, vi) I E(G).3,12 Este permisa revizitarea varfurilor si a muchiilor. Daca V(w(1,n)) = este sirul varfurilor drumului w(1,n) iar E(w(1,n)) = este sirul muchiilor sale, atunci l(w(1,n))=½E(w1,n)½ ³ ½V(w1,n) ½- 1, reprezinta lungimea drumului, care este egala cu numarul muchiilor traversate. Daca nici o alta conditie nu este impusa, drumul se numeste drum aleator. Conditii aditionale specifica un anumit tip de drum:13-16

Drum inchis (Self-returning walk, srw) este drumul care porneste si sfarseste in acelasi varf, vn=v1 ;  altfel drumul este deschis.

Cale (Self-avoiding walk, path p): este drumul care are toate varfurile si muchile distincte:  vi ¹ vj, (vi-1, vi) ¹ (vj-1, vj), pentru oricare 1 £ i < j £ n. Altfel spus, calea viziteaza varfurile si muchiile o singura data si nu se admite nici o ramificare. Lungimea caii este l(p(1,n))=½E(p(1,n))½= ½V(p(1,n))½- 1.

Drum Eulerian (trail):  este drumul ale carui muchii e1,e2, , en sunt distincte, in timp ce varfurile pot fi revizitate.

Ciclu (circuit):  este calea ale carei puncte de plecare si intoarcere coincid.

Cale Hamiltoniana:  este calea deschisa ce viziteaza o data toate varfurile din graf.

Circuit Hamilton: este o cale Hamiltoniana inchisa (Figura 1.14).

   drum inchis

    cale

      trail

     circuit

cale

  Hamiltoniana

circuit

Hamiltonian

Figura 1.14. Diferite tipuri de drumuri

Distanta topologica d(i,j): este lungimea caii celei mai scurte (daca exista) care uneste varfurile i si j: , altfel d(i,j)=¥ . Distanta dintre doua varfuri adiacente este egala cu unitatea. Cea mai scurta cale este numita si geodezica.

Excentricitatea unui varf i, ecc(i), intr-un graf conex este distanta maxima dintre i si oricare varf j al grafului: ecc(i) = max d(i,j).

raza unui graf, r(G), este excentricitatea minima in G: r(G) = min ecc(i) = min max d(i,j). diametrul unui graph, d(G), este excentricitatea maxima in G: d(G) = max ecc(i) = max max d(i,j). Multimea tuturor distantelor (geodezicelor) in G se noteaza cu D(G).

detur, d(i,j), reprezinta calea cea mai lunga (daca exista) ce uneste varfurile i si j: ,  altfel d(i,j)= ¥ . Setul tuturor detururilor in G se noteaza cu D(G).

 Intr-un graf conex, distanta si deturul reprezinta metrici, adica, pentru oricare varfuri i, j, k:

m(i,j) ³ 0; m(i,j)= 0 daca i= j

m(i,j) = m(j,i)

m(i,j) + m(i,k) ³ m(j,k)

Distanta metrica: este distanta, masurata in metri sau submultipli ai acestuia (nm, Angstroms), dintre doua varfuri i si j. Tabelul 1.1 illustreaza aceste notiuni.

Tabelul 1.1. Distante topologice si metrice

Graf

Distanta topologica

Distanta metrica (Ao)

CH3-CH3

1

1.54

CH2=CH2

1

1.34

CHsCH

1

1.21

Valenta sau gradul varfului  i, vai: este numarul muchiilor incidente in varful i.1 Daca toate varfurile au acelasi grad, graful se numeste regulat;  altfel se numeste neregulat (Figura 1.15).

                                   (a)

(b)

 

 

  

 

Figura 1.15. Grafuri ponderate cu valenta varfurilor:  3-regulat (a) si  neregulat (b)

Invariant: este o proprietate a grafului theoretic, care se pastreaza prin izomorfism.14-16 Cu alte cuvinte, valoarea numerica a proprietatii ramane neschimbata indiferent de numerotarea sau reprezentarea pictoriala a grafului.

                       

1.3.  Grafuri Moleculare

Un graf molecular este un model al unui system chimic, utilizat  pentru caracterizarea interactiunii componentelor sale: atomi, legaturi, grupuri de atomi sau molecule. Formula structurala a unei substante chimice poate fi reprezentata ca graf molecular, varfurile lui fiind atomii, iar laturile corespunzand legaturilor covalente. In mod obisnuit, atomii de hydrogen se neglijeaza (Figura 1.16) si de asemenea unghiurile dintre legaturi. Atomii grei altii decat carbonul (heteroatomii) pot fi reprezentati ca in Figura 1.5. Similar, transformarea unei molecule (o reactie chimica) poate fi vizualizata  printr-un graf de reactie, ale carui varfuri sunt specii chimice iar laturile cai de reactie.

(a)

(b)

Figura. 1.16: O structura chimica (a) si graful molecular corespunzator acesteia (b).

Referinte

    1.    Harary , F.  Graph Theory, Addison ‑ Wesley,  Reading, M.A., 1969.

    2.    Sylvester, J. J. On an application of the new atomic theory to the graphical

       representation of the invariants and covariants of binary quantics - with three

       appendices, Am. J. Math. 1874, 1, 64-90.

    3.    Trinajstić, N. Chemical Graph Theory , CRC Press, Inc., Boca Raton, Florida, 1983.

    4.    Kőnig, D. Theorie der endlichen und  unendlichen Graphen. Leipzig, 1936.

       Reprinted Chelsea, New York, 1950.

    5.    Kier, L. B.; Hall, L.H. Molecular Connectivity in Chemistry and Drug Research,

       Acad. Press, 1976.

    6.    Balaban, A. T.; Filip, P. Computer program for topological index J (average distance

      sum connectivity), MATCH, Commun. Math. Comput. Chem., 1984, 16, 163-190.

    7.    Ionescu, T. Grafuri‑Aplicatii, Ed. Ped. Bucharest, 1973.

    8.    Euler, L. Elementa doctrinae solidorum et demonstratio nonnularum insignium proprietatum quibus solida heddris planis inclusa sunt praedita, Novi Comment. Acad. Sci. I. Petropolitanae, 1758, 4, 109-160.

    9.    Kuratowski, K. Sur le problème des courbes gauches en topologie, Fund. Math.

       1930, 15, 271-283.

10.    Klin, M.H.; Zefirov, N.S. Group theoretical approach to the investigation of

      reaction graphs for highly degenerate rearrangements of chemical compounds. II. Fundamental

      concepts. MATCH, Commun. Math. Comput. Chem., 1991, 26, 171-190.

11.    Oprescu, D.; Bejan, L.; Patrascu, V. Informatica, Ed. Niculescu, Bucuresti, 2001

12.    Cayley E.  , Phil. Mag., 67 (1874) 444.

13.    Berge, C. Teoria Grafurilor si Aplicatiile Ei, Ed. Tehnica , Bucuresti , 1969.

14.    Kier, L. B. ; Hall, L. H. Molecular connectivity in chemistry and drug research, Acad. 

              Press, 1976.

15.    Diudea, M. V.; Gutman, I.; Jäntschi, L. Molecular Topology, Nova, New York, 2002.

16.    Diudea, M. V.; Florescu, M. S.; Khadikar, P. V. Molecular Topology and Its Applications, Eficon, Bucharest, 2006.



Biofizica


Biochimie
Biofizica
Botanica

UTILIZAREA DETECTORULUI GEIGER-MÜLLER SAU A DETECTORULUI CU SCINTILATIE PENTRU DETERMINAREA VARIATIEI CU DISTANTA A FLUXULUI DE RADIATII
DETERMINAREA COEFICIENTULUI DE TENSIUNE SUPERFICIALA
Absorbtia luminii
Studiul prin spectroscopie in infrarosu al legaturilor de hidrogen in solutie
Structura apei
Membrana celulara
Potentialul membranar de repaus
Determinarea raportului caldurilor molare
DENSIMETRIE
DETERMINAREA DENSITATII SOLIDELOR SI LICHIDELOR





















 
Copyright © 2014 - Toate drepturile rezervate