Kanonické indexování vrcholů molekulového grafu Molekulový graf: g =



Yüklə 490 b.
tarix02.03.2018
ölçüsü490 b.
#29133


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í = indexování, které splňuje následující podmínky:

    • lze vygenerovat algoritmicky
    • libovolnému atomu libovolné molekuly přísluší vždy jistý index J (bez ohledu na to, jakým molekulovým grafem je molekula reprezentována)

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.



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)



Yüklə 490 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə