| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| matematica:asd:asd_15:progetto_15 [16/05/2016 alle 06:51 (9 anni fa)] – Roberto Grossi | matematica:asd:asd_15:progetto_15 [16/05/2016 alle 19:40 (9 anni fa)] (versione attuale) – Roberto Grossi |
|---|
| 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. | 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 la dimensione (numero di vertici) del 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. | Il progetto richiede di trovare la dimensione (numero di vertici) del 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 scoprire 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 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. | * 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 il SICC massimo contiene almeno 144 vertici per ''1ald'' vs ''1fcb'', ma il progetto ammette che uno possa trovarne uno più piccolo di 144. |
| * Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite {{:matematica:asd:asd_15:lorenzotattinislides.pdf|questo link}}. | * 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}}. | * Un estratto della documentazione sul formato dei file presi da PDB è disponibile tramite {{:matematica:asd:asd_15:estrattodocpdb.pdf|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). | Il grafo va costruito a partire da un file di testo 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). |
| |
| {{:matematica:asd:asd_15:atom.jpg?600|}} | {{:matematica:asd:asd_15:atom.jpg?600|}} |
| |
| 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 è "residue seq number" (riferimento incrociato alla rispettiva strutture secondaria). | 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 struttura secondaria). |
| |
| {{:matematica:asd:asd_15:atom2.jpg?600|}} | {{:matematica:asd:asd_15:atom2.jpg?600|}} |
| |
| 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 l'inizio della sequenza dei residui). | 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). |
| |
| {{:matematica:asd:asd_15:helixsheet.jpg?600|}} | {{:matematica:asd:asd_15:helixsheet.jpg?600|}} |
| |
| | 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.) |
| |
| 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 | Come menzionato prima, 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). |
| * [1 , 2] : legame covalente | |
| * (2 , 3.2] : legame non covalente | 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’intervallo |
| * l'arco non esiste se la distanza è inferiore a 1, che viene considerata rumore, oppure se la distanza è superiore a 3.2 angstrom. | * [1 ... 2] : legame covalente; |
| | * (2 ... 3,2] : legame non covalente; |
| | * 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. |
| | |
| | Suggerimento. Ogni volta che viene trovato un SICC più grande, conviene stamparne subito la dimensione, in modo che il programma possa essere interrotto dopo un'ora senza perdere l'informazione calcolata fino a quel momento. |
