Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisione Revisione precedente Prossima revisione | Revisione precedente | ||
matematica:asd:asd_15:vuoto [16/05/2016 alle 05:19 (8 anni fa)] Roberto Grossi |
matematica:asd:asd_15:vuoto [16/05/2016 alle 13:36 (8 anni fa)] (versione attuale) Roberto Grossi |
||
---|---|---|---|
Linea 1: | Linea 1: | ||
====== Progetto di ASD 2015/2016 ====== | ====== Progetto di ASD 2015/2016 ====== | ||
- | Il progetto si basa su file presi dal [[http:// | + | Il progetto si basa su file presi dal [[http:// |
- | 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 |
- | 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, | + | 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 |
- | Il progetto richiedere di trovare il sottografo indotto connesso comune | + | Il progetto richiedere di trovare il SICC più grande possibile in due grafi etichettati, |
- | Tre proteine prese da PDB sono disponibili | + | * Tre proteine, prese da PDB e denominate '' |
+ | * Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite {{: | ||
+ | * Un estratto della documentazione sul formato dei file presi da PDB è disponibile tramite {{: | ||
- | Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite questo link. | + | Il grafo va costruito |
- | 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: |
- | - id | + | Volendo, si possono utilizzare altre informazioni per tagliare via gli isomorfismi meno interessanti, |
- | - x , y , z (coordinate cartesiane in angstrom) | + | |
- | - element name | + | |
- | Volendo, si possono utilizzare altre informazioni per tagliare via gli isomorfismi meno interessanti, | + | {{:matematica: |
- | - residue seq number (per cross referenziare con strutture secondarie) | + | Le strutture secondarie |
- | I campi di interesse in ciascuna HELIX e ciascuno SHEET sono: | + | {{:matematica: |
- | -id | + | Nota (a cura di A. Conte). Per chiarire la connessione tra i campi suddetti nelle strutture secondarie: resSeq è l' |
- | -start residue sequence number | + | |
- | -end residue sequence number | + | |
+ | Come menzionato sopra, utilizzando le informazioni sopra è possibile restringere gli isomorfismi, | ||
- | 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 | + | |
- | (2 , 3.2] : legame non covalente | + | |
- | (Meno di 1 è noise) | + | * altrimenti, l'arco non esiste |
- | + | ||
- | 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 |