Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática:

1. Dynamic Programming and Graph Algorithms in Computer Vision: A Survey.
2. Dynamic programming and board games: A survey (acceso restringido con usurio/clave).
3. Some dynamic programming problems useful to solve the mobile robot localization problem.
4. Systematic Dynamic Programming in Bioinformatics.

Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática:

1. Dynamic Programming and Graph Algorithms in Computer Vision: A Survey.
2. Dynamic programming and board games: A survey (acceso restringido con usurio/clave).
3. Some dynamic programming problems useful to solve the mobile robot localization problem.
4. Systematic Dynamic Programming in Bioinformatics.

El problema tiene aplicaciones, entre otras muchas, en los dominios de

• la bioinformática (ver el enlace http://webdiis.unizar.es/asignaturas/AB/?p=93) y de
• la robótica (ver http://webdiis.unizar.es/asignaturas/AB/?p=1144).

Researchers store images in DNA, search for and perfectly retrieve them.

Y aquí puede encontrarse el artículo de investigación:

A DNA-Based Archival Storage System (por James Bornholt, Randolph Lopez, Douglas M. Carmean, Luis Ceze, Georg Seelig y Karin Strauss).

Se ha creado una página que contendrá información sobre la nueva asignatura de la especialidad de Computación: Bioinformática.

photo credit: Leigh Prather/ Shutterstock

El próximo miércoles 29 de abril, a las 15:00 h., la presentará en clase (aula 12, edificio Ada Byron) la profesora Elvira Mayordomo.

(Transparencias)

El problema tiene aplicaciones, entre otras muchas, en los dominios de

• la bioinformática (ver el enlace http://webdiis.unizar.es/asignaturas/AB/?p=93) y de
• la robótica (ver http://webdiis.unizar.es/asignaturas/AB/?p=1144).

Hablaremos en clase de la distancia de edición entre secuencias de caracteres.

El problema tiene aplicaciones, entre otras muchas, en los dominios de

• la bioinformática (ver el enlace
  http://webdiis.unizar.es/asignaturas/AB/?p=93) y de
• la robótica (ver
  http://webdiis.unizar.es/asignaturas/AB/?p=1144).

Hace 150 años se encontraron por vez primera partes del esqueleto del denominado hombre de Neandertal cerca de Düsseldorf (Alemania). Desde entonces, hemos querido saber qué relación existe entre el Homo sapiens, nuestro antepasado, y el de Neandertal.

Hoy sabemos que el Homo neanderthalensis no es un ancestro del Homo sapiens, y viceversa. Las diferencias encontradas entre el genotipo del Homo sapiens y el del Homo neanderthalensis lo demostraron. Las nuevas tecnologías nos permiten extraer genotipos de huesos de más de 30000 años de antigüedad. Los genotipos se extraen en forma de secuencias de ADN. Estas secuencias son como los planos de construcción de los seres vivos. Con el transcurso del tiempo, las secuencias de ADN cambian debido a mutaciones. Dadas las secuencias de ADN de diferentes especies, se puede calcular su similitud con la ayuda de un computador. Medimos la similitud de dos secuencias mediante la especificación de la distancia entre ellas. Una pequeña distancia entre dos secuencias de ADN indica una gran similitud entre ambas. Pero, ¿cómo se calcula la distancia entre dos secuencias de ADN? En esta asignatura veremos cómo se diseña un algoritmo para resolver este problema. Para ello, necesitaremos un modelo matemático de las secuencias de ADN, de las mutaciones, y de la distancia entre dos secuencias.

Una secuencia de ADN se compone de bases. Una secuencia de tres bases codifica un aminoácido. Existen cuatro bases diferentes, que suelen representarse con las letras A, G, C y T. Por tanto, una secuencia de ADN puede representarse con una cadena de símbolos del alfabeto Σ = {A, G, C, T}.

Por ejemplo, CAGCGGAAGGTCACGGCCGGGCCTAGCGCCTCAGGGGTG, es una parte de la secuencia de ADN de un pollo.

En la naturaleza, las secuencias de ADN cambian a causa de las mutaciones. Una mutación puede considerarse como una aplicación desde una secuencia de ADN x a otra secuencia de ADN y. Supongamos que todas las mutaciones se pueden modelar utilizando los siguientes tres tipos básicos de mutaciones:

1. borrado de un carácter,
2. inserción de un carácter, y
3. sustitución de un carácter por otro carácter.

Por ejemplo, sea x = AGCT una secuencia de ADN. Entonces, la mutación “sustituir G por C” mutaría x a la secuencia y = ACCT. Utilizamos la notación “a → b” para representar la sustitución de a por b. De igual forma, “a →” representa el borrado del carácter a, y  “→ b” es la inserción del carácter b. Además, debe especificarse explícitamente la posición en la que se produce la mutación.

Para medir la distancia entre dos secuencias de ADN, damos un coste específico a cada mutación básica. La mutación s tiene coste c(s). El coste de una mutación se corresponde con la probabilidad de esa mutación. Cuanto más probable sea una mutación, más bajo será su coste. Utilizamos los siguientes costes para las tres mutaciones básicas:

• borrado: 2
• inserción: 2
• sustitución: 3

Para comparar dos secuencias de ADN x e y, se requiere en la mayoría de los casos más de una mutación básica transformando x en y. Por ejemplo, si queremos comparar x = AG con y = T, entonces no sería suficiente con una mutación básica.

Pero podríamos obtener la transformación usando la secuencia de mutaciones S = A →, G → T (es decir, borrar A y luego sustituir G por T). El coste c(S) de una secuencia de mutaciones, S = s₁. . . , s_t es la suma de los costes de sus mutaciones básicas, es decir,

c(S) := c(s₁) + … + c(s_t).

La distancia entre dos secuencias de ADN se define como el coste de una secuencia específica de mutaciones que transforma una en la otra. El problema es que puede haber muchas secuencias diferentes de mutaciones que transforman una secuencia de ADN en otra. Por ejemplo, podríamos utilizar las siguientes secuencias de mutaciones para transformar la secuencia x = AG en y = T:

• S₁ = A →, G → T;
  c(S₁) = c(A →) + c(G → T) = 2 + 3 = 5
• S₂ = A → T, G →;
  c(S₂) = c(A → T) + c(G →) = 3 + 2 = 5
• S₃ = A →, G →, → T;
  c(S₃) = c(A →) + c(G →) + c (→ T) = 2 + 2 + 2 = 6
• S₄ = A → C, G →, C →, → T;
  c(S₄) = c(A → C) + c(G →) + c(C →) + c(→ T) = 3 + 2 + 2 + 2 = 9

Existen muchas otras secuencias que transforman x en y, pero ninguna de ellas tiene un coste menor que el de las secuencias S₁ y S₂. Para definir la distancia entre dos secuencias de ADN, usamos la secuencia de mutaciones de menor coste. Dada una función de coste c, la distancia de d_c(x,y) de las secuencias de ADN x e y se define como

d_c(x,y) := min{ c(S) | S transforma x en y }.

Por ejemplo, las secuencias S₁ y S₂ son las secuencias de mutaciones con mínimo coste que transforman x = AG en y = T. Por tanto, la distancia evolutiva d_c(x,y) entre x e y es 5.

El cálculo de la distancia evolutiva entre dos secuencias de ADN es uno de los problemas que estudiaremos en esta asignatura.

Fuente: Algorithms Unplugged, B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner (eds.), Springer, 2011.