|
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 [[polinomio|polinomiale]], tuttavia utilizza tecniche quali il [[backtracingbacktracking]] 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 [[chemoinformaticachemioinformatica]], 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 [[legame covalente|legami covalenti]].<ref>{{cita pubblicazione|autore=J. R. Ullmann|titolo=An Algorithm for Subgraph Isomorphism|rivista=Journal of the ACM|volume=23|numero=1|pp=31-42|anno=1976|url=http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf|accesso=11 giugno 2013|urlarchivio=https://web.archive.org/web/20131029205845/http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf|dataarchivio=29 ottobre 2013|urlmorto=sì}}</ref>
==Algoritmo di Ullman in chemoinformaticachemioinformatica==
L'algoritmo si basa su una [[matrice (matematica)|matrice]] con dimensioni <math>m * n</math> dove <math>m</math> è la il numero di [[atomo|atomi]] della molecola e <math>n</math> 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).<ref name="3d chemical structure">{{cita pubblicazione|autore=A. T. Brint, P. Willett|titolo=Pharmacophoric Pattern Matching in Files of 3D Chemical Structures: Comparison of Geometric Searching Algorithms|rivista=J. Mol. Graph.|anno=1987|volume=5|numero=1|pp=49-56|doi=10.1016/0263-7855(87)80045-0|accesso=11 giugno 2013}}</ref>
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 [[legame chimico|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, asintoticamentecome già accennato rimane però asintoticamente esponenziale.<ref name="3d chemical structure"/>
==BibliografiaNote==
<references/>
{{Portale|chimica|informatica}}
* J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
Michael R. Garey and David S. Johnson (1979).
[[Categoria:Algoritmi Informaticasui grafi|Ullmann]]
| 