Gráfok kanonikalizációja

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

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

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

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

Benzotiazol(en)

Összegképlet: C₇H₅NS. 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

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

• IUPAC International Chemical Identifier (InChI) Programs User’s Guide (IUPAC)
• InChI Canonicalization Algorithm

Kapcsolódó szócikkek

• International Chemical Identifier
• Benzotiazol(en)