22 de gener de 2015

Llumins topològics

Sovint a classe proposem exploracions que es basen en cerques exhaustives: buscar tots els quadrilàters que es poden fer en un geoplà de 4x4, totes les formes de connectar 5 quadrats que es toquin com a mínim per un costat (pentòminos), tots els tretracubs possibles, etc. En aquestes cerques és normal discutir si figures o formes girades o simètriques són iguals o diferents. En tot cas, aquestes comparacions de "formes" es fan sense "deformar". L'exploració a la que us convidem demana aquest petit esforç suplementari: abstreure els trets fonamentals de la forma, imaginar-se-la amb possibles deformacions. És una exploració "topològica".

Quan s'intenta explicar què és la topologia són dues les "definicions" que més proliferen. Una d'elles diu que és una geometria en la que la mesura no importa. Una altra és que es tracta de la geometria de "la goma elàstica" en la que observem les invariàncies amb un determinat tipus de deformacions: les que estires, comprimeixes, abonyegues, aplanes... però no trenques, no forades, no fas ruptures. Si a qualsevol persona li mostres un dònut, un croissant, un plat i una tassa i li demanes que emparelli farà el que veiem a l'esquema.

En canvi un matemàtic farà aquest altre emparellament:


L'argument serà que cada parella és topològicament equivalent. Dònut i tassa tenen un forat, i plat i croissant cap. Podem convertir sense trencaments un croissant d'argila o plastilina en un plat. I podrem convertir també sense ruptures un dònut (un tor) en una tassa.

Quina és l'exploració que proposem? Començarem amb un exemple.

Si tenim un sol llumí no podem cercar gaires formes diferents: una línia (el llumí és el segment vermell i la línia topològicament equivalent la blava)


Amb dos llumins no anem molt més lluny. De fet no "ens movem". Només podem obtenir una línia (recordem que la mida no importa, el que importa és la forma obtinguda).


Amb tres llumins ja tenim més possibilitats. Obtenim tres formes diferents: una línia, una "estrella" de tres braços i un triangle (una línia tancada sense "apèndixs").


L'exploració tracta de buscar totes les formes topològicament equivalents amb 4, 5 i 6 llumins.

Però abans d'abordar el problema et convidem a continuar llegint per fer algunes precisions.

Continuem?

13 de gener de 2015

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?