Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_15:vuoto [16/05/2016 alle 05:19 (10 anni fa)] – Roberto Grossi
+++ matematica:asd:asd_15:vuoto [16/05/2016 alle 13:36 (10 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 1: / Linea 1: @@
 ====== Progetto di ASD 2015/2016 ======
-Il progetto si basa su file presi dal [[http://www.rcsb.org/pdb/home/home.do|Protein Data Bank]] (PDB) e richiede di rappresentare ciascuna proteina come un grafo: prese due tali proteine, occorre restituire la dimensione del loro sottografo comune più grande. Segue il dettaglio di quanto richiesto.
+Il progetto si basa su file presi dal [[http://www.rcsb.org/pdb/home/home.do|Protein Data Bank]] (PDB) e richiede di rappresentare ciascuna proteina come un grafo: prese due tali proteine, occorre restituire la dimensione del loro sottografo comune più grande possibile trovato entro un certo limite di tempo. Segue il dettaglio di quanto richiesto.
-Dato un grafo connesso e non orientato G = (V,E) e un sottoinsieme di vertici X di V, il sottografo indotto G[X] = (X, E_X) ha X come insieme di vertici e E_X = { {u,v} in E :  u,v in X } come insieme di archi: in sostanza, si sceglie X da V e poi si ereditano in modo implicito tutti gli archi di G che collegano i nodi di X tra di loro. Tale sottografo è connesso se per ogni coppia di vertici in X esiste sempre un cammino che li collega tramite archi di G[X].
+Dato un grafo connesso e non orientato G = (V,E) e un sottoinsieme di vertici X di V, il sottografo indotto G[X] = (X, E_X) ha X come insieme di vertici e E_X = { {u,v} in E :  u,v in X } come insieme di archi: in sostanza, si sceglie X da V e poi si ereditano in modo implicito tutti gli archi di G che collegano i vertici di X tra di loro. Tale sottografo è connesso se per ogni coppia di vertici in X esiste sempre un cammino che li collega tramite archi di G[X].
-Due grafi G e H ammettono un sottografo comune se esiste un isomorfismo che ne preserva vertici e archi: G[X] = (X, E_X) è un sottografo indotto connesso comune (SICC) se esiste un sottografo indotto H[Y] = (Y, E_Y) di H e un isomorfismo h : X -> Y tale che {u,v} appartiene a E_X sse {h(u), h(v)} appartiene a E_Y. Notare che più isomorfismi h possono soddisfare la condizione precedente (per esempio se il sottografo indotto è una clique). Nel caso che i nodi dei grafi siano etichettati, occorre anche che tali etichette corrispondano attraverso h: l’etichetta di un nodo z in X e quella del nodo h(z) in Y devono essere uguali o compatibili. Se anche gli archi sono etichettati, vale una considerazione analoga.
+Due grafi G e H ammettono un sottografo comune se esiste un isomorfismo che ne preserva vertici e archi: G[X] = (X, E_X) è un sottografo indotto connesso comune (SICC) se esiste un sottografo indotto H[Y] = (Y, E_Y) di H e un isomorfismo h : X -> Y tale che {u,v} appartiene a E_X sse {h(u), h(v)} appartiene a E_Y. Notare che più isomorfismi h possono soddisfare la condizione precedente (per esempio se il sottografo indotto è una clique). Nel caso che i vertici dei grafi siano etichettati, occorre anche che tali etichette corrispondano attraverso h: l’etichetta di un vertice z in X e quella del vertice h(z) in Y devono essere uguali o compatibili. Se anche gli archi sono etichettati, vale una considerazione analoga.
-Il progetto richiedere di trovare il sottografo indotto connesso comune più grande possibile in due grafi etichettati, dandosi come limite un’ora di tempo di calcolo. Infatti il problema è NP-hard per cui il progetto richiede di trovare un’euristica e non è detto che si riesca a beccare il SICC di dimensione massima vista la difficoltà del problema. Tuttavia nei casi reali questo problema va comuqnue risolto con un’euristica, per esempio nelle proteine.
+Il progetto richiedere di trovare il SICC più grande possibile in due grafi etichettati, dandosi come limite un’ora di tempo di calcolo. Infatti il problema è NP-hard per cui il progetto richiede di trovare un’euristica e non è detto che si riesca a beccare il SICC di dimensione massima vista la difficoltà del problema. Tuttavia nei casi reali questo problema va comunque risolto mediante un’euristica, per esempio nelle proteine.
-Tre proteine prese da PDB sono disponibili tramite questo link. Per esempio, sappiamo che l’SICC massima è almeno …. per 1ald e 1fcb, ma il progetto ammette che uno possa trovarne una più piccola di …..
+  * Tre proteine, prese da PDB e denominate ''1ald'', ''1fcb'' e ''4enl'', sono disponibili in {{:matematica:asd:asd_15:proteine.zip|questo file zip}}. Per esempio, sappiamo che l’SICC massima contiene almeno 144 vertici per ''1ald'' vs ''1fcb'', ma il progetto ammette che uno possa trovarne una più piccola di 144.
+  * Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite {{:matematica:asd:asd_15:lorenzotattinislides.pdf|questo link}}.
+  * Un estratto della documentazione sul formato dei file presi da PDB è disponibile tramite {{:matematica:asd:asd_15:estrattodocpdb.pdf|questo link}}.
-Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite questo link.
+Il grafo va costruito da un file PDB come segue. I **vertici** sono gli atomi, descritti nelle linee ATOM. I campi di interesse sono "serial" (identificatore unico dell'atomo), "x", "y", "z" (sue coordinate cartesiane in angstrom) e "element" (simbolo dell'elemento associato all'atomo).
-Un estratto della documentazione sul formato dei file presi da PDB è disponibile tramite questo link.
-Il grafo va costruito da un file PDB come segue. I vertici sono gli atomi, descritti nelle linee ATOM. I campi di interesse sono:
+{{:matematica:asd:asd_15:atom.jpg?600|}}
-- id
+Volendo, si possono utilizzare altre informazioni per tagliare via gli isomorfismi meno interessanti, per esempio guardando alle strutture secondarie chiamate alpha-helix e beta-sheet. Il campo di interesse in ATOM è "resSeq" (riferimento incrociato alla rispettiva strutture secondaria).
-- x , y , z (coordinate cartesiane in angstrom)
-- element name
-Volendo, si possono utilizzare altre informazioni per tagliare via gli isomorfismi meno interessanti, per esempio guardando alle strutture secondarie chiamate alpha-helix e beta-sheet. I campi di interesse in ATOM sono:
+{{:matematica:asd:asd_15:atom2.jpg?600|}}
-- residue seq number (per cross referenziare con strutture secondarie)
+Le strutture secondarie sono etichettate come HELIX e SHEET e i loro campi di interesse sono "serNum" (è il riferimento incrociato unico menzionato sopra), "initSeqNum" (identifica l'inizio della sequenza dei residui) e "endSeqNum" (identifica la fine della sequenza dei residui).
-I campi di interesse in ciascuna HELIX e ciascuno SHEET sono:
+{{:matematica:asd:asd_15:helixsheet.jpg?600|}}
--id
+Nota (a cura di A. Conte). Per chiarire la connessione tra i campi suddetti nelle strutture secondarie: resSeq è l'identificatore del residuo (amminoacido) a cui appartiene l'ATOM in questione. Una HELIX o uno SHEET coinvolgono un certo numero di residui consecutivi, che vanno appunto da initSeqNum fino a endSeqNum. Se nella colonna initSeqNum c'è un valore x e in endSeqNum c'è il valore y, tutti gli ATOM aventi "resSeq" con valore compreso tra x e y (inclusi) ne fanno parte.(Per inciso, gli atomi che non fanno parte di una HELIX o uno SHEET contribuiscono alla cosiddetta random coil.)
--start residue sequence number
--end residue sequence number
+Come menzionato sopra, utilizzando le informazioni sopra è possibile restringere gli isomorfismi, rendendo compatibili due vertici che corrispondono ad atomi che sono entrambi nello stesso tipo di struttura secondaria (HELIX o SHEET).
-Gli archi del grafo da costruire sono implicitamente definiti dalla seguente regola: due vertici hanno un legame se la loro distanza euclidea in angstrom è nell’intevallo
+Gli **archi** del grafo da costruire sono implicitamente definiti dalla seguente regola: due vertici hanno un legame se la loro distanza euclidea in angstrom è nell’intevallo
-[1 , 2] : legame covalente
+  * [1 , 2] : legame covalente
-(2 , 3.2] : legame non covalente
+  * (2 , 3.2] : legame non covalente
-(Meno di 1 è noise)
+  * altrimenti, l'arco non esiste (la distanza è inferiore a 1, che viene considerata rumore, oppure la distanza è superiore a 3.2 angstrom e le forze sono troppo deboli).
-Nota: in alcuni file PDB, la proteina può essere stata replicata più volte: in tal caso è sufficiente prendere soltanto la componente connessa a partire dal primo vertice ATOM
+Nota. In alcuni file PDB, la proteina può essere stata replicata più volte: in tal caso è sufficiente prendere soltanto la componente connessa a partire dal primo vertice ATOM