Matemàtica en ajuda de la genètica: l'algoritme de Needleman-Wunsch

L'activitat que presentem no té gaire sentit, per sí mateixa, per realitzar-la a una classe de matemàtiques, però l'adquireix de cop si la fem en paral·lel a les classes de naturals quan s'estiguin treballant qüestions de genètica. Fins i tot, encara serà més rica si es pot treballar també conjuntament amb les classes de tecnologia si acabem elaborant un full de càlcul més "sofisticat" dels que normalment proposem. És un exemple de com la matemàtica ajuda a resoldre un problema plantejat des del camp de la biologia i de com després els informàtics podem implementar un programa a partir de la resposta matemàtica. De fet l'algoritme de Needleman-Wunsch que estudiarem, i del qual podeu trobar molta informació a internet, és un dels més coneguts en el "territori" del que es coneix com a bioinformàtica.

El problema en qüestió es refereix a cercar el millor alineament de dues seqüències biològiques (nucelòtids, aminoàcids, etc,). Mirem'ho amb un exemple relacionat amb la genètica.

Imaginem que tenim dues seqüències d'ADN en la seva forma més tradicional, com una llista ordenada dels quatre tipus de bases que les formen: Adenina (A), Timina (T), Citosina (C) i Guanina (G). Per simplificar posarem com a exemple dues seqüències curtes:

T A C G T C A A

A T T C G C A

Podem tenir la necessitat de comparar aquestes seqüències per diferents raons: mirar si fan funcions similars, esbrinar el grau de proximitat genètica entre dues espècies, etc. L'alineament de seqüències ens pot ajudar a fer-ho. Però quines són les condicions per alinear? Per començar posem una seqüència a sobre de l'altra.

Observem que tenim dues parelles de bases alineades, cinc parelles que són diferents (les de l'esquerra) i un forat a la dreta de la segona seqüència (representat amb un guió). La desaparició d'una base o la diferència entre dues d'alineades poden ser producte de mutacions genètiques.

Però hi ha altres alineacions possibles. Per exemple, aquesta emparella tres bases iguals, tres de diferents i deixa tres forats.

Encara tenim altres possibilitats. En aquesta emparellem cinc d'iguals, una de diferent i deixem tres forats.

Quin dels tres és el millor alineament? De quina forma podem trobar més ràpidament el millor alineament? Aquest és el problema que resol l'algoritme de Needleman-Wunch.

El vols conèixer?

Abordarem el problema en dues parts: la qualificació d'alineaments i la cerca del millor. Finalment farem algunes propostes d'aula.

Puntuació dels alineaments

Podem elaborar un sistema de "premis" i "càstigs" a cadascuna d'aquestes tres possibilitats:

• lletres coindidents (premi)
• lletres diferents (càstig)
• forat (càstig)

Seran els biòlegs els que decidiran la puntuació dels premis i penalitzacions. Posem, per exemple, que triem aquest barem:

• lletres coincidents: +1
• lletres diferents: -1
• forat: -2

Ara podem aplicar aquest barem a les tres alineacions anteriors i observar quina és la que treu millor nota.

És possible que hi hagi altres combinacions. De moment la més òptima, amb les puntuacions donades és la tercera.

En tot cas, disposem d'un sistema de qualificació d'alineacions de seqüències. Ara es tracta de trobar la millor, per un barem donat, de la forma més ràpida possible.

L'algoritme de Needleman-Wunsch

Comparar seqüències curtes "a mà" no és massa complicat. Però si treballem amb seqüències de centenars, milers o milions de "lletres" el problema és fa més gros. L'existència d'un algoritme és important perquè aquest després pot ser programable i els ordinadors podran trobar els millors alineaments molt ràpidament.

Sovint s'explica aquest algoritme comparant dues paraules que tenen el mateix significat en dues llengües diferents, per valorar el seu grau de proximitat. Nosaltres l'explicarem amb aquesta animació emparellant les lletres de dues paraules que l'única relació que tenen és tenir tres lletres iguals: CAUSA i SUCS. (No us espanteu per la quantitat de diapositives, la majoria són molt ràpides).

En aquest cas hi ha tres alineaments òptims amb un valor de -4. Tots ells tenen una coincidència, tres diferències i un forat.

Per a nosaltres, matemàtics, els tres alineaments són equivalents. Seran els biòlegs els que hauran de triar el més raonable segons els seus coneixements.

Sembla evident que si variem les puntuacions els alineaments que podem obtenir seran diferents. Podem fer comparacions alineant les paraules MARCAR i REMAR . A primer cop d'ull podem veure que tenim un grup local de tres lletres (MAR) comú a les dues paraules.

Si fem un barem que puntuï molt la igualtat però penalitzi de forma molt semblant la diferència o els forats podem obtenir dues alineacions òptimes de valor +34, una de les quals és aquesta.

D-diagonal   E-esquerra  A- a dalt

Si penalitzem ara més la diferència que els forats obtenim sis alineaments de puntuació 55. Un d'ells és el següent:

I a l'aula?

En el context que hem assenyalat al començament podem fer diferents activitats.

• Havent explicat el sistema de premis-càstigs podem intentar buscar "a mà" el millor alineament de dues seqüències com: ACTGACTG i AGTGCACG. Aquestes seqüències tenen quatre emparellaments iguals directes (alineant-les per l'esquerra), però posant forats convenientment poden arribar-ne a 6 i amb una puntuació millor.

• Aplicar l'algoritme "manualment" en casos com els descrits, a les seqüències de l'activitat anterior, a paraules semblants (per exemple comparant un mateix mot en català i altra llengua romànica o amb el llatí), a seqüències inventades, etc, Pot ser una bona idea fer treballar petits grups amb una mateixa comparació de seqüències, però amb barems diferents, per poder comparar després els resultats obtinguts.
  
• Explicar l'algoritme, justificar-lo pas a pas. Per què ens quedem amb la màxima puntuació? Per què anem "acumulant" resultats? Ens garanteix la taula contemplar tots els alineaments possibles? Per què un desplaçament lateral o vertical representa un forat?

• Treballar amb applets que permetin modificar alguns paràmetres i introduir seqüències (o paraules) més llargues. .Observar a continuació com varien els resultats segons els canvis de barem. A internet podem trobar alguns applets que, a més, presenten modificacions de l'algoritme. Una de les més interessants penalitza de forma diferent "obrir" un forat que "ampliar-lo". La majoria d'applets permeten pujar arxius amb la qual cosa, si aconseguim seqüències reals d'ADN, podrem fer alguna simulació més real (encara que ens costarà més comparar-les)

Aquest applet permet triar entre alguns paràmetres donats i diferencia "obrir" forat d'anar-lo ampliant

L'applet de Wolfram-Demonstrations només deixa triar entre paraules donades.
Al seu favor té que dibuixa la taula i el "camí"

Aquest applet funciona de forma diferent. La taula no es construeix igual i hi ha un paràmetre nou.
Es poden investigar les modificacions de l'algoritme

• A les classes de tecnologia es pot dissenyar un full de càlcul que en construeixi la taula, tot fent els càlculs i, si gosem, pintant de colors diferents les cel·les segons la direcció. Haurem de fer servir fórmules amb condicionals (SI), buscant màxims (MAX), fent formats condicionals per canviar els colors de les cel·les. Podeu descarregar un exemple en aquest enllaç.

• Podem investigar altres algoritmes de comparació o d'alineament existents. És tot un camp obert per fer un bon treball de recerca de batxillerat!