Una seqüència en format FASTA consta de dues parts. La primera comença sempre pel símbol “>” i correspon a l’identificador de la seqüència. La segona part consta de diferents línies de text que contenen la nostra seqüència d’aminoàcids. Es recomanable que les línies de text no superin els 80 caràcters d’extensió.
Exemple: >gi|29350131|ref|NP_813634.1| putative anti-sigma factor MDKIHYKELIEKYFEGNIADTEIKELSDWIKNDRQLQNWWEQEFTKSDAAIDPILRDKLFARIKE TSPRTKGVRTLPMIPWRWVAAILLPVCIAFFTYYLIDSSQMTSAPFIVKADKGDKATVELPDGTN ASQLSYLNNFGEKVRRVQLNGEAYFKVAPDEKHAFIVQVGDLEVKVLGTSFNVSAYEDAKDITVV GIYTQETSRMMKPGDKIEYNKTTHQLVATQVHPNDYIEWTKGNIYFEKESLENIMKTLSRIYDVS NKLPKEYFTGTIPSGGIQNALNILMLTSPFYYEMDGSVIVLKEK
Utilitzem les matrius de substitució per calcular el valor corresponent en l’alineament de cada parell d’aminoàcids. Hi ha dos tipus principals de famílies de matrius, les Blosum i les PAM
Primerament enregistrem les dues seqüències FASTA en un vector prescindint de l’identificador.
Després enregistrem la matriu de substitució en un “hash of hashes”.
Per fer un alineament global d’aquestes dues seqüències, inicialment nosaltres vam construir una matriu de puntuacions parcials de tots els alineaments possibles a partir de la següent recurrència: (S.B. Needleman and C.D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. 'Journal of Molecular Biology', 48:443-453, 1970.)
Si,j = max (Si-1,j + gap), (Si,j-1 + gap), (Si-1,j-1 + si,j)
Si,j serà el valor que enregistrarem en la casella corresponent, si,j és igual a la puntuació, segons la matriu de substitució donada, d’alinear l’aminoàcid ièssim de la primera seqüència amb el jotaèssim de la segona. Gap és la penalització en cas de alinear un aminoàcid amb un gap, el valor del qual es escollit per l’usuari abans de construir la matriu.
Paral·lelament enregistràvem una lletra en una altra matriu, per tal de saber si la puntuació màxima de Si,j provenia de la casella superior(U), esquerra(L) o diagonal(D).
Entenem per casella superior Si-1,j , esquerra Si,j-1 i diagonal Si-1,j-1.
Un cop teníem les dues matrius construïdes, utilitzàvem les lletres enregistrades a la segona matriu per a recórrer en sentit invers, des de la última casella a la primera, la matriu de puntuacions parcials obtenint l’alineament òptim entre les dues seqüències.
En la presentació de resultats mostrem les dues seqüències alineades, amb el corresponent identificador i completades amb els símbols “*” i “:” que corresponen a igual parell d’aminoàcids i a una puntuació positiva en la casella de la matriu de substitució corresponent a aquell alineament, respectivament.
Incorporar diferents penalitzacions per a l’obertura i extensió de gaps. Això ho vam fer afegint una iteració més al programa de manera que la complexitat va augmentar a cúbica. Aquesta innovació consistia no només recollir la màxima puntuació de les caselles immediatament esquerra o immediatament superior, sinó tenir en compte possibles salts que permetessin una puntuació més elevada tenint en compte els valors de penalització per obertura de gap i per extensió de gap.
Reduir a ordre quadràtic la complexitat del programa. Per fer això vam utilitzar un nou sistema de recurrències: (Pavel A. Pevzner'Computational Molecular Biology. An algorithmic Approach' MIT Press, 2000.)
On EG és el valor de penalització per extensió de gap, OG és el valor de penalització per obertura de gap, Si,jU és una nova matriu on enregistrem els valors corresponents a les puntuacions superiors i Si,jL és una nova matriu on enregistrem els valors corresponents a les puntuacions esquerres.
Per tant, d’aquesta manera, hem reduït la complexitat de l’algorisme i també el temps d’execució del programa, sacrificant espai de memòria ja que cal enregistrar 4 noves matrius.
Implementar reduccions de les penalitzacions per a gaps situats als extrems de l’alineament. Per tal de fer-ho, hem optat per a eliminar el valor d’obertura de gap en tots aquells gaps que es troben al principi o final de l’alineament que corresponen a tots aquells que es troben a la primera columna i la primera fila de la matriu de puntuacions parcials.