Algoritmo di Ullmann: differenze tra le versioni

Versione delle 19:51, 19 feb 2019

Versione delle 12:06, 29 apr 2019

Riga 5:

==Algoritmo di Ullman in chemioinformatica==

L'algoritmo si basa su una [[matrice (matematica)|matrice]] con dimensioni <math>m * n</math> dove <math>m</math> è 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|url=httphttps://www.sciencedirect.com/science/article/pii/0263785587800450|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.