Algoritme Smith-Waterman

L'algoritme de Smith-Waterman és una reconeguda estratègia per a realisar alineament local de seqüències biològiques (ADN, ARN o proteïnes); és dir que determina regions similars entre un parell de seqüències.
L'algoritme SW va ser propost per Temple Smith i Michael Waterman en 1981.[1] Està basat en l'ús d'algoritmes de programació dinàmica, de tal forma que té la desijable propietat de garantisar que el alineament local trobat és òptim sobre un determinat sistema de puntajes que s'use (tals com a matrius de substitució).
Les alternatives bàsiques per a realisar el alineament d'un parell de seqüències són: el alineament local i l'alineament global.
Els allineaments globals pretenen alinear cada símbol (o residu) en cada seqüència. Esta estratègia és especialment útil quan les seqüències a alinear són altament similars i aproximadament del mateix tamany. En contrast, els allineaments locals són més útils quan les seqüències a alinear posseïxen grans diferències, pero se sospita que existixen regions de similitut.
Algoritme
Siguen i les dos seqüències biològiques a alinear, les llongituts de les quals són i respectivament. La puntuació de similitut entre dos elements i està donada per . A cada eliminació de llongitut se li assigna una penalisació .
Per a trobar un parell de segments en una gran similitut, es construïx una matriu de ×, inicializando la primera columna i primer fila en valors de .
- .
- Cada valor representa la màxima similitut entre dos segments que terminen en i respectivament. Dits valors s'obtenen de la següent relació de recurrència:
- a on
- és la puntuació d'alinear i ,
- és la puntuació si es troba al final d'una eliminació de llongitut ,
- és la puntuació si es troba al final d'una eliminació de llongitut ,
- indica que no existix alguna similitut entre i , s'afig este valor per a evitar valors negatius.
- Per a recuperar el parell de segments en màxima similitut, es porta a terme un rastreig revers a partir del màxim element de fins a terminar en un element el valor del qual siga igual a , sent est l'inici de l'alineació local òptima.
Complexitat algorítmica
L'algoritme de Smith-Waterman té una complexitat temporal de i una complexitat espacial de . Açò representa una disminució considerable del cost computacional sobre l'enfocament de força bruta, que té un temps d'eixecució de degut a que existixen i subsecuencias de i respectivament. No obstant, la seua complexitat representa una desventaja en comparació a la de l'algoritme de Needleman-Wunsch,[2] que té una complexitat llineal. Especialment quan el valor de és molt gran. És per això que es varen desenrollar alternatives en un temps d'eixecució llineal[3][4] i uns atres en complexitat espacial llineal sobre .[5]
Eixemple
Siguen :AAGGCT i :AACCCG les dos seqüències a alinear en una puntuació de similitut està donada per la següent relació:
.
La matriu de puntuació es inicializa en per a tots els elements de la primera columna i la primera fila. Despuix es calculen totes les puntuaciónes entre i , començant per i , denotat en groc en la següent matriu.
| A !
scope="col" style="width:18px;" | A ! scope="col" style="width:18px;" | C |
C | C | G | ||||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A |
0 || style = "background: yellow;"| 1 || || || || || | |||||||
| A |
0 || || || || || || | |||||||
| G | 0 | ||||||
| G | 0 | ||||||
| C | 0 | ||||||
| T | 0 |
Una volta calculats tots els valors es busca l'element en la màxima puntuació, denotat en vert.
| A !
scope="col" style="width:18px;" | A ! scope="col" style="width:18px;" | C |
C | C | G | ||||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A |
0 || 1 || 1 || 0||0 ||0 ||0 | |||||||
| A |
0 ||1 || style = "background: green;"|2|| 1|| 0|| 0||0 | |||||||
| G | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| C | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| T | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Finalment, per a recuperar l'alineació local òptima de i es porta a terme un rastreig a partir d'eixe element fins a aplegar a un element en valor de .
| A !
scope="col" style="width:18px;" | A ! scope="col" style="width:18px;" | C |
C | C | G | ||||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A |
0 || style = "background: green;"|1 || 1 || 0||0 ||0 ||0 | |||||||
| A |
0 ||1 || style = "background: green;"|2|| 1|| 0|| 0||0 | |||||||
| G | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| C | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| T | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
L'alineació resultant d'este eixemple consistix en alinear únicament els primers dos elements de cada seqüència.
AA || AA
Penalisació per buits
Penalisació llineal
la penalisació per buits servix per a determinar la puntuació d'un indel, és dir, una inserció o una eliminació. L'algoritme de Smith-Waterman ampra una penalisació llineal per estendre la llongitut d'un buit, a on la penalizacion depén únicament de la llongitut del buit i del cost d'un buit d'un sol espai : .
Buits afins
Gotoh va propondre un model de buits afins, que consistix en modificar la penalizacion per a que esta siga funció de dos paràmetros: , a on és la penalisació per estendre un buit, és la penalisació per iniciar un buit i és la llongitut del buit. Este esquema es reduïx a la penalisació llineal quan . Este model oferix dos ventages: reduir el número d'operacions a i permetre que s'assigne un cost més alt per iniciar un buit que per estendre-ho. L'última propietat té importants implicaciónes biològiques ya que una simple mutació pot ocasionar varis canvis en un segment d'una seqüència, per lo tant la creació d'un buit sol tindre major impacte que la seua llongitut. La disminució en el cost computacional de l'algoritme de Gotoh es deu a que est intenta trobar solament una de les alineaciónes locals òptimes i no garantisa trobar alguna, a diferència de Smith-Waterman que busca trobar totes per lo que sempre troba l'alineació òptima.
L'algoritme de Gotoh ampra tres matrius de :
- : puntuació per alinear i ,
- : puntuació per alinear en un buit,
- : puntuació per alinear en un buit
Estes matrius tenen la següent inicialisació:
- ,
- ,
- ,
Els valors d'estes matrius s'obtenen de les següents relacions de recurrència:
Buits convexos
Waterman[6] va propondre un atre sistema de penalisació encara més flexible. A diferència del model de buits afins a on els costs d'iniciar i estendre un buit són constants, i respectivament, en la penalisació de buits convexos el cost d'estendre el buit disminuïx a mida que aumenta la seua llongitut: .
Referències
- ↑ Smith TF, Waterman MS(1981).«Identification of common molecular subsequences.».J Mol Biol..147(1): 195-7.[1]
- ↑ (1970).«A general method applicable to the search for similarities in the amino acid sequence of two proteins».Journal of Molecular Biology.48(3): 443–453.doi:10.1016/0022-2836(70)90057-4.
- ↑ Osamu Gotoh(1982).«An improved algorithm for matching biological sequences».Journal of Molecular Biology.162(3): 705–708.doi:10.1016/0022-2836(82)90398-9.«10.1.1.204.203»
- ↑ (1986).«Optimal sequence alignment using affine gap costs».Bulletin of Mathematical Biology.48(5–6): 603–616.doi:10.1007/BF02462326.
- ↑ (1988).«Optimal alignments in linear space».Bioinformatics.4(1): 11–17.doi:10.1093/bioinformatics/4.1.11.«10.1.1.107.6989»
- ↑ (1984).«Efficient Sequence Alignment Algorithms».Journal of Theoretical Biology.108: 333-337.doi:10.1016/s0022-5193(84)80037-5.
- Este artícul conté una traducció derivada de «Algoritmo Smith-Waterman» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.