Entrambe le parti precedenti la revisione
Revisione precedente
Prossima revisione
|
Revisione precedente
|
matematica:asd:asd_15:vuoto [16/05/2016 alle 06:10 (8 anni fa)] Roberto Grossi |
matematica:asd:asd_15:vuoto [16/05/2016 alle 13:36 (8 anni fa)] (versione attuale) Roberto Grossi |
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. | 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 "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?200|}} | 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). |
| |
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). | {{:matematica:asd:asd_15:atom2.jpg?600|}} |
| |
fig | 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). |
| |
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). | {{: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.) |
| |
fig | 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 |