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 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 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 questo link.
• Un estratto della documentazione sul formato dei file presi da PDB è disponibile tramite questo link.

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).

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).

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).

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.)

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).

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

• [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.

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.