Revistes Catalanes amb Accés Obert (RACO)

Combinatòria i biologia: funcions d'inferència i alineació de seqüències

Sergi Elizalde i Torrent

Resum


Aquest article mostra alguns exemples d'aplicació d'eines combinatòries
a problemes en biologia computacional. Els models estadístics s'usen per resoldre
qüestions provinents de la biologia, com per exemple per determinar quines parts del
genoma es tradueixen a proteïnes, o com una seqüència d'ADN es va transformar en
una altra durant l'evolució, a través d'una sèrie de mutacions, insercions i supressions.
Cada possible resposta té una certa probabilitat que depèn dels paràmetres del model.
Quan aquests es coneixen, la resposta més probable, anomenada explicació, s'obté
resolent un problema d'optimització combinatòria. La funció que envia cada observació
a la seva explicació corresponent s'anomena funció d'inferència.

En aquest article donem una fita superior al nombre de funcions d'inferència de
qualsevol model gràfic dirigit. Aquesta fita és polinòmica en la mida del model, per un
nombre fix de paràmetres, i representa una millora respecte a la fita exponencial de
Pachter i Sturmfels que es coneixia fins ara. Després apliquem aquesta fita a un model
per alineació de seqüències que s'utilitza en biologia computacional, i veiem que en
aquest cas la nostra fita és asimptòticament ajustada.

Text complet: PDF