PÀGINA DE SUPORT




    Al 1970, Needleman i Wunsch van desenvolupar un algorisme basat en la tècnica de programació dinàmica per obtenir (originalment, ara s'ha modificat per altres objectius) un aliniament global de seqüències; la programació dinàmica es basa en resoldre els problemes basant-se en la resolució del problema anterior.

L'equació:

Si,j = màxim entre:
  • Si-1, j-1 + S(i,j)
  • Si-1, j + gap
  • Si, j-1 + gap

és una equació de recurrència que ens permet calcular la puntuació de l'aliniament òptim entre dues seqüències, a partir de les puntuacions dels aliniaments òptims entre subseqüències més petites: ens permet calcular de manera recursiva les puntuacions dels aliniaments òptims entre tots els parells de subseqüències de les seqüències originals.
Aquest càlcul recursiu es fa amb una matriu on en la casella (i,j) enregistrem la puntuació de l'aliniament òptim entre la subseqüència que acaba en la posició 'i' de la primera seqüència i en la posició 'j' de la segona.
Aquesta puntuació depèn de l'esquema de puntuacions extret d'una matriu de substitució, així com de la puntuació que li assignem a l'aliniament d'un simbol amb gap. En aquesta matriu, la primera fila i columna són "extres" a les seqüències, per poder introduir gaps inicials, i corresponen a la "inicialització de la matriu".

Amb aquest algorisme de programació dinàmica hem de fer només tres càlculs per omplir cada casella de l'aliniament, es a dir, n x m x 3 per omplir tota la matriu, i aquest és un número d'operacions molt més petit que el numero d'operacions necessaries per construir tots els aliniaments possibles entre les dues seqüències.

Per acabar obtenint l'aliniament òptim segons l'algorisme de Needleman i Wunsch, només queda desfer el camí des de la casella inferior dreta de la matriu seguint les direccions de les quals hem anat venint en cada posició. Podem trobar varis aliniaments igualment òptims, però cal recordar que l'aliniament òptim sempre dependrà de la matriu de substitució que fem servir en cada cas.

    Són fitxers dels quals el seu nom sol tenir extensió fa. Aquests format s'utilitza per enregistrar seqüències. Cada seqüència va precedida d'una línia que comença amb el símbol '>' i segueix d'una paraula que identificarà la seqüència. Aquesta paraula és l'identificador, que en la sortida del programa utilitzarem per indicar de quina seqüència es tracta.

    Les matrius de substitució són matrius en les que es representen les probabilitats de que un aminoàcid determinat canvïi a un altre segons diferents criteris, com poden ser:

  •  Observació que en proteïnes amb la mateixa funció el canvi es dóna: seria un criteri basat en l'evolució:
  •  Segons propietats fisico-químiques dels aminoàcids que s'intercanvien.

    Aquestes matrius les farem servir per fer aliniaments de seqüències, ja que ens interessarà tenir en compte les substitucions que no ens alteren la funció. Per això, si "s'accepta" el canvi segons els criteris abans mencionats, es donarà una puntuació positiva a l'aparellament entre aquests dos símbols, i si el canvi és molt desfavorable penalitzarem aquesta parella aliniada amb una puntuació negativa.

Exemples d'aquestes matrius, basades en criteris de l'evolució, són:

  •  Matrius PAM: Les va iniciar Margaret Dayhoff als anys 70 - 80; ella va estudiar 71 grups de proteïnes en les que en cada grup hi havia un mínim del 85% d'aminoàcids idèntics, és a dir, eren seqüències properes evolutivament, i va observar 1572 canvis de nucleòtids, uns canvis considerats com a mutacions acceptades (accepted point mutations), ja que no alteren la funció de la proteïna.
        A partir d'aquests canvis es va derivar una taula que contenia les freqüències de canvis d'un aminoàcid a un altre, i es va normalitzar considerant que es produís un canvi de mitja entre dues seqüències en la llargada de cada 100 aminoàcids, o el que és el mateix, que un aminoàcid tingués un 1% de probabilitat de mutar. A aquesta distància evolutiva se la va anomenar PAM 1 (1 percent of accepted mutations).

    A partir d'aquesta matriu PAM 1 i considerant que els canvis en un lloc eren independents als canvis que s'havien produït previament en aquest lloc, es va considerar que aquest procés de canvis d'aminoàcids es podria descriure com un model de Markov, segons el qual podem multiplicar aquesta matriu PAM 1 'x' vegades per ella mateixa per anar aconseguint matrius que corresponguin a intervals evolutius cada cop més grans i puguem així comparar seqüències més separades evolutivament entre elles.
        Per exemple la matriu PAM 250 és la matriu que descriu les probabilitats de canvi d'aminoàcids quan cada residu ha mutat un promig de 2'5 vegades (250%), i s'ha obtingut multiplicant PAM 1 250 vegades per ella mateixa.


  •  BLOSUM: Són diferents a les PAM ja que les BLOSUM deriven de "blocs" de seqüència conservats en grups de proteïnes, és a dir, aliniaments locals sense gaps que podem trobar a la base de dades Blocks.

    Com abans, puntuacions negatives en les caselles de la matriu ens indicaran que la substitució entre aquests dos aminoàcids és desfavorable, i puntuacions positives que el canvi és favorable o que simplement no canvia la funció de la proteïna.
        Hi ha diferents matrius BLOSUM, segons si volem aliniar seqüències més o menys similars, com passava també en el cas de les matrius PAM. En aquest cas, per exemple, la matriu BLOSUM 45 està construïda a partir de seqüències que com a màxim tenen un 45% de similaritat entre elles, i la BLOSUM 80 com a màxim un 80% de similaritat. Aquí, doncs, haurem d'usar matrius amb valors alts (80) per compara seqüències properes evolutivament entre elles, a l'inrevés que les matrius PAM, que haurem d'agafar les de valors més baixos (PAM 1, p.ex.) per fer aquest tipus de comparacions. Altres exemples de matrius BLOSUM són: BLOSUM 30 i BLOSUM 62 .


    La puntuació dels gaps és rellevant, perquè pot fer variar la puntuació dels aliniaments. Un esquema de puntuacions que tracti els gaps com els mismatchs, amb la mateixa puntuació, és poc realista, ja que des del punt de vista de l'evolució, és menys versemblant que s'hagi produït en la seqüència dos esdeveniments d'inserció - delecció que no pas que s'hagi produït un esdeveniment d'aquests però que abarquin una seqüència més llarga.
    Per això, la majoria de programes d'aliniament de seqüències, incloent-hi el nostre, consderen dos components en la puntuació per als gaps, que poden puntuar diferent (segons el que ens interessi en cada cas concret):
  1. Obertura de gap.
  2. Extensió de gap: aquesta ve determinada per una funció que depèn de la longitud del gap.
A més d'això, hem de considerar també un altre fet biològic que és que és més provable que els gaps es trobin en un dels extrems de la proteïna, ja sigui en l'extrem C-terminal o en l'N-terminal, que no pas al mig de la seqüència, ja que això implica que només hi ha hagut pèrdua d'un tros de la seqüència en el primer cas, en comptes d'un tall i lligament de la seqüència en el segon cas.
    Per representar això en el nostre programa hem inicialitzat la primera fila i la primera columna de la matriu de l'aliniament amb les penalitzacions corresponents a extensió de salt en comptes d'amb les d'obertura de salt.