Date due sequenze biologiche e
, e una funzione
che ci calcola la loro distanza (compreso il costo del gap),
i problemi che vogliamo risolvere sono
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:
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
in
.
Come si può notare applicando le operazioni inverse (
,
e
) si può trasformare
la sequenza
in
.
Per cui possiamo definire:
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
, e cancellare l'intera sequenza
, poi applicare l'operatore
di inserimento
, fino a creare la sequanza
, 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