L’algoritmo di Needleman-Wunsch

Allineamento di proteine

Cercare similitudini fra sequenze di peptidi è estremamente utile per stabilire rapporti evolutivi fra proteine (e quindi fra gli esseri viventi che le sintetizzano), per progettare vaccini, per studiare fenomeni di autoimmunità e altro. In questo post presento un software che si occupa proprio del confronto fra due sequenze proteiche. La scrittura di questo programma mi ha tenuto compagnia durante molti mesi, segnandomi la rotta fra le costanti ricadute e riacutizzazioni della mia malattia, malattia che fin’ora non mi ha ancora abbandonato per un solo giorno. Mentre scrivevo questo e altri codici, che ne sono lo sviluppo, inventavo anche un modo per aspettare il domani.

Needleman e Wunsch

L’algoritmo di Needleman-Wunsch descrive un procedimento automatico che consente di calcolare il migliore allineamento possibile fra due sequenze di amminoacidi (Needleman SB, Wunsch CD, 1969). Questo metodo permette di svolgere in modo relativamente veloce e ingegnoso il confronto fra tutti gli allineamenti fra le due sequenze, considerando ogni possibile numero di lacune, in ogni possibile posizione. Il suo scopo è quello di scegliere fra questi allineamenti il migliore, ovvero quello che garantisce il ‘punteggio’ più alto, essendo tale punteggio calcolato utilizzando delle matrici quadrate di dimensione 20, dette ‘matrici di sostituzione’. Questo compito è non banale e comporta l’esame di un numero di allineamenti pari a

dove k e m sono le lunghezze dei due peptidi. Si tratta di numeri molto elevati, infatti posto ad esempio k=4 e m=6, si ottengono circa 215 allineamenti diversi. In genere però si ha a che fare con peptidi di centinaia di amminoacidi, il che comporta milioni di possibili allineamenti tra cui cercare il migliore. Ebbene, l’algoritmo di Needleman e Wunsch permette di effettuare questa analisi senza dover considerare direttamente ogni allineamento possibile. In figura 2 e 3 si ha una descrizione grafica di questo algoritmo.

Il mio programma

Il mio software per l’allineamento globale fra due proteine si chiama NeW_6 ed è scritto in Octave. Il programma presenta la stessa funzionalità di due analoghi prodotti di largo impiego, che sono LALIGN dello Swiss Institute of Bioniformatics e EMBOSS Needle dell’Europen Bioinformatic Institute. In particolare il mio programma ha le seguenti caratteristiche:

• permette all’utente di scegliere fra un set di comuni matrici di sostituzione;
• ha un modello di lacuna del tipo a+b(x), dove a è la penalità della lacuna iniziale, b quella delle lacune di estensione e x è il numero di lacune;
• prevede lacune alla fine delle sequenze.

Lo sviluppo del programma, nonché il codice, si trovano in questo PDF, dove è possibile seguire vari esempi applicativi e varie versioni del programma stesso, nonché dei test in cui ne confronto l’output con i programmi attualmente in uso.

Applicazioni

Perché scrivere un programma che esiste già? Mi è servito per penetrare i metodi di allineamento fra due sequenze di amminoacidi, ma soprattutto mi ha permesso di costruire programmi più complessi (non inclusi nel PDF di cui sopra) che sto attualmente utilizzando per risolvere problemi di immunologia.

In cerca di una soluzione.