Algoritm Smith-Waterman

Algoritmul Smith-Waterman este un algoritm bioinformatic conceput pentru alinierea secvenței , adică determinarea gradului de asemănare (numit și omologie) a secvențelor de nucleotide sau proteine .

Descriere

Algoritmul a fost propus în 1981 de Temple F. Smith și Michael S. Waterman ^[1] . Algoritmul se bazează pe programare dinamică și este o variantă a algoritmului Needleman-Wunsch (propus cu câțiva ani mai devreme).

Algoritmul calculează distanța de editare între două secvențe în cazul alinierii locale . În cazul general, operațiunile disponibile sunt:

potrivire ( potrivire ) a două caractere egale
substituirea unui personaj într-un personaj diferit
inserarea (inserarea) unui caracter;
ștergerea unui personaj;

Pentru a calcula distanța de editare, trebuie prevăzută o schemă de cost adecvată. O schemă de cost comun este distanța Levenshtein (unde operațiunile de înlocuire, inserare și ștergere costă 1). O schemă mai generală poate fi utilizată furnizând o matrice a costurilor înlocuirilor și penalizărilor pentru lacune (care sunt consecința directă a inserțiilor și ștergerilor).

Algoritmul folosește o matrice ca structură de date și operează în două faze. În prima fază, se completează matricea și se obține scorul celei mai bune alinieri. În cea de-a doua fază se efectuează un backtracking pentru a recupera transformarea ( editarea șirului ) care permite efectuarea alinierii.

Algoritmul

Matricea $H.$ ${\ displaystyle H}$ $H.$ este construit după cum urmează:

$H(i,0)=0,\;0\leq i\leq m$ ${\ displaystyle H (i, 0) = 0, \; 0 \ leq i \ leq m}$ ${\ displaystyle H (i, 0) = 0, \; 0 \ leq i \ leq m}$

$H(0,j)=0,\;0\leq j\leq n$ ${\ displaystyle H (0, j) = 0, \; 0 \ leq j \ leq n}$ ${\ displaystyle H (0, j) = 0, \; 0 \ leq j \ leq n}$

${\text{ Se }}a_{i}=b_{j}$ ${\ displaystyle {\ text {Se}} a_ {i} = b_ {j}}$ ${\ displaystyle {\ text {Se}} a_ {i} = b_ {j}}$ $w(a_{i},b_{j})=w{\text{(Match)}}$ ${\ displaystyle w (a_ {i}, b_ {j}) = w {\ text {(Match)}}}$ ${\ displaystyle w (a_ {i}, b_ {j}) = w {\ text {(Match)}}}$ ${\text{ o se }}a_{i}!=b_{j}$ ${\ displaystyle {\ text {o se}} a_ {i}! = b_ {j}}$ ${\ displaystyle {\ text {o se}} a_ {i}! = b_ {j}}$ $w(a_{i},b_{j})=w{\text{(Substitution)}}$ ${\ displaystyle w (a_ {i}, b_ {j}) = w {\ text {(Înlocuire)}}}$ ${\ displaystyle w (a_ {i}, b_ {j}) = w {\ text {(Înlocuire)}}}$

$H(i,j)=\max {\begin{Bmatrix}0\\H(i-1,j-1)+\ w(a_{i},b_{j})&{\text{Match/Substitution}}\\H(i-1,j)+\ w(a_{i},-)&{\text{Deletion}}\\H(i,j-1)+\ w(-,b_{j})&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$ ${\ displaystyle H (i, j) = \ max {\ begin {Bmatrix} 0 \\ H (i-1, j-1) + \ w (a_ {i}, b_ {j}) și {\ text { Potrivire / Înlocuire}} \\ H (i-1, j) + \ w (a_ {i}, -) & {\ text {Ștergere}} \\ H (i, j-1) + \ w (-, b_ {j}) & {\ text {Insertion}} \ end {Bmatrix}}, \; 1 \ leq i \ leq m, 1 \ leq j \ leq n}$ ${\ displaystyle H (i, j) = \ max {\ begin {Bmatrix} 0 \\ H (i-1, j-1) + \ w (a_ {i}, b_ {j}) și {\ text { Potrivire / Înlocuire}} \\ H (i-1, j) + \ w (a_ {i}, -) & {\ text {Ștergere}} \\ H (i, j-1) + \ w (-, b_ {j}) & {\ text {Insertion}} \ end {Bmatrix}}, \; 1 \ leq i \ leq m, 1 \ leq j \ leq n}$

Unde este:

$la, b$ ${\ displaystyle a, b}$ $a, b$ = Sunt cele două șiruri din alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$
$m={\text{length}}(a)$ ${\ displaystyle m = {\ text {length}} (a)}$ ${\ displaystyle m = {\ text {length}} (a)}$
$n={\text{length}}(b)$ ${\ displaystyle n = {\ text {length}} (b)}$ ${\ displaystyle n = {\ text {length}} (b)}$
$H(i,j)$ ${\ displaystyle H (i, j)}$ ${\ displaystyle H (i, j)}$ - este scorul de similaritate maxim între sufixul lui a [1 ... i] și sufixul lui b [1 ... j]
$w(c,d),\;c,d\in \Sigma \cup \{'-'\}$ ${\ displaystyle w (c, d), \; c, d \ in \ Sigma \ cup \ {'-' \}}$ ${\ displaystyle w (c, d), \; c, d \ in \ Sigma \ cup \ {'-' \}}$ , '-' este schema de scoruri de penalizare / decalaj