InChIKey

A standard International Chemical Identifier egy a molekulaszerkezetből számított, a molekulára nézve egyedi kémiai azonosító, mely a molekula egyes tulajdonságait elkülönítve, rétegekben adja meg (a rétegeket a /-jel választja el egymástól).

Az InChIKey a standard InChI-ből számított fix hosszúságú, „majdnem” egyedi azonosító (lásd alább), mely adatbázisbeli ill. interneten való keresésre alkalmas. Pontosan 27 betűből (benne két kötőjelből) áll:

• 14 nagybetű az InChI fő rétegéből számítva. A molekula vázát adja meg: összegképlet, az atomok közötti kémiai kötések.
• kötőjel
• 8 nagybetű az InChI fennmaradó rétegeiből számítva. A molekula térszerkezetét és az izotópokat adja meg.
• S betű, amely azt jelzi, hogy az InChIKey a standard InChI-ből készült
• az InChI verzióját jelző nagybetű (jelenleg az 1-es verzió az utolsó, kódja A)
• kötőjel
• a protonréteg jelzője (1 nagybetű)

Az InChIKey fix hosszúság adatbázisbeli kódolásra használható, a nagybetűket pedig az internetes keresők nem szabdalják szavakra – ellentétben a kódolatlan InChI-vel, mely zárójeleket, /-jeleket, kötőjeleket tartalmaz.

Kiszámítás

A 14-karakteres kód forrása a standard InChI-ben a prefix utántól, az összegképlettel kezdődik, és a proton (/p) rétegig tart. A 14 karakter a szöveg sha-256 kriptográfiai hash függvényének 65 bitjéből számítódik; e 65 bit a 256 bites hash első 72 bitjében található.

A 8-karakteres kód a protonréteg utántól az InChI végéig tartó szövegrészből számítódik. (A protonréteg egyik hash-ben sem szerepel, csak az InChIKey utolsó karakterében.) Ez a szöveg hash-ének 37 bitje az első 40 biten belül.

A 65 bit négy 14 bites és egy 9 bites részből tevődik össze. A 37 bitben két 14 bites és egy 9 bites rész van. A 14 bit három betűt (tripletet), a 9 bit két betűt (dupletet) ad meg InChIKey-ben.

14 biten 16384-féle szám ábrázolható, míg az angol abc három betűjével 26³ = 17576, azaz bizonyos betűhármasok nem fognak előfordulni. A kód alkotói úgy döntöttek, hogy az EAA–EZZ és TAA–TTV közötti kódokat hagyják el, hogy még kisebb legyen az esélye annak, hogy a kód értelmes szóval legyen azonos. Az angol nyelvben ui. gyakori az E és T betű, és az ezzel kezdődő szavak.

A tripletek és dupletek sha-256-ból vett bitjei

Sorsz.	14 betű
1.	10,11,12,13,14,15, 0, 1, 2, 3, 4, 5, 6, 7
2.	28,29,30,31,16,17,18,19,20,21,22,23, 8, 9
3.	46,47,32,33,34,35,36,37,38,39,24,25,26,27
4.	48,49,50,51,52,53,54,55,40,41,42,43,44,45
5.	71,56,57,58,59,60,61,62,63
8 betű
3.	35,36,37,38,39,24,25,26,27

Ez azt jelenti, hogy ha a 14 bites kód nagyobb vagy egyenlő 2704-gyel, akkor a kódhoz hozzá kell adni 676-ot. Ha az így kapott kód nagyobb vagy egyenlő 12168-cal, akkor a kódhoz hozzá kell adni még 516-ot.

A 9 bites kódoknál (melyek a hash végén vannak) a legnagyobb betűpárokat hagyták el, vagyis itt nincs kódkorrekció.

A fenti 14- ill. 9 bites kódot 26-os számrendszerbe kell átváltani a 3 ill. 2 betű előállításához.

Az eredeti elképzelés az volt, hogy az sha-256 első 14 bitje adja az első három betűt, a második 14 bit a második betűhármast, stb. Az IUPAC által kiadott programban egy csúnya programozási hiba folytán azonban összekeveredett a bitek sorrendje. Ez az InChIKey minőségét nem befolyásolta, de a kódnak az IUPAC által leírt algoritmustól eltérő előállítását megnehezítette. Az IUPAC kijavította a programozási hibát, addigra azonban az InChIKey már elterjedt (ne felejtsük: az InChIKey legfontosabb jellemzője, hogy a molekulából számítható egyedi kód), így a javítást a gyakorlatban már nem használták, és a hibás program által előállított InChIKey lett a szabvány.

A jobb oldali táblázat mutatja, hogy a 14- ill. 9 bites csoportok egyes bitjei az sha-256 hányadik bitjeiből állnak össze. Az eredeti terv a 0-tól 64-ig ill. 36-ig egyesével növekvő táblázat volt.

Egyediség

A hash-függvény alkalmazása a kulcs rövidítésével megkönnyíti a keresést, azonban nem tudja biztosítani, hogy két különböző kulcshoz tartozó hash-érték biztosan különböző legyen. A hash segítségével nagyon gyorsan ki lehet keresni a néhány szóba jöhető rekordot, melyek közül aztán lassabb módszerrel keresik ki az eredeti feltételnek eleget tevőket.

Az InChIKey megalkotásakor lehetett tudni, hogy előbb-utóbb találnak ütközést, ui. a létező vegyületek száma jóval nagyobb, mint a lehetséges InChIKey-ek száma. Az InChIKey méretét úgy határozták meg, hogy a 2007-es bevezetéskor létező legnagyobb, 50–100 millió molekulavázat tároló adatbázisoknál elhanyagolható legyen az ütközés esélye.

Az ütköző kulcsok számának várható értéke a ${\frac {k(k-1)}{2p}}\approx {\frac {k^{2}}{2p}}$ formulával számítható, ahol $p$ a kulcs lehetséges értékeinek száma és $k$ az adatbázisbeli rekordok száma.

Molekulaváz esetén $p=2^{65}$. Egymilliárd ($k=10^{9}$) rekordnál ez az érték 0,0136, tízmilliárd ($k=10^{10}$) rekordnál ennek százszorosa, 1,3553. A várható érték kb. 6,1×10⁹ rekordnál éri el a 0,5-et.

A sztereoizomer kulcsnál $p=2^{37}$. Százezer ($k=10^{5}$) rekordnál az ütközés várható értéke 0,03680, egymilliónál ($k=10^{6}$) 3,68. A várható érték kb. 3,7×10⁵-nál éri el a 0,5-et, vagyis az 50%-os ütközési esélyt.

Az első adatbázisbeli kulcsütközést 2009-ben fedezték fel a spongistatin I 2²⁶ sztereoizomerje között. Az első molekulavázak közötti ütközésre két év múlva, 2011-ben találtak rá.

Források

• Igor Pletnev, Andrey Erin, Alan McNaught, Kirill Blinov, Dmitrii Tchekhovskoi and Steve Heller: InChIKey collision resistance: an experimental testing (Journal of Cheminformatics)
• InChI - the worldwide chemical structure identifier standard (PMC)
• InChI Source Code Documentation (IUPAC)

Kapcsolódó lapok

• International Chemical Identifier (InChI)
• hasítófüggvény
• kriptográfiai hash függvény
• Secure Hash Algorithm(en)