DESENVOLUPAMENT DEL PROGRAMA



Aquest programa està estructurat en 5 parts ben diferenciades, on 4 d'elles estan posades dins de funcions.
  • Entrada de paràmetres necessaris per tal d'executar el programa
  • Llegir els fitxers de les seqüències
  • Llegir la matriu de substitució
  • Construir la matriu d'aliniament
  • Recuperar i mostrar l'aliniament


ENTRADA DE PARÀMETRES

  Necessitem entrar-hi les dues seqüències que volem aliniar. Aquestes han d'estar en format FASTA per tal de que el programa les pugui llegir. A més, haurem d'indicar quina matriu de substitució volem que el programa tingui en compte a l'hora de construir l'aliniament. Finalment, només falta indicar-li quina penalització per obertura de gap i per extensió de gap volem donar a l'aliniar un aminoàcid amb un gap.



LLEGIR FITXERS DE SEQÜÈNCIES

   El programa utilitza una funció per agafar els aminoàcids que contenen cadascuna de les seqüències i ho enregistra en forma de vector, de manera que cada posició del vector correspon a un determinat aminoàcid dins de la seqüència. Cridem la funció dues vegades ja que tenim dues seqüències. A més, passem tot els caràcters a majúscules per si la seqüència entrada conté algun caràcter en minúscula que el programa més endavant no reconeixeria.



LLEGIR MATRIU DE SUBSTITUCIÓ

   Mitjançant una funció, el programa llegeix la matriu de substitució indicada al principi i l'enregistra en forma de hash de hashos - és una estructura semblant a un vector de vectors amb la diferència que no es guia per posicions sinó per dues paraules clau - . Això ens servirà més endavant per poder recuperar les puntuacions corresponents a aliniar dos aminoàcids, ja siguin iguals o diferents.



CONSTRUIR MATRIU D'ALINIMAMENT

   Per tal de construir la matriu, fem servir una funció a la que li entrem els paràmetres següents:
  1. Vector on hi ha la primera seqüència
  2. Vector on hi ha la segona seqüència
  3. Hash de hashos on hi ha la matriu de substitució
  4. Valor de la penalització per obertura de gap
  5. Valor de la penalització per extensió de gap
Durant la funció construim quatre matrius, una on hi enregistrem les puntuacions màximes que obtenim com a resultat d'aplicar l'algorisme de programació dinàmica, l'altra on indicarem E, A o D tot depenent de la procedència del valor màxim, i les altres dues que contindran els valors màxims obtinguts de totes les possibilitats d'introduir salts de diferents longituds en l'aliniament, una per als salts cap a la dreta i l'altra per als salts cap amunt; aquestes dues últimes matrius tenen tres dimensions, la primera on hi ha la puntuació i la segona on hi ha el número de gaps introduïts. Juntament a la lletra en la segona matriu indiquem també el número de salts que hem hagut d'introduir per tal que ens dóni la màxima puntuació en el cas d'aliniar amb gap (aquest número el treiem de les dues matrius que els contenen, abans mencionades).
En la matriu de les puntuacions, en la primera posició, assignem per definició el valor 0 mentres que en la primera fila i columna, cada aminoàcid de la seqüència corresponent s'alinia amb un gap. Les penalitzacions per gap en aquests casos, corresponen a extensió de gap, i no a obertura tot i que estem obrint un gap, per una raó biològica, ja que és més provable que hi hagin gaps als extrems C o N-terminals que no pas al mig de la seqüència.
Així mateix, en la matriu de la procedència, a la primera posició hi assignem: FI per indicar que aquí s'acaba l'aliniament (simbòlic); la primera fila correspondrà tota a E1 (esquerra) i la primera columna a A1 (amunt).
Arribat aquest punt, només ens cal omplir les posicions interiors de la matriu. Això ho fem buscant el valor màxim entre les tres possibilitats que se'ns ofereixen: diagonal, esquerra i amunt, fent servir el següent algorisme de programació dinàmica:

Si,j = màxim entre
  • Si-1, j-1 + S(i,j)
  • Si-1, j + gap
  • Si, j-1 + gap
on Si i Sj corresponent a les coordenades de cada posició en la matriu, S(i,j) el valor d'aliniar aquests dos aminoàcids en la matriu de substitució i gap és el valor de la penalització per gap.

En el cas dels aliniaments amb gaps - els que venen de dalt o de l'esquerra - hem obtingut aquests valors mitjançant una subfunció que el que fas és anar calculant totes les puntuacions d'introduir totes les possibles llargades de gaps des de la posició on estem fins al principi de la fila o de la columna (depenent de si es tracta del valor esquerra o amunt respectivament), i ens retorna el valor màxim juntament amb el número de gaps que hem introduit.Això ho fa emmagatzemant els diferents valors en una nova matriu, per cada direcció dels gaps (esquerra i amunt); d'aquesta manera aconseguim que el programa es mantingui en complexitat cuadràtica ja que no cal que recalculi els valors en cada posició perquè els pot recuperar de la nova matriu.
Obtingudes ja les 3 possibilitats: diagonal, esquerra i amunt, triem en cada cas el valor més gran i l'anotem en la primera matriu - la de puntuacions ; a més, anotem en la segona matriu - la de la procedència - d'on l'hem agafat.
Finalment, ajuntem les dues matrius construïdes en una matriu de tres dimensions on en la posició 0 de la tercera dimensió hi enregistrem la matriu de les puntuacions i en la posició 1 la matriu de la procedència.



RECUPERAR I MOSTRAR L'ALINIAMENT

  Mitjançant la última funció del programa aconseguim recuperar l'aliniament òptim començant per la última posició de la matriu de tres dimensions i anar retrocedint fins arribar a la primera posició.

La sortida la mostrem en forma de tres vectors: els 2 primers vectors contindran les seqüències correctament aliniades, i el tercer vector contindrà els símbols corresponents a cada parella d'aminoàcids aliniats: si aquests són idèntics, es representarà per un '*', si són diferents però la puntuació d'aliniar-los és superior a 0 en la matriu de substitució, es representarà per ':', i si la seva puntuació és menor que 0 o estan aliniats amb un gap, no mostrarem cap símbol.
Per recuperar l'aliniament, ens basem amb la posició 1 de la tercera dimensió de la matriu, ja que aquí trobarem el camí a seguir per anar acumulant en cada posició la màxima puntuació possible de tot el recorregut que ja hem fet - en aquest concepte es basa la programació dinàmica, en resoldre es problemes basant-se en la resolució del problema anterior -.

Per tal de mostrar l'aliniament òptim final d'una manera ordenada i il·lustrativa fem les següents modificacions:

  • Anem recorrent els tres vectors per tal de que quedin dividits al sortir per pantalla en blocs de 50 posicions
  • Introduim al principi de cada bloc, l'identificador de la seqüència corresponent, als que al principi d'aquesta funció haurem eliminat, si existeix, el símbol '>' que molt sovint trobem a l'identificador de les seqüències en format FASTA.
  • Calculem el % d'identitat de l'aliniment a partir dels '*' del vector on hi hem enregistrat els simbols
  • Calculem el % de similaritat de l'aliniament a partir dels '*'  i  ':' del vector de símbols
  • Mostrem l'Score que ja tenim a la matriu



Per poder veure millor l'estructura del programa, clicant aquí el podreu observar.