La Bioinformatica è una disciplina scientifica dedicata alla risoluzione di problemi biologici con metodi informatici; le attività di base della Bioinformatica comprendono il retrieval delle informazioni all' interno di databases biologici, il confronto fra sequenze genomiche e la rappresentazione delle strutture proteiche. Prima di analizzare le tecniche di allineamento fra sequenze proteiche, volevo ricordare come quest' ultime siano composte dai 20 tipi di amminoacidi presenti in natura; una proteina sarà quindi composta da una particolare sequenza di amminoacidi come nel caso dell' insulina (prima proteina scoperta nel '51)
insulina = MALWMRLLPLLALLALWGPDPAAAFVNQHLCGSHLVEALYLVCGERG
FFYTPKTRREAEDLQVGQVELGGGPGAGSLQPLALEGSLQKRGIVEQCCTSICSLY
QLENYCN
Ogni giorno all' interno dei laboratori di tutto il mondo vengono scoperte nuove sequenze biologiche; queste sequenze vengono analizzate al fine di effettuarne una classificazione basata sulla funzione biologica che la sequenza ricopre. La Bioinformatica offre quindi ai ricercatori uno strumento che permetta loro di eseguire una classificazione funzionale in modo automatico, ponendo su quest' ultima un elevato grado di fiducia. Biologicamente si può osservare come due sequenze proteiche che derivino da un ancestor comune (sequenze omologhe) condividano delle interessanti similarità strutturali e funzionali presentando purtroppo sequenze con basso grado di similarità. L' allineamento di sequenze proteiche (pairwise alignment)permette quindi di riuscire ad evidenziare quelle regioni che possono condividere interessanti similarità; si possono produrre due tipologie di allineamento, uno globale che prevede l'allineamento delle sequenze secondo la loro intera lunghezza, ed uno locale che non richiede che il confronto delle due sequenze sia svolto per l' intera lunghezza delle sequenze (biologicamente sono più rilevanti gli allineamenti locali). Date due sequenze proteiche x e y, un allineamento locale fra le due sequenze viene definito come:
All' allineamento locale sopra mostrato possiamo definire uno score in modo da ricercare fra le coppie di sequenze proteiche l' allineamento che massimizzi lo score (condizione di ottimalità). Possiamo quindi definire, riferendoci alle sequenze sopra esposte, la formula per il calcolo dello score come:
s(x, y)= s(E,E) + s(F,E) + s(G,G) + s(I, I) − s(gaps)
La formula ci dice che lo score ottenuto fra x e y è dato dalla somma degli score ottenuta dall' allineamento dei singoli residui (aminoacidi) a cui vanno sottratti gli score negativi attribuiti ai gap (buchi) presenti nella regione allineata (quella in rosso).Lo score fra due residui, ad esempio s(F,E), viene attribuito in base a delle matrici (dette matrici di sostituzione), in cui viene assegnato un punteggio ad ogni coppia di amminoacidi (matrici quindi 20x20 ).
Da un punto di vista informatico (che maggiormente ci interessa 
), quale algoritmo utilizzereste per allineare localmente due sequenze proteiche? Una possibile soluzione è quella di eseguire un allineamento brute-force ottenendo una complessità esponenziale al crescere della lunghezza della coppia di sequenze... come al solito quindi un approccio brute-force mal si adatta a situazioni reali. Gli algoritmi che ben si prestano alla risoluzione di problemi di sequence analysis utilizzano tecniche di programmazione dinamica; come il metodo divide et impera, la programmazione dinamica (DP) risolve problemi mettendo insieme le soluzioni di un certo numero di sottoproblemi. A differenza del dividi et impera, i sottoproblemi da risolvere non sono necessariamente
disgiunti (vale a dire: uno stesso sottoproblema pu`o essere comune a diversi sottoproblemi). Onde evitare di ricalcolare più volte la soluzione di uno stesso sottoproblema, i sottoproblemi vengono risolti con una strategia bottom-up. Il processo di sviluppo di un algoritmo di DP è composto da tre fasi:
- definizione di un metodo ricorsivo per il calcolo del valore di una soluzione ottima
- calcolo del valore di una soluzione ottima secondo uno schema bottom-up (dal basso verso l’alto)
- costruzione della soluzione ottima dalle informazioni raccolte nella frase precedente (traceback)
Analizziamo intituivamente come procede l' algoritmo sopra illustato, riferendoci all'implementazione di Smith-Waterman (algoritmo di allineamento locale ottimo tra coppia di sequenze) per passare successivamente alla definizione formale del problema in termini ricorsivi; supponiamo di avere due stringe ( sequenze di aminoacidi ), x e y aventi valore rispettivamente TFDERILGVQ e QTFWECIKGD; illustriamo graficamente come operi il l' algoritmo di Smith-Waterman:
Nella prima fase dell' algoritmo per ogni coppia di simboli presenti nelle strighe x ed y viene assegnato uno score basato su di una matrice di scoring; le matrici di scoring assegnano score ai vari accoppiamenti tenendo conto di informazioni biologiche accumulate nel corso degli anni. Illustriamo adesso la seconda fase dell' algoritmo quella in cui lo spazio di ricerca tra le possibili combinazioni viene ristretto assumendo solo tre possibili path percorribili:
Come possiamo vedere per ogni cella della nostra matrice vengono calcolati tre valori: un valore dato dalla somma degli score ottenuti sul path diagonale (caso in cui sto allineando un residuo di x con un residuo su y), un valore dato dalla somma ottenuta sul path orizzontale (caso in cui allineo un gap di x con un residuo di y) ed un valore dato dalla somma ottenuta sul path verticale (caso in cui allineo un gap di y con un residuo di x). Calcolati questi tre valori viene memorizzato solo il valore massimo. Memorizzato il valore per ogni possibile cella si passa alla fase di back-tracing, in cui in modo bottom up risalgo all' allineamento locale ottimo:
Come si vede in figura viene scelto il valore massimo risalendo verso l'origine selezionando il valore massimo sulle tre possibile scelte che si incontrano ad ogni passo. L' ottimalità della soluzione viene proprio garantita dalla massimizzazione che viene fatta sulla scelta dei valori ad ogni singola iterazione. L' algoritmo di Smith-Waterman appena proposto abbassa la complessità di computazione ad una soglia quadratica. Definiamo in fine le formule di ricorrenza che descrivono il processo sopra illustrato:
Dopo tutta questa fatica non ci resta che procedere con un pò di codice.... fortunatamente esiste il solito porting di una libreria java che ci offre già un' implementazione dell' algoritmo di Smith-Waterman, ottimizzato seguendo le direttive indicate da Gotoh. Analizzando il diagramma delle classi riportato di seguito possiamo vedere come siano stati rappresentati ottimamente tutti i concetti sopra esposti.
Questo post nasce in seguito all' elaborato che ho svolto per il superamento dell' esame di Apprendimento Automatico. Per chi volesse approfondire gli argomenti sopra esposti, consiglio la lettura del paper di Hiroto Saigo e Vert all' interno del quale l' algoritmo di Smith Waterman sopra esposto viene modificato per essere utilizzato come kernel valido da utilizzare con SVM. Se siete interessati alla bioinformatica posso spiegare in un altro post il funzionamento di altri algoritmi ad esempio quelli euristici, quali BLAST o FASTA... fatemi sapere
Vox populi, vox dei