Algoritmo di Ullmann
L'algoritmo di Ullmann è un algoritmo per la soluzione del problema dell'isomorfismo di sottografi. Il problema è NP-completo e l'algoritmo non fornisce una soluzione in tempo polinomiale, tuttavia utilizza tecniche quali il backtracking per diminuire il tempo effettivo di esecuzione, che però non hanno effetto sulla complessità asintotica, che rimane esponenziale.
L'algoritmo di Ullmann trova applicazione nella chemioinformatica, in particolare nella ricerca di specifici frammenti all'interno di una molecola. Una molecola può essere vista tramite la sua formula di struttura, come un grafo non orientato, i cui vertici sono gli atomi e i cui spigoli sono i legami covalenti.[1]
Algoritmo di Ullman in chemioinformatica[modifica | modifica wikitesto]
L'algoritmo si basa su una matrice con dimensioni dove è il numero di atomi della molecola e il numero di atomi del frammento da ricercare. Ogni colonna rappresenta quindi un atomo del frammento, ogni riga un atomo della molecola completa. Da una situazione iniziale in cui in tutte le posizioni della tabella è presente un "1", l'idea è che alla fine rimanga un "1" soltanto nelle posizioni in cui l'atomo nel frammento cercato corrisponde ad una posizione nella molecola. In ogni colonna e riga perciò alla fine può esserci soltanto un "1" (si vuole cercare solo un'occorrenza del frammento).[2]
Per diminuire il numero di combinazioni da verificare, si utilizza una fase preliminare in cui si sfruttano le conoscenze chimiche: viene messo uno "0" in ogni posizione in cui gli atomi (su riga e colonna) non sono dello stesso tipo (per esempio C e N). Inoltre viene messo uno "0" anche in ogni posizione in cui gli atomi del frammento abbiano un numero di legami maggiore a quello nella molecola principale.
In seguito si provano diverse combinazioni di 1 e 0, cercando però ad ogni passaggio di individuare quali combinazioni non siano accettabili, in modo da diminuire in modo significativo il tempo di esecuzione, che, come già accennato rimane però asintoticamente esponenziale.[2]
Note[modifica | modifica wikitesto]
- ^ J. R. Ullmann, An Algorithm for Subgraph Isomorphism (PDF), in Journal of the ACM, vol. 23, n. 1, 1976, pp. 31–42. URL consultato l'11 giugno 2013 (archiviato dall'url originale il 29 ottobre 2013).
- ^ a b A. T. Brint, P. Willett, Pharmacophoric Pattern Matching in Files of 3D Chemical Structures: Comparison of Geometric Searching Algorithms, in J. Mol. Graph., vol. 5, n. 1, 1987, pp. 49-56, DOI:10.1016/0263-7855(87)80045-0. URL consultato l'11 giugno 2013.
