Il progetto si basa su file presi dal 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 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 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 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 comuqnue risolto con 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 …..

Una breve presentazione (del dott. Lorenzo Tattini) è disponibile tramite questo link. 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:

- id - 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:

- residue seq number (per cross referenziare con strutture secondarie)

I campi di interesse in ciascuna HELIX e ciascuno SHEET sono:

-id -start residue sequence number -end residue sequence number

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)

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