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... Megfordítva, bármely teljes gráfinvariáns segítségével megszerkeszthető egy kanonikus alak.. 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..
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.InChI Software Downloads (InChITRUST)
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-algoritmusLásd: InChIKey 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
bélyegkép|jobbra|300px|
Ö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.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é.
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
.---------. 150px
(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
Források IUPAC International Chemical Identifier (InChI) Programs User’s Guide (IUPAC) InChI Canonicalization Algorithm
Kapcsolódó szócikkek International Chemical Identifier
Kategória:Kémia Kategória:Gráfalgoritmusok