Gráfok kanonikalizációja

A Wikipédiából, a szabad enciklopédiából

A gráfelmélet területén a gráfok kanonikalizációja vagy kanonizációja egy adott G gráf kanonikus alakjának megtalálása. A kanonikus forma egy olyan Canon(G) címkézett gráf, ami izomorf G-vel, továbbá minden G-vel izomorf gráfnak is ugyanez a kanonikus alakja. Így tehát a gráfkanonikalizáció problémájának megoldása automatikusan megoldja a gráfizomorfizmus problémáját is: Két gráf, G és H akkor izomorf, ha kanonikus alakjaik, Canon(G) és Canon(H) megegyeznek.

A gráfok kanonikus alakja a teljes gráfinvariánsok egyik példája: bármely két izomorf gráf kanonikus alakja megegyezik és bármely két nem izomorf gráf kanonikus alakja különbözik.[1][2] Megfordítva, bármely teljes gráfinvariáns segítségével megszerkeszthető egy kanonikus alak.[3] Az n csúcsú gráf csúcspontjait megszámozhatjuk 1-től n-ig egész számokkal, így a gráf kanonikus alakja a csúcsainak egy permutációjával is leírható. A gráfok kanonikus formáját kanonikus címkézésnek is nevezik.[4]

Vegyészeti alkalmazása[szerkesztés]

A kanonikalizációs algoritmus egy vegyület vázának egységes, a molekula helyzetétől független leírását lehetővé tevő módszer. Szerkezettel megadott molekulák keresésére használják.

A módszert az IUPAC dolgozta ki 2000-től kezdve egy egységes azonosító, az International Chemical Identifier (InChI) kifejlesztése során, és kiadott egy programot is, mely az azonosítót kiszámítja. A program LGPL licenc alatt, Windows és Linux operációs rendszerben fut.[5]

Molekulaváz[szerkesztés]

A molekula vázán e szócikkben a molekulát alkotó atomokat és az azok közötti kötéseket értjük. Nem teszünk különbséget kettős és hármas kötés (vagyis a hidrogénatomok száma) között, és nem vesszük figyelembe a molekula más tulajdonságait sem (térszerkezet, izotópok stb.).

Matematikai értelemben a molekulaváz egy olyan gráf, melynek csúcsai különbözőek (is) lehetnek.

A kanonikalizált váz (gráf) a molekulát alkotó atomokhoz rendel egy-egy egyedi címkét (sorszámot), mely független a molekula lerajzoláskori helyzetétől.

Az InChI-ben a váz megadására egy szabványos gráfbejárási algoritmust használnak (melyet e szócikk nem tartalmaz), és ezt az utat adják meg a kanonikus atomszámokkal (lásd alább). Az atomokhoz kötődő hidrogének száma és a molekula többi tulajdonsága is része az InChI-nek, de a molekulaváztól különböző (al)rétegben van megadva. (A rétegeket és alrétegeket a / jel választja el egymástól az InChI-ben.)

A kémiai adatbázisok – melyekben általában több tízmillió molekula található – kanonikus formában tárolják a molekulák szerkezetét. A keresőkérdéseket átalakítják e kanonikus formára, és egy hash-algoritmus[6] segítségével igen gyorsan megtalálják a molekulát.

Algoritmus[szerkesztés]

Az algoritmus lényege: külön csoportba sorolja a különböző atomokat, azon belül alcsoportokat hoz létre a szomszédos atomok száma szerint. Ha egy (al)csoportban még így is több atom marad, akkor a 2-, 3-, 4- stb. atomnyi távolságra levő atomokat is figyelembe veszi.

Példa: 1,3-benzotiazol[szerkesztés]

Benzotiazol(en)

Összegképlet: C7H5NS. A hidrogénatomokat elhagyjuk, az elemeknek abc-rendben számot adunk: C=1, N=2, S=3.

Az alábbi táblázatokban az Atom oszlopban a szerkezeti képletben kékkel jelölt címkéket használtuk (ez a szabványos heterogyűrűs atomszámozás, de bármilyen megkülönböztető címkét használhattunk volna). A Szomszédok oszlopban az atommal szomszédos atomok címkéi vannak. E két oszlop a számítás során nem változik.

Atom Szomszédok Régi Új
1 2,7a 3,2 9
2 1,3 1,2 5
3 2,3a 2,2 8
3a 3,4,7a 1,3 7
4 3a,5 1,2 5
5 4,6 1,2 5
6 5,7 1,2 5
7 6,7a 1,2 5
7a 1,3a,7 1,3 7
Atom Szomszédok Régi Új
1 2,7a 9,5,7 9
2 1,3 5,8,9 5
3 2,3a 8,5,7 8
3a 3,4,7a 7,5,7,8 6
4 3a,5 5,5,7 4
5 4,6 5,5,5 2
6 5,7 5,5,5 2
7 6,7a 5,5,7 4
7a 1,3a,7 7,5,7,9 7
Atom Szomszédok Régi Új
1 2,7a 9,5,7 9
2 1,3 5,8,9 5
3 2,3a 8,5,6 8
3a 3,4,7a 6,4,7,8 6
4 3a,5 4,2,6 3
5 4,6 2,2,4 2
6 5,7 2,2,4 2
7 6,7a 4,2,7 4
7a 1,3a,7 7,4,6,9 7
Atom Szomszédok Régi Új
1 2,7a 9,5,7 9
2 1,3 5,8,9 5
3 2,3a 8,5,6 8
3a 3,4,7a 6,3,7,8 6
4 3a,5 3,2,6 3
5 4,6 2,2,3 1
6 5,7 2,2,4 2
7 6,7a 4,2,7 4
7a 1,3a,7 7,4,6,9 7

A bal oldali táblázat Régi oszlopának első száma az elemhez rendelt érték (C=1, N=2, S=3), a második szám a szomszédos atomok száma. Az oszlop kitöltése után a táblázatot sorba rendezzük ezen oszlop szerint, és a kapott sorszámokat írjuk az Új oszlopba. Ha a rendezéskor két vagy több egymás alatti érték azonos, akkor az értéket tartalmazó legutolsó sor számát írjuk valamennyi sorba.

Vegyük észre (az Új oszlop rendezésével), hogy az algoritmus máris elkülönítette a két heteroatomot a szénatomoktól, és a szénatomokat is két csoportra osztotta aszerint, hogy 2 vagy 3 szomszédjuk van-e. Ez a felosztás a későbbiekben már nem változik, csak az ezeken belüli sorrend.

A második táblázat Régi oszlopának első száma az előző táblázatbeli Új érték, a többi szám a szomszédok előző táblázatbeli Új értéke. A második táblázat Új oszlopát ugyanúgy kapjuk, mint az első táblázatban: a Régi oszlop szerint sorba rendezünk, és a sorszám adja az Új értéket.

Ezt az eljárást folytatjuk addig, amíg az Új oszlop valamennyi száma különböző lesz, vagy az előző táblázathoz képest már nincs változás az Új oszlopban.[7]

A második táblázatban a 2-es atom már külön csoportba kerül, mert a két szomszédjának nagyobb az értéke. Ugyancsak külön csoportba kerül az 5,6 és 4,7 atompár, mert az utóbbiak egyik szomszédjának három szomszédja van, míg az 5,6 mindkét szomszédjának 2 szomszédja van.

A harmadik táblázat már a 4. és 7. atom között is különbséget tud tenni azon az alapon, hogy a 7-es közelebb van a kénhez, és a kénhez tartozó érték nagyobb a nitrogénénél.

A negyedik táblázat már az 5. és 6. atom között is különbséget tesz a 4. ill. 7. atom alapján.
Az 1,3-benzotiazol InChI-je: InChI=1S/C7H5NS/c1-2-4-7-6(3-1)8-5-9-7/h1-5H, ahol az első vastag betűs rész az összegképletet, a második a bejárási utat adja meg. A 4. táblázat Atom és Új oszlopa alapján visszaírva az ábrán látható kék számokra: 

.-----------4 
|          /
5-6-7-7a-3a 
      |    \
      |     3-2-1
      |         |
      .---------.

(Az InChI-ben az 1-5H azt mondja meg, hogy az 1–5. atomhoz – kék számokkal: 2,4,5,6,7 – egy-egy hidrogénatom kapcsolódik.)

Jegyzetek[szerkesztés]

  1. ↑ Arvind, Vikraman; Das, Bireswar & Köbler, Johannes (2008), "A logspace algorithm for partial 2-tree canonization", Computer Science – Theory and Applications: Third International Computer Science Symposium in Russia, CSR 2008 Moscow, Russia, June 7-12, 2008, Proceedings, vol. 5010, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 40–51, DOI 10.1007/978-3-540-79709-8_8.
  2. ↑ Arvind, V.; Das, Bireswar & Köbler, Johannes (2007), "The space complexity of k-tree isomorphism", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, vol. 4835, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 822–833, DOI 10.1007/978-3-540-77120-3_71.
  3. ↑ Gurevich, Yuri (1997), "From invariants to canonization", Bulletin of the European Association for Theoretical Computer Science (no. 63): 115–119, <http://research.microsoft.com/en-us/um/people/gurevich/opera/131.pdf>.
  4. ↑ Babai, Laszlo & Luks, Eugene (1983), "Canonical labeling of graphs", Proc. 15th ACM Symposium on Theory of Computing, pp. 171–183, DOI 10.1145/800061.808746.
  5. ↑ InChI Software Downloads (InChITRUST)
  6. ↑ Lásd: InChIKey
  7. ↑ Az algoritmus nem tud különbséget tenni pl. a karboxil-csoport két oxigénje között, így az ezekhez tartozó sorszámok sohasem válnak különbözővé.

Források[szerkesztés]

Kapcsolódó szócikkek[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Gráfok_kanonikalizációja&oldid=26558556”