Počítačová chemie přednáška) Úvod přednáška)

Počítačová chemie (3. přednáška)

• Úvod (1. přednáška)

• Molekula

• Struktura molekuly (2., 3. a 4. přednáška)
• Geometrie molekuly (5. přednáška)
• Vhled do praxe (6. přednáška)

• Molekulové modelování

• Molekulová mechanika (7. a 8. přednáška)
• Kvantová mechanika (9. a 10. přednáška)
• Molekulová dynamika (11. přednáška)
• Vhled do praxe (12. přednáška)

Struktura molekuly II

• Izomorfismus

• Automorfismus

• Chemická vzdálenost

• Kanonické indexování

Izomorfismus molekulových grafů

• Neformálně I:

• Dva molekulové grafy jsou izomorfní, pokud reprezentují stejnou molekulu.

• Neformálně II:

• Dva molekulové grafy jsou izomorfní, liší-li se pouze indexováním vrcholů.

• Neformálně III:

• Dva molekulové grafy jsou izomorfní, pokud:
• Každý uzel Ni grafu G lze zobrazit na uzel Ni grafu G.
• Sousední uzly uzlu Ni lze zobrazit na sousední uzly uzlu Ni.

Izomorfismus molekulových grafů

• Formálně:

• Grafy G = (V, E, L, , ) a G = (V, E, L, , ) jsou izomorfní, pokud existuje bijektivní zobrazení (permutace) f: V V s následujícími vlastnostmi:

• pokud uzly u, v  V tvoří n hran {u, v} grafu G, pak uzly f(u), f(v)  V tvoří n hran {f(u), f(v)} grafu G
• pokud uzel u  V tvoří n smyček {u, u} grafu G, pak uzel f(u)  V tvoří n smyček {f(u), f(u)} grafu G
• zobrazení f zachovává ohodnocení vrcholů: (u) = (f(u)) pro každé u  V

• Vztah mezi izomorfismem a izomerií:

• Molekuly M1 a M2 jsou izomorfní => M1 a M2 jsou izomerní.

Izomorfismus a matice sousednosti

• Molekulové grafy určené pomocí matice sousednosti:

• G = (V, A, , ) a G = (V, A, , )

• Izomorfismus (=permutace) f: V V´

• K permutaci f lze sestrojit permutační matici P. Poznámka: Permutační matice vznikne z jednotkové matice permutací jejich řádku.

• Potom platí: A = PT A P

Časová složitost

• Velmi neformálně:

• Problém je NP-úplný, pokud pro něho nelze vytvořit algoritmus s nejhůře polynomiální časovou složitostí.

• Příklad:

• algoritmy řešitelné v polynomiálním čase patří například do složitostních tříd: O(n), O(n log n), O(n2), O(n3), atd.
• NP-úplné algoritmy patří například do složitostních tříd: O(2n), O(n!), O(nn), atd.

Isomorfismus - časová složitost & řešení problému

• Problém isomorfismu obecných grafů patří pravděpodobně (není to dokázáno, ale vše tomu nasvědčuje :-) mezi NP-úplné problémy.

• Řešení problému:

• Hrubou silou
• Zefektivnění:
• backtracking
• dělení vrcholů do tříd
• Omezená třída grafů:
• rovinné grafy
• Porovnání číselných charakteristik grafů

Algoritmy pro testování izomorfismu I

• Využití hrubé síly (brute force):

• Popis algoritmu:

• Pro každou permutaci f: V  V se otestuje, zda se jedná o izomorfismus.

• Složitost:

• Množiny V i V mají stejný počet vrcholů, označme si ho n.

• => existuje n! permutací f: V  V

• algoritmus se nachází ve složitostní třídě O(n!)

Izomorfismus - backtracking

• Zefektivnění metody „hrubou silou“

• Nezabývá se všemi zobrazeními. Přidává další vrchol jen k parciálním zobrazením, které splňují podmínky izomorfismu.

• V nejhorším případě má tato metoda také faktoriální složitost, ale pro běžné případy je výpočet podstatně kratší než při využití hrubé síly.

Izomorfismus - backtracking - princip

• a) zobrazí libovolný uzel (uzlu z G neboli vzoru přiřadí uzel z G´ neboli obraz)
• b) otestuje, zda je vzniklé parciální zobrazení izomorfismus (pro nové* uzly platí: vzory i obrazy mají stejné ohodnocení a stejné stupně):
• pokud ano, zobrazí sousedy nových vzoru(ů) na sousedy nových obraz(ů) a opakuje krok b)
• pokud ne, vrátí se o krok zpět a volí jiné zobrazení
• * Nové = zobrazené v posledním kroku. Z rekurzivity algoritmu je zřejmé, že pro původní (dříve přidané) uzly je parciální zobrazení izomorfismus => nemusíme pro ně nic testovat :-).

Izomorfismus - backtracking - příklad

• v1, v2, v3, v4

Izomorfismus - dělení vrcholů do tříd

• Kritéria dělení do tříd:
• ohodnocení atomu
• stupeň vrcholu
• Princip:
• Vrcholy grafu G, náležící do určité třídy, jsou zobrazovány pouze na vrcholy grafu G´, náležející do téže třídy.
• Poznámka: Lze také využít jemnější rozdělení do tříd:
• Kromě ohodnocení a stupně atomu vezmeme při rozdělování do úvahy i ohodnocení a stupně jeho sousedů.
• Rozdělit uzly podle počtu jednoduchých, dvojných a trojných vazeb, které daná vazba tvoří.

Izomorfismus - dělení vrcholů do tříd - příklad

Izomorfismus - rovinné grafy

• Definice:
• Graf nazýváme rovinným, pokud je možno vytvořit jeho rovinné nakreslení.
• Nakreslení grafu je postup, který každému vrcholu grafu přiřadí bod roviny a každé hraně {u, v} přiřadí souvislý prostý oblouk, který spojuje body, přiřazené vrcholům u a v.
• Rovinné nakreslení = Nakreslení, které je provedeno tak, že dva oblouky mají nejvýše 1 společný bod. A to jen v případě, že tento společný bod odpovídá vrcholu, ze kterého obě hrany vycházejí.

Izomorfismus - rovinné grafy - příklad

Izomorfismus - rovinné grafy - příklad

Izomorfismus - rovinné grafy

• Třída rovinných grafů je podtřídou obecných grafů.
• V chemii má velká část molekul rovinné grafy.
• Vyjímky: zeolity, fullereny, některé bioorganické látky (alkaloidy, hormony, ...), složitější polymery a biopolymery.
• Určení, zda je graf rovinný:
• Algoritmus hledající jeho rovinné nakreslení; O(n)
• Izomorfismus rovinných grafů:
• Hopcroftův a Tarjanův algoritmus; O(n log n)
• => Izomorfismus rovinných grafů není NP-úplný problém :-)

Domácí úkol

• Najdi alkaloid, jehož molekulový graf není rovinný.

• Body: Maximálně 2%, 0.5% za každou molekulu (molekuly musí patřit do různých chemických tříd).

Izomorfismus - číselné charakteristiky grafů

• počet vrcholů a hran

• invarianty vyplývající z matice sousednosti:

• charakteristický polynom matice
• kořeny charakteristického polynomu
• vlastní vektory normované matice
• determinant matice
• ...

Izomorfismus - obecný algoritmus

• Porovnání číselných charakteristik grafů:

• nesouhlasí => grafy nejsou izomorfní

• souhlasí:

• Jsou grafy rovinné?
• jeden ano, druhý ne => grafy nejsou izomorfní
• oba ano => algoritmus pro izomorfismus rovinných grafů
• oba ne => algoritmus pro izomorfismus obecných grafů

Izomorfismus - využití v chemii

• Platí:

• Izomorfní grafy reprezentují stejné molekuly.

• Využití: Prohledávání databází molekul.

• Vstup: molekulový graf
• Výstup: informace o vstupní molekule (případně hlášení, že molekula nebyla nalezena)
• Postup: hledání izomorfismu mezi vstupní molekulou a prvky databáze
• Nevýhoda: Velká časová složitost. Hledání molekuly o velikosti N v databázi s M molekulami: O(M.N!)

Automorfismus

• = izomorfismus grafu sama na sebe

• = operace symetrie nad molekulovými grafy, které zachovávají topologii grafu (= nemění matici sousednosti)

• Topologická ekvivalence:

• Dvojice vrcholů vi a vj je topologicky ekvivalentní, pokud existuje takový automorfismus , který zobrazuje jeden vrchol na druhý: (vi) = vj

Automorfismus - příklad

• Molekula formaldehydu má dva automorfismy:

• 1: v1 v12: v1 v1

• v2 v2 v2 v2

• v3 v3 v3 v3

• v4 v4 v4 v4

Automorfismus a matice sousednosti

• Molekulový graf určený pomocí matice sousednosti:

• G = (V, A, , )

• Automorfismus (=permutace) : V V

• K permutaci  lze sestrojit permutační matici P.

• Potom platí:

• A = PT A P

Automorfismus - grupa

• Množina všech automorfismů:

• Aut = {1, 2, …}, kde : V  V

• Operace skládání zobrazení:

• o: (, )  

• Grupa automorfismů:

• Gaut = (Aut, o)

• Grupa automorfismů může být izomorfní s nějakou bodovou grupou prostorové symetrie.

• Pro formaldehyd:

• Gaut = ({1, 2},o)

Cvičení

• Pro molekulu aminomethanu:

Cvičení - řešení

Chemická vzdálenost molekul

• Označení:

• Chemická vzdálenost molekul (molekulových systémů) M a M´ se označuje (M, M´).

• Význam:

• (M, M´) je číslo, charakterizující rozdíl mezi strukturami molekul M a M´.

• KDY (pro jaké molekuly) MÁ CHEMICKÁ VZDÁLENOST SMYSL???

Chemická vzdálenost molekul

• Označení:

• Chemická vzdálenost molekul (molekulových systémů) M a M´ se označuje (M, M´).

• Význam:

• (M, M´) je číslo, charakterizující rozdíl mezi strukturami molekul M a M´.

• Aby měla tato vzdálenost smysl, musí být vstupní molekuly izomerní.
• Čím menší je rozdíl struktur, tím menší je chemická vzdálenost.
• Izomorfní molekuly mají chemickou vzdálenost rovnu 0.

• Využití:

• Plánování syntézy (vyhledávání reaktantů s minimální nenulovou chemickou vzdáleností).

Chemická vzdálenost molekul - definice v chemii

• Popis chemické vzdálenosti:

• (M, M´) je číslo, charakterizující jak komplikovaná je chemická přeměna jedné molekuly v druhou. Konkrétně:

• (M, M´) je počet valenčních elektronů (ať již vazebných nebo nevazebných), jejichž přemístěním v rámci M získáme M´.

• Příklad:

Chemická vzdálenost molekul - matematická definice

• Využijeme matici sousednosti - ta pro každý atom popisuje, kde jsou umístěny jeho elektrony (v kolika vazbách s jakými atomy a v kolika nevazebných elektronových párech) .

• První matematickou definici chemické vzdálenosti formulovali Dugundji a Ugi (1973). Definovali chemickou vzdálenost jako Hammingovu normu rozdílu matic sousednosti.

• Definice Hammingovy normy:

• Nechť M je matice typu N x N, pak její Hammingova norma je:

Chemická vzdálenost molekul - matematická definice

• Definice (M, M´) podle Dugundjiho a Ugiho:

Chemická vzdálenost molekul - matematická definice II

• => Než začneme matice A a A´odečítat, musíme řádky a sloupce matice A´ zpermutovat tak, aby pro i = 1, 2, … N platilo:

• Pokud vrcholy v a v´ označují stejný (i-tý) řádek matic sousednosti A a A´,

• pak (v) = (v´) .

• Analogicky pro sloupce.

Chemická vzdálenost molekul - matematická definice III

• Vhodnou permutací řádků a sloupců matice A´ je zobrazení podobnosti .

• Definice  (opakování :-):

• Bijektivní zobrazení V  V, které zachovává ohodnocení vrcholů chemickými značkami:
• (u) = ((u)) pro každé u  V

Chemická vzdálenost molekul - matematická definice IV

• Pro zobrazení  vytvoříme permutační matici P.

• Pro matici A´ tedy vytvoříme permutovanou matici: PT A´ P

• Původní definici (M, M´) podle Dugundjiho a Ugiho upravíme následovně:

• (M, M´) = || A - PT A´ P ||

Chemická vzdálenost molekul - matematická definice V

• Upravená matematická definice stále není korektní. Proč?

Chemická vzdálenost molekul - matematická definice V

• Upravená matematická definice stále není korektní. Proč?

• Pro 2 molekuly může existovat více zobrazení podobnosti. Které z nich vybrat?

• Chemická definice (M, M´) říká:

• (M, M´) = nejmenší počet valenčních elektronů, které je nezbytné v rámci M přemístit, abychom získali M´.

• => Musíme vybrat takové zobrazení, aby hodnota || A - PT A´ P || byla minimální.

Chemická vzdálenost molekul - matematická definice VI

• Korektní definice chemické vzdálenosti tedy vypadá následovně:

• (M, M´) = min || A - PT A´ P ||,

• kde minimalizace se provádí přes všechny zobrazení podobnosti  (a jejich permutaèní matice P)

• Chemická vzdálenost pro izomerní molekulové grafy vytváří metriku.

• Platí totiž tři definiční vlastnosti metriky:

• Symetričnost: (M, M´) = (M´, M)
• Trojúhelníková nerovnost: (M, M)  (M, M´ ) + (M´, M)
• Nezápornost: (M, M´)  0

Chemická vzdálenost molekul - algoritmus

• Algoritmus pro výpočet chemické vzdálenosti:

• (M, M´) := 
• FOR  zobrazení V  V DO
• IF Jde o zobrazení podobnosti THAN.
• Sestroj pro zobrazení permutační matici P.
• (M, M´) := min ( (M, M´) , || A - PT A´ P || )

Chemická vzdálenost molekul - složitost

• Výpočet chemické vzdálenosti patří k NP-úplným problémům.

• Musíme totiž zkonstruovat všechna možná zobrazení V  V a pro |V| = N je těchto zobrazení N!.

• Pro větší molekuly je tato složitost neakceptovatelná =>

• využívají se optimalizace & heuristiky.

• Poznámka: Problém izomorfismu je zúžením problému chemické vzdálenosti:

• (M, M´) = 0  M je izomorfní s M´

Chemická vzdálenost molekul - příklad výpočtu

• Formaldehyd: Hydroxykarben:

Literatura o izomorfismu, automorfismu a chemické vzdálenosti

• Kvasnička V., Kratochvíl M., Koča J.: Matematická chemie a počítačové řešení syntéz. Academia (1987)

• Kučera L.: Kombinatorické algoritmy. SNTL (1989)

• Kratochvíl M., Matyska L.: Logická struktura chemie. Masarykova univerzita (1994)

Kanonické indexování vrcholů molekulového grafu

• Molekulový graf: G = (V, E, L, , )

• Indexování vrcholů molekulového grafu G:

• bijekce : V  I

• I je indexová množina: I = {1, 2, …, |V|}

• Každému vrcholu je tedy přiřazeno přirozené číslo (index).

Kanonické indexování vrcholů molekulového grafu

• Kanonické indexování = indexování, které splňuje následující podmínky:

• Pro molekulový graf MG s indexováním I lze vygenerovat algoritmicky (pomocí nějakého algoritmu alg_CI)
• Mějme libovolná indexování I1 a I2. Pro vzniklá kanonická indexování CI1 = alg_CI(MG, I1) a CI2 = alg_CI(MG, I2) musí platit:
• i(CI1) = i (CI2) 
• atom s indexem i(CI1) je topologicky ekvivalentní s atomem s indexem i(CI2)

Indexování - počet způsobů

• Molekulový graf má n vrcholů => existuje n! různých způsobů indexování tohoto grafu.

• Pokud |Aut| > 1 (existuje i jiný automorfismus než identita),

• pak existuje pouze n! / |Aut| různých indexování.

• Příklad - formaldehyd:

• počet atomů: 4
• počet automorfismů: 2
• počet různých indexování: 4! / 2 = 12

Kanonické indexování - matice sousednosti

• Pro dva kanonicky indexované molekulové grafy

• G = (V, A, , ) a G = (V, A, , ) platí:

• A = A´ <=>

• grafy reprezentují stejnou molekulu <=>

• grafy jsou izomorfní

Kanonické indexování - využití

• Využití: Prohledávání databází molekul:

• Databáze: obsahuje kanonicky indexované molekuly

• Vstup: kanonicky indexovaná molekula

• Postup: porovnává matice sousednosti vstupní molekuly a molekul z databáze

• (Porovnávání matic velikosti N má složitost O(N2).)

• Výhoda: Podstatně menší časová složitost, než kdybychom pro každou dvojici (vstupní molekula, molekula z databáze) hledali izomorfismus

• Hledání molekuly o velikosti N v databázi s M molekulami:

• Pomocí izomorfismu: O(M.N!)

• Pomocí kanonického indexování: O(M.N2)

Kanonické indexování - algoritmy

• Řešení „hrubou silou“:

• lze vytvořit velké množství takovýchto algoritmů
• Například: Pro každé indexování určit číselnou hodnotu, kterou má lineární zápis matice sousednosti. Poté zvolit indexování s nejvyšší číselnou hodnotu.
• Lineární zápis matice: 1 2  1 234
• 3 4

Kanonické indexování - Morganův algoritmus

• První algoritmus pro kanonické indexování (1965)

• Většina ostatních pracuje na podobném principu

• Poznámka:

• Morganův algoritmus je založen pouze na topologii molekuly, ignoruje násobné vazby, smyčky a ohodnocení vrcholů chemickými značkami.
• Toto omezení je pouze zdánlivé: Z topologie výše uvedená data určit. Například:
• stupeň vrcholu (atomu) + vaznost atomu => počet násobných hran

Morganův algoritmus

• Ohodnoť každý uzel jeho stupněm

• Urči počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Ohodnoť vrcholy součtem ohodnocení sousedních vrcholů

• Urči počet odlišných hodnot

• Opakuj výše uvedené dva body dokud se bude měnit počet odlišných hodnot

Morganův algoritmus

• Většina uzlů má teď odlišné ohodnocení

• Označ jako 1 uzel s nejvyšším ohodnocením

• Označ jeho sousedy v pořadí jejich ohodnocení

Morganův algoritmus

• Zbývající sousedé uzlu 2 mají stejné ohodnocení

• vyber z nich ten který je spojen více hranami (C=C je zelená)
• je možno též uvažovat hmotnost atomů (u různých)
• když jsou atomy ekvi- valentní, zvol jakýkoliv

• Pokračuj, dokud nejsou označeny všechny atomy

Morganův algoritmus

• Zbývající sousedé uzlu 2 mají stejné ohodnocení

• vyber z nich ten který je spojen více hranami (C=C je zelená)
• je možno též uvažovat hmotnost atomů (u různých)
• když jsou atomy ekvi- valentní, zvol jakýkoliv

• Pokračuj, dokud nejsou označeny všechny atomy

Morganův algoritmus

• Po dokončení

• algoritmu:

• Kanonicky

• indexovaný

• graf.

Morganův algoritmus - zhodnocení

• Výhody algoritmu:

• Nízká složitost algoritmu: O(n2)

• Nevýhody algoritmu:

• Algoritmus může v některých případech indexovat chybně (přiřadit stejný index atomům, které nejsou chemicky ekvivalentní)

Cvičení – Morganův algoritmus

• Oindexujte molekulu 1-chlorpropanu pomocí Morganova algoritmu

Cvičení – Morganův algoritmus - řešení

Kanonické indexování - algoritmy

• Shelleyho-Munkův algoritmus:

• rozšíření původní Morganovy myšlenky
• bere v úvahu také vlastnosti sousedů ohodnocovaného atomu
• složitost: O(n2)

Kanonické indexování – Shelleyho-Munkův algoritmus

• Každému atomu, který není vodík, přiřaď hodnotu CI, což je dvoumístné číslo, jehož první číslice odpovídá stupni atomu a druhá číslice označuje typ atomu (pro uhlík 2, pro dusík 3 a pro kyslík 4).

• 2. Urči počet odlišných hodnot CI, označ jej NCI.

Kanonické indexování – Shelleyho-Munkův algoritmus II

Kanonické indexování – Shelleyho-Munkův algoritmus III

• 3. Každému atomu přiřaď novou hodnotu CI v rozmezí 1 až NCI tak, že atomy s nejmenší puvodní CI hodnotou obdrží 1 a atomy s nejvetší puvodní CI hodnotou obdrží NCI.

• 4.Jestliže je NCI shodné s počtem atomu, které nejsou vodík, číslování nevodíkových atomů je hotovo.

Kanonické indexování – Shelleyho-Munkův algoritmus IV

Kanonické indexování – Shelleyho-Munkův algoritmus V

• 5. Každému atomu přiřaď TCI, což je řetězec pěti dvoumístných čísel s tím, že to nejlevejší odpovídá CI hodnotě příslušného atomu, zbývající čtyri pole obsahují seznam CI sousedních atomů v sestupném pořadí podle velikosti zleva doprava. Pokud má atom méně než čtyři sousední atomy, jsou zbývající místa vyplněna nulami.

• 6. Urči počet odlišných hodnot TCI, označ jej NTCI.

Kanonické indexování – Shelleyho-Munkův algoritmus VI

Kanonické indexování – Shelleyho-Munkův algoritmus VII

• 7. Každému atomu přiřaď novou hodnotu TCI v rozmezí 1 až NTCI tak, že atomy s nejmenší původní TCI hodnotou obdrží 1 a atomy s nejvetší původní TCI hodnotou obdrží NTCI.

• 8. Jestliže číslo NTCI je menší nebo rovno číslu NCI, jdi na 9, jinak naplň CI každého atomu hodnotou TCI, hodnotu NCI naplň hodnotou NTCI a proveď další iteraci algoritmu.

• 9. Číslování nevodíkových atomů je hotovo.

Kanonické indexování – Shelleyho-Munkův algoritmus VIII

Kanonické indexování – Shelleyho-Munkův algoritmus IX

• 10. Vytvoř kanonické indexování (indexovány i vodíky):

• Atom s nejvyšším indexem dostane kanonický index 1.

• Vodíky na tomto atomu dostanou čísla 2, 3, ..., M.

• Atom s druhým nejvyšším indexem dostane kanonický index M+1.

• Vodíky na tomto atomu dostanou čísla M+2, M+3, ...

• Atd.

Kanonické indexování – Shelleyho-Munkův algoritmus X

Shelleyho-Munkův algoritmus - zhodnocení

• Výhody algoritmu:

• Nízká složitost algoritmu: O(n2)
• Nižší pravděpodobnost chyby než u Morganova algoritmu

• Nevýhody algoritmu:

• Pomalejší a implementačně náročnější než Morganův algoritmus.

Cvičení - Shelleyho-Munkův algoritmus

• Oindexujte molekulu 1-chlorpropanu pomocí Shelleyho-Munkova algoritmu

Cvičení - Shelleyho-Munkův algoritmus - řešení

Literatura o kanonickém indexování

• Kvasnička V., Kratochvíl M., Koča J.: Matematická chemie a počítačové řešení syntéz. Academia (1987)

• Ivanciuc O.: Canonical numbering and constitutional symetry, Encyclopedia of Computational Chemistry. John Wiley & Sons (1998)

• Barnard J.: Chemical structure representation and search systems. Cheminfo, Indiana University (2002)