<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:wx="http://ilps.science.uva.nl/WikiXML/wx" xml:lang="it" lang="it">
<head>
<title>Algoritmo di Ullmann</title>
<meta name="wx_namespace" content="0"/>
<meta name="wx_pagename" content="Algoritmo_di_Ullmann"/>
<meta name="wx_page_id" content="1131062"/>
</head>
<body>
<div id="wx_article">
<wx:section level="1" title="Algoritmo di Ullmann" id="wxsec1"><h1 class="pagetitle" id="wx1">Algoritmo di Ullmann</h1>

<p id="wx2">L'<b id="wx3">algoritmo di Ullmann</b> è un <a href="/wit/Algoritmo" title="Algoritmo" wx:linktype="known" wx:pagename="Algoritmo" wx:page_id="16" id="wx4">algoritmo</a> per la soluzione del problema dell'<a href="/wit/Isomorfismo_di_sottografi" title="Isomorfismo di sottografi" wx:linktype="known" wx:pagename="Isomorfismo_di_sottografi" wx:page_id="1138062" id="wx5">isomorfismo di sottografi</a>. Il problema è <a href="/wit/NP-completo" title="NP-completo" wx:linktype="known" wx:pagename="NP-completo" wx:page_id="458403" id="wx6">NP-completo</a> e l'algoritmo non fornisce una soluzione in tempo <a href="/wit/Polinomiale" class="new" title="Polinomiale" wx:linktype="unknown" wx:pagename="Polinomiale" id="wx7">polinomiale</a>, tuttavia utilizza tecniche quali il <a href="/wit/Backtracing" class="new" title="Backtracing" wx:linktype="unknown" wx:pagename="Backtracing" id="wx8">backtracing</a> per diminuire il tempo effettivo di esecuzione, che però non hanno effetto sulla <a href="/wit/Complessit%C3%A0_asintotica" class="new" title="Complessità asintotica" wx:linktype="unknown" wx:pagename="Complessità_asintotica" id="wx9">complessità asintotica</a>, che rimane <a href="/wit/Esponenziale" title="Esponenziale" wx:linktype="known" wx:pagename="Esponenziale" wx:page_id="117154" id="wx10">esponenziale</a>.</p>

<p id="wx11">L'algoritmo di Ullmann trova applicazione nella <a href="/wit/Chemoinformatica" class="new" title="Chemoinformatica" wx:linktype="unknown" wx:pagename="Chemoinformatica" id="wx12">chemoinformatica</a>, in particolare nella ricerca di specifici frammenti all'interno di una <a href="/wit/Molecola" title="Molecola" wx:linktype="known" wx:pagename="Molecola" wx:page_id="2761" id="wx13">molecola</a>. Una molecola può essere vista tramite la sua <a href="/wit/Formula_di_struttura" title="Formula di struttura" wx:linktype="known" wx:pagename="Formula_di_struttura" wx:page_id="217136" id="wx14">formula di struttura</a>, come un <a href="/wit/Grafo" title="Grafo" wx:linktype="known" wx:pagename="Grafo" wx:page_id="651611" id="wx15">grafo</a> non orientato, i cui vertici sono gli atomi e i cui spigoli sono i <a href="/wit/Legame_covalente" title="Legame covalente" wx:linktype="known" wx:pagename="Legame_covalente" wx:page_id="22083" id="wx16">legami covalenti</a>.</p>

<a id="Algoritmo_di_Ullman_in_chemoinformatica" name="Algoritmo_di_Ullman_in_chemoinformatica"/>
<wx:section level="2" title="Algoritmo di Ullman in chemoinformatica" id="wxsec2"><h2 id="wx17">Algoritmo di Ullman in chemoinformatica</h2>

<p id="wx18">L'algoritmo si basa su una matrice con dimensioni m * n dove m è la il numero di <a href="/wit/Atomo" title="Atomo" wx:linktype="known" wx:pagename="Atomo" wx:page_id="326" id="wx19">atomi</a> 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).</p>

<p id="wx20">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 <a href="/wit/Legame_chimico" title="Legame chimico" wx:linktype="known" wx:pagename="Legame_chimico" wx:page_id="41868" id="wx21">legami</a> maggiore a quello nella molecola principale.</p>

<p id="wx22">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 <a href="/wit/Tempo_di_esecuzione" title="Tempo di esecuzione" wx:linktype="known" wx:pagename="Tempo_di_esecuzione" wx:page_id="132052" id="wx23">tempo di esecuzione</a>, che, come già accennato rimane però asintoticamente esponenziale.</p>

<a id="Bibliografia" name="Bibliografia"/>
</wx:section><wx:section level="2" title="Bibliografia" id="wxsec3"><h2 id="wx24">Bibliografia</h2>

<ul id="wx25">
<li id="wx26">
<p id="wx27">J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.</p>
</li>

<li id="wx28">
<p id="wx29">A. T. Brint, P. Willett, "Pharmacophoric Pattern Matching in Files of 3D Chemical Structures: Comparison of Geometric Searching Algorithms." J. Mol. Graph. 1987, 5, 49-56</p>
</li>
</ul>
</wx:section></wx:section></div>
<div id="wx_categorylinks">
<a href="/wit/index.php?title=Speciale:Categories&amp;article=Algoritmo_di_Ullmann" title="Speciale:Categories" wx:linktype="known" wx:pagename="Speciale:Categories" id="wx30">Categoria</a>: <span dir="ltr" id="wx31"><a href="/wit/Categoria:Algoritmi" title="Categoria:Algoritmi" wx:linktype="known" wx:pagename="Categoria:Algoritmi" wx:page_id="42921" id="wx32">Algoritmi</a></span></div>
<div id="wx_languagelinks">
</div>
</body>
</html>
