DISSENY DEL PROGRAMA

Aquest programa (com molts altres) està estructurat en quatre blocs bàsics. És important destacar que, enfront el plantejament inicial, s'han fet diverses millores, de les quals es recomana la seva lectura abans d'accedir a les explicacions dels blocs esmentats:

    -Declaració de varibles.

    -Entrada de dades.

    -Cos del programa.

    -Sortida de dades.

    -Funcions.

Si voleu fer un anàlisi més exhaustiu sobre el disseny de Let's seXXXqs!!!, podeu veure el seu Codi font; aquest, disposa d'anotacions al costat de cada comanda i resulta molt autoexplicatiu.

Let's seXXXqs!!!





MILLORES

La principal millora que s'ha fet respecte al plantejament inicial és la d'aplicar l'anomenat Affine Gap Model. Si ens fixem en els següents alineaments:


...veurem que tenen la mateixa puntuació final i per tant tots dos podrien ser considerats com a òptims, però el primer té més sentit des del punt de vista evolutiu, doncs només presenta un fenòmen d'inserció o deleció, mentres el segon en necessita dos. Aquesta distinció ens serà possible gràcies a l'Affine Gap Model, doncs la penalització de salt es desdoblarà en dos components:


... on O és l'obertura de salt i E l'extensió de salt, multiplicat per l posicions seguides (en les que s'ha extés el salt). Així, el nostre exemple anterior quedaria de la següent manera:


Per aplicar aquest model al nostre programa l'opció més intuitiva és la d'afegir una iteració al programa dins de l'algorisme, de manera que calculi la màxima puntuació d'introduir un salt entre totes les possibilitats que ofereixen totes les caselles anteriors de la fila (o columna, segons quina seqüència sigui) i no només la de la casella anterior. El problema d'aquesta solució és que fa augmentar l'ordre de complexitat de l'algorisme de cuadràtic a cúbic!!!


La segona millora (dins de la primera...) és precisament la de poder aplicar l'Affine Gap Model mantenint l'ordre de complexitat cuadràtic, mitjançant el següent algorisme:


Aquest, és una adaptació del que ja hem vist anteriorment a l'apartat Mètodes (programació dinàmica). En aquest, en comptes d'escollir entre les tres opcions ja esmentades, s'escull entre l'opció de sumar la puntuació d'alinear els dos símbols a la de la casella anterior en diagonal i les opcions dels valors de les caselles Si,j de les matrius de salts. Aquestes dues matrius "noves" es generen paral.lela, però prèviament (referent a cada casella Si,j) a la de puntuacions, així ja existeix un valor per quan l'algorisme recorre a elles a l'hora de triar entre les tres opcions abans esmentades. El sentit d'aquestes matrius, és que abans de triar si introduim salt o no, haurem de triar si és millor que aquest sigui nou (per tant obertura de salt) o que sigui l'extensió d'un d'anterior.

*(Per entendre millor el funcionament d'aquest procés, podeu visitar l'apartat Exemples de la plana web)


La tercera millora és que no s'ha considerat obertura de salt en aquells salts situats al principi de la seqüència, doncs a nivell biològic és més provable que no pas un salt enmig, doncs el primer pot provenir d'un salt ja obert en la part anterior de la seqüència (que no coneixem o que no estem alineant...), en canvi, en el segon cas sabem del cert que el salt s'està obrint. Per tant, en la primera casella de la primera fila i la primera casella de la primera columna de la matriu de puntuacions, es penalitza només amb l'extensió de salt.


Finalment comentar que, degut al caracter seqüencial de l'aplicació de l'algorisme, hi haurà preferències en cas d'empat en les puntuacions a l'hora de triar les diverses opcions. En el nostre cas, es dóna preferència a l'extensió de salt enfront l'obertura de salt, i a l'introducció d'un salt a la segona i primera seqüència (per aquest ordre) enfront l'alineament dels respectius símbols.


TORNA



DECLARACIÓ DE VARIABLES

En aquest bloc senzillament es llisten les variables més importants que farem servir durant la consecució del programa. Això ho fem perquè el programa necessita que si hem d'utilitzar variables prèviament les declarem, o sigui, que especifiquem la intenció d'utilitzar-les. Posteriorment ja les inicialitzarem assignant-les un/s valor/s per primer cop.


TORNA



ENTRADA DE DADES

En aquest bloc es realitzen les següents accions:

    -Captura de les seqüències. Per a cada una d'elles, primer es registra el seu nom identificador en una variable singular i després el símbols que la conformen en un vector (variable plural), amb cadascun dels símbols en la respectiva posició del vector.

    -Captura de la matriu de substitucions. Es recorre la matriu i es registren els seus valors en un "hash de hash's". Un hash és una variable plural com un vector, però que en comptes d'indexar els seus valors per la posició, ho fa associant-los a una clau. En el nostre cas, tractant-se d'una matriu bidimensional, tindrem dues claus (seran els dos símbols que es substitueixen), que aniran associades al seu respectiu valor de substitució.



TORNA



COS DEL PROGRAMA

Aquest bloc és el més important; el podríem descriure com el "motor" del programa. En ell es realitzen les següents accions:

    -Construcció de les matrius de salts (dues),puntuacions i d'alineament. Per a omplir-les farem servir l'algorisme de programació dinàmica adaptat a l'Affine Gap Model (ja vist a millores). Cada matriu l'enregistrarem en un "vector de vectors", doncs tindrem dues dimensions de posicions per accedir als valors (com en el cas del "hash de hash's); cal destacar, però, que en algunes posicions (només en les que sigui necessari) de les dues matrius de salts tindrem un valor en la tercera dimensió, corresponent al nombre de posicions que s'està extenent un salt. Aquesta indicació és necessaria posteriorment per a poder recuperar l'alineament.

    -Recuperem l'alineament òptim a partir de la matriu d'alineament. En dos vectors anirem enregistrant els símbols de cada una de les seqüències o el símbol del salt "-", en funció de la procedència de cada casella que progressivament ens vagi indicant la matriu. A més, enregistrem en una variable la llargada de l'alineament i en una altra la puntuació final o score, corresponent al valor que trobem a l'última casella abaix a la dreta de la matriu de puntuacions.

    -Generem el vector paral.lel a l'alineament (característic del format CLUSTAL), que fa referència als graus d'identitat i similitud. Els calculem i els enregistrem en una variable.



TORNA



SORTIDA DE DADES

Aquest bloc és el que s'ocuparà de retornar-nos els resultats que esperem després d'haver executat el programa; senzillament fa:

    -Preparar el format de les variables que contenten l'etiqueta identificadora de les seqüències, de manera que s'ajustin a les nostres necessitats a l'hora de mostrar-les per pantalla. A més, també generarem un vector ple d'espais, donat que encara que el vector de l'alineament amb els símbols d'identitat i similitud no té etiqueta, també necessita una separació per estar ben alineat quan el mostrem per pantalla.

    -Finalment mostrar el resultat, o sigui l'alineament òptim entre les dues seqüències desitjades, en format CLUSTAL.



TORNA



FUNCIONS

En aquest bloc tenim totes les funcions necessàries per a executar el programa. Si us mireu el Codi font, veureu que és on realment s'hi troben totes les comandes... Les funcions per a executar Let's seXXqs!!! són (en ordre d'aparició):

    -FASTArapid

    -MATRIXexpress

    -SEXoclock

    -YANKEESgohome

    -LADYstardust

    -LASTname



TORNA