Allineamento tra due sequenze

Date due sequenze biologiche $s$ e $t$, e una funzione che ci calcola la loro distanza (compreso il costo del gap), i problemi che vogliamo risolvere sono

• calcolare il valore della loro distanza (minima)
• determinare un allineamento ottimo con tale distanza

Da un punto di vista biologico, durante l'evoluzione possono essere intervenuti vari processi che hanno fatto divergere le due sequenze. Di tutte le possibilità noi terremo in considerazione solo quelle puntiformi (per casi più generali, come repeats, o genome re-arangments, vedere [5],[4], [7], [9] e [11]). In particolare le seguenti:

• deletion: cancellazione di un amminoacido (o base)
• insert: inserimento di un amminoacido (o base)
• match/mismatch: conservazione/sostituzione di un amminoacido (o base)

A questi eventi noi associamo le operazioni corrispondenti

• deletion: $D(a,-)$
• insert: $I(-,b)$
• match/mismatch: $M(a,b)$

Queste operazioni si possono anche vedere come operazioni che servono per trasformare la prima sequenza nella seconda. Ovviamente vogliamo che la cosa sia simmetrica, e che si possa trasformare la seconda sequenza nella prima utilizzando le operazioni inverse. Siccome queste operazioni agiscono sulla sequenza, sono anche chiamate operazioni di editing. Come esempio consideriamo la Tabella , dove si mostra un modo possibile in cui applicando le operazioni di editing M, D, M, M, I, M, M, e M, si possa trasformare ls sequenza $s$ in $t$. Come si può notare applicando le operazioni inverse ( $I \leftarrow D$, $D \leftarrow I$ e $M(a,b) \leftarrow M(b,a)$) si può trasformare la sequenza $t$ in $s$. Per cui possiamo definire:

• costo di un allineamento di $s$ e $t$ è la somma dei costi di tutte le operazioni necessarie a trasformare $s$ in $t$.

Tabella: Esempio delle operazioni di "editing"

Si può notare che esistono un numero elevatissimo di modi in cui si può trasformare una sequenza in un'altra, utilizzando le operazioni di editing. Possiamo per esempio applicare l'operatore di cancellazione $D$, e cancellare l'intera sequenza $s$, poi applicare l'operatore di inserimento $I$, fino a creare la sequanza $t$, come

       Edit operation : DDDDDDDIIIIIII
                    s : AGCAGTA-------
                    t : -------ACACCTA
       Gap cost = 1   : 11111111111111 = 14 = (len(s)+len(t))

Come si può notare, ad ogni insieme di operazioni corrisponde un costo ed un allineamento corrispondente. Si può inoltre dimostrare che il numero di possibili allineamenti tra due sequenze $s$ e $t$ le cui lunghezze sono circa uguali ad $n$ è maggiore di $e^n$. Per cui dato il numero elevato di possibili allineamenti, il problema che si vuole risolvere è quello di trovare un allineamento ottimo, dove definiamo

• Allineamento ottimo (BA) di s e t, è uno degli allineamenti che ha il minimo costo $C(BA)$