Ejemplo

Búsqueda de motivos
En esta clase se repasó, en primer lugar, el problema de buscar motivos en una base de ADN; se puso por ejemplo de un gen de la bacteria E. Coli regulado por el factor detrascripción CRP; la base de datos (ADN) utilizada tiene 18 secuencias de longitud 105 bp; experimentalmente se encontró 23 motivos de longitud 23 bp.
Luego se formulo un modelo matemático delproblema biológico; el modelo consiste en buscar en un espacio de soluciones factibles, un patrón de r palabras de longitud l construídas sobre un alfabeto de 4 símbolos (a, c, g, t), quetiene valor máximo de la función consenso. Obviamente, primero se definieron los conceptos: perfil, función consenso y palabra de consenso. El patrón en referencia queda determinado por un vectorde r elementos de posiciones iniciales, que son las posiciones iniciales de las palabras del patrón.
Finalmente se resolvió el problema por dos métodos: el primero fue una búsqueda a la fuerzabruza bruta, el segundo utilizando un método por “branch and bound”. El método por fuerza bruta requiere un esfuerzo enorme; el espacio de estados debe explorarse exhaustivamente y tiene(n-l+i)r soluciones candidato, de tal manera que tiene un tiempo de ejecución exponencial. El método por “branch and bound” (bab) representa el espacio de búsqueda por un árbol de profundidad r yfactor de ramificación (n-l+1), cuyas hojas representan las soluciones factibles y hay (n-l+1)r. Este árbol se podría explorar por los métodos de búsqueda tradicionales: primero en profundidad,primero en anchura, primero el mejor, A*, etc. El método bab tiene en el mejor de los casos un comportamiento lineal, mientras que en el peor de los casos su comportamiento es exponencial Sinembargo, el método por “branch and bound” visto en clase tiene un buen comportamiento promedio (determinado experimentalmente), y por eso se lo recomienda frente al método por fuerza bruta.