Morganov algoritmus je algoritmus používaný v chemoinformatike na porovnávanie a jednoznačnú identifikáciu molekulových grafov. Jeho hlavným cieľom je na základe 2D topológie určiť, či dva grafické zápisy molekúl reprezentujú tú istú chemickú štruktúru a to nezávisle od spôsobu kreslenia alebo očíslovania atómov. Algoritmus priraďuje atómom hodnoty založené na ich topologickom okolí a tieto hodnoty iteratívne spresňuje, čím vytvára invarianty charakteristické pre danú štruktúru. Princíp Morganoveho algoritmu je základom mnohých metód používaných pri práci s molekulovými množinami a v chemických databázach kde je potrebné vylúčiť duplicitné štruktúry. Príkladom je registrácia látok v Chemical Abstracts Service (CAS). V modernom drug discovery sa princípy Morganovho algoritmu používajú aj ako základ pre niektoré typy molekulových fingerprintov (napr. ECFP), ktoré sa uplatňujú pri vyhľadávaní podobných molekúl a virtuálnom screeningu.

História Morganov algoritmus bol vyvinutý v 60. rokoch 20. storočia v rámci Chemical Abstracts Service (CAS), ktorá budovala jeden z prvých rozsiahlych počítačových systémov na správu chemických informácií. Hlavným cieľom CAS bolo vytvoriť registračný systém chemických látok, v ktorom by bola každá jedinečná chemická štruktúra uložená iba raz a prepojená so všetkými dostupnými informáciami, ako sú vedecké publikácie a experimentálne údaje.

Algoritmus publikoval H. L. Morgan v roku 1965 v článku The Generation of a Unique Machine Description for Chemical Structures: A Technique Developed at Chemical Abstracts Service. Morganov algoritmus sa stal jedným z prvých prakticky použiteľných riešení problému ekvivalencie molekulových grafov v chemických databázach. Princípy zavedené Morganom sa postupne uplatnili v ďalších metódach štandardizácie chemických štruktúr, vrátane algoritmov na generovanie kanonických lineárnych zápisov molekúl a moderných molekulových fingerprintov. Samotný Morganov algoritmus bol v priebehu času rozšírený a nahradený sofistikovanejšími postupmi, no jeho koncept rozšírenej konektivity (extended connectivity) zostáva jedným zo základných stavebných prvkov súčasných nástrojov na prácu s chemickými štruktúrami a databázami.

Algoritmus Morganov algoritmus pracuje s molekulou reprezentovanou ako molekulový graf, ktorý je v počítači uložený vo forme tzv. connection table, ktorá predstavuje tabuľkový zápis atómov a ich vzájomných väzieb. Takáto reprezentácia umožňuje jednoznačný zápis chemickej štruktúry, no v závislosti od číslovania atómov môže existovať viacero ekvivalentných zápisov tej istej molekuly.

Extended connectivity (rozšírená konektivita) Kľúčovým prvkom Morganovho algoritmu je pojem extended connectivity, teda iteratívne rozširovanie informácie o lokálnom topologickom okolí atómu.

Algoritmus pracuje v nasledujúcich krokoch:

Inicializácia hodnôt atómov: Každému atómu sa priradí počiatočná hodnota, ktorá zodpovedá jeho konektivite, teda počtu priamo viazaných nevodíkových atómov. Tát hodnota je invariantná voči číslovaniu atómov. Iteratívna aktualizácia hodnôt: V každej iterácii sa nová hodnota atómu vypočíta ako súčet hodnôt jeho susedných atómov z predchádzajúceho kroku. Týmto spôsobom sa do hodnoty atómu postupne premieta informácia o čoraz širšom topologickom okolí. Zastavenie iterácie: Iterácia pokračuje dovtedy, kým sa počet rôznych hodnôt v grafe ďalej zvyšuje. Výsledné hodnoty predstavujú topologické invarianty, ktoré sú charakteristické pre danú molekulovú štruktúru a nezávislé od jej pôvodného číslovania

náhľad|736x736bod|Obr. 1 Princíp rozšírenej konektivity. V každej iterácii algoritmu sa hodnota každého uzla nahradí súčtom hodnôt jeho susedných uzlov z predchádzajúceho kroku. Po každej iterácii sa sleduje počet rôznych hodnôt v grafe (k), ktorý vyjadruje mieru topologického rozlíšenia uzlov. Iterácia pokračuje dovtedy, kým sa hodnota k zvyšuje. Ak sa v nasledujúcom kroku už nezvýši, proces sa ukončí a za výsledok sa považujú hodnoty z predchádzajúcej iterácie.

Na základe vypočítaných hodnôt rozšírenej konektivity algoritmus zavádza čiastočné usporiadanie atómov. Atómy s vyššími hodnotami majú pri číslovaní prednosť pred atómami s nižšími hodnotami. Tento krok výrazne zmenšuje množinu možných číslovaní atómov, ktoré je potrebné zohľadniť. Namiesto generovania všetkých teoreticky možných zápisov molekuly algoritmus pracuje len s obmedzenou podmnožinou kandidátov, ktoré sú konzistentné s daným usporiadaním.

Výber kanonickej reprezentácie Z redukovanej množiny kandidátnych zápisov sa následne vytvoria príslušné connection tables. Tieto tabuľky sa porovnávajú lexikograficky ako reťazce symbolov v pevne definovanom poradí (väzby, uzly, typy atómov a pod.). Ako kanonická reprezentácia sa vyberie tá tabuľka, ktorá je podľa tohto poradia „najmenšia“.

Význam a využitie Morganov algoritmus položil základy pre:

registračné systémy chemických látok (napr. CAS Registry), generovanie kanonických lineárnych zápisov molekúl (napr. SMILES), moderné molekulové fingerprinty založené na rozšírenej konektivite (ECFP).

Referencie

Kategória:Chemoinformatika