Algoritmo di Ullmann: differenze tra le versioni

Versione delle 13:45, 5 set 2007

Versione delle 13:10, 28 ott 2012

Riga 5:

==Algoritmo di Ullman in chemoinformatica==

L'algoritmo si basa su una matrice con dimensioni m * n dove m è la il numero di [[atomo|atomi]] della molecola e n 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).

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.