Algoritme Smith-Waterman
El algoritme de Smith-Waterman és una reconeguda estratègia per a realisar alineamiento 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'us d'algoritmes de programació dinàmica, de tal forma que té la desijable propietat de garantisar que el alineamiento 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 alineamiento d'un parell de seqüències són: el alineamiento local i l'alineamiento global.
Els alineamientos 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 alineamientos 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
[editar | editar còdic]Sean ___MATH_0___ i ___MATH_1___ les dos seqüències biològiques a alinear, les llongituts de les quals són ___MATH_2___ i ___MATH_3___ respectivament. La puntuació de similitut entre dos elements ___MATH_4___ i ___MATH_5___ està donada per ___MATH_6___. A cada eliminació de llongitut ___MATH_7___ se li assigna una penalisació ___MATH_8___.
- Per a trobar un parell de segments en una gran similitut, es construïx una matriu ___MATH_9___ de ___MATH_10___×___MATH_11___, inicializando la primera columna i primer fila en valors de ___MATH_12___.
- ___MATH_13___.
- Cada valor ___MATH_14___ representa la màxima similitut entre dos segments que terminen en ___MATH_15___ i ___MATH_16___ respectivament. Dits valors s'obtenen de la següent relació de recurrencia:
- ___MATH_17___
- a on
- ___MATH_18___ és la puntuació d'alinear ___MATH_19___ i ___MATH_20___,
- ___MATH_21___ és la puntuació si ___MATH_22___ es troba al final d'una eliminació de llongitut ___MATH_23___,
- ___MATH_24___ és la puntuació si ___MATH_25___ es troba al final d'una eliminació de llongitut ___MATH_26___,
- ___MATH_27___ indica que no existix alguna similitut entre ___MATH_28___ i ___MATH_29___, 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 ___MATH_30___ fins a terminar en un element el valor del qual siga igual a ___MATH_31___, sent est l'inici de l'alliniació local òptima.
Complexitat algorítmica
[editar | editar còdic]L'algoritme de Smith-Waterman té una complexitat temporal de ___MATH_32___ i una complexitat espacial de ___MATH_33___. Açò representa una disminució considerable del cost computacional sobre l'enfocament de força bruta, que té un temps d'eixecució de ___MATH_34___ degut a que existixen ___MATH_35___ i ___MATH_36___subsecuencias de ___MATH_37___ i ___MATH_38___ 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 ___MATH_39___ é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 ___MATH_40___ .[5]
Eixemple
[editar | editar còdic]Sean ___MATH_41___:AAGGCT i ___MATH_42___:AACCCG les dos seqüències a alinear en una puntuació de similitut està donada per la següent relació:
___MATH_43___.
La matriu de puntuació es inicializa en ___MATH_44___ per a tots els elements de la primera columna i la primera fila. Despuix es calculen totes les puntuaciónes entre ___MATH_45___ i ___MATH_46___ , començant per ___MATH_47___ i ___MATH_48___, 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'alliniació local òptima de ___MATH_49___ i ___MATH_50___ es porta a terme un rastreig a partir d'eixe element fins a aplegar a un element en valor de ___MATH_51___.
| 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'alliniació resultant d'este eixemple consistix en alinear únicament els primers dos elements de cada seqüència.
AA || AA
Penalisació per buits
[editar | editar còdic]Penalisació llineal
[editar | editar còdic]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 ___MATH_52___ depén únicament de la llongitut ___MATH_53___ del buit i del cost ___MATH_54___d'un buit d'un sol espai : ___MATH_55___.
Buits afins
[editar | editar còdic]Gotoh va propondre un model de buits afins, que consistix en modificar la penalizacion ___MATH_56___ per a que esta siga funció de dos paràmetros: ___MATH_57___, a on ___MATH_58___ és la penalisació per estendre un buit, ___MATH_59___ és la penalisació per iniciar un buit i ___MATH_60___ és la llongitut del buit. Este esquema es reduïx a la penalisació llineal quan ___MATH_61___. Este model oferix dos ventages: reduir el número d'operacions a ___MATH_62___ 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'alliniació òptima.
L'algoritme de Gotoh ampra tres matrius de ___MATH_63___:
- ___MATH_64___: puntuació per alinear ___MATH_65___ i ___MATH_66___,
- ___MATH_67___: puntuació per alinear ___MATH_68___ en un buit,
- ___MATH_69___: puntuació per alinear ___MATH_70___ en un buit
Estes matrius tenen la següent inicialización:
- ___MATH_71___,
- ___MATH_72___,
- ___MATH_73___,
- ___MATH_74___
Els valors d'estes matrius s'obtenen de les següents relacions de recurrencia:
- ___MATH_75___
- ___MATH_76___
- ___MATH_77___
Buits convexos
[editar | editar còdic]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, ___MATH_78___ i ___MATH_79___ respectivament, en la penalisació de buits convexos el cost d'estendre el buit disminuïx a mida que aumenta la seua llongitut: ___MATH_80___.
Referències
[editar | editar còdic]- ↑ Smith TF, Waterman MS(1981).147(1)
- 195-7.[1]
- ↑ “A general method applicable to the search for similarities in the amino acid sequence of two proteins” (1970). Journal of Molecular Biology 48 (3): 443–453. doi:. PMID 5420325.
- ↑ Osamu Gotoh (1982). “An improved algorithm for matching biological sequences”. Journal of Molecular Biology 162 (3): 705–708. doi:. PMID 7166760.
- ↑ “Optimal sequence alignment using affine gap costs” (1986). Bulletin of Mathematical Biology 48 (5–6): 603–616. doi:. PMID 3580642.
- ↑ “Optimal alignments in linear space” (1988). Bioinformatics 4 (1): 11–17. doi:. PMID 3382986.
- ↑ “Efficient Sequence Alignment Algorithms” (1984). Journal of Theoretical Biology 108: 333-337. doi:.
- 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.