CC30A Algoritmos y Estructuras de Datos

Prof. Rodrigo Paredes

Tarea 2

Fecha de entrega: viernes 13 de septiembre. No se aceptarán tareas atrasadas.


Objetivos

En esta tarea se pretende prácticar con dos estructuras de datos básicas en computación: los árboles y las listas.

El problema que vamos a abordar en esta tarea consiste en buscar cuál es el gen menos repetido dentro de una secuencia genética e indicar las posiciones del gen dentro de la secuencia.
 

Descripción de la tarea

Uno de los problema estudiados en biología computacional es buscar genes cortos dentro de una secuencia genética grande.

Para simplificar el problema vamos a considerar que la secuencia genética consiste en un string gigante (secuencia S, de tamaño n), compuesta por las letras 'A', 'C', 'G' y 'T'. Por ejemplo:

TACTAAGAAGC

y lo que interesa es buscar strings cortos (gen G, de tamaño m) dentro de esta secuencia gigante. Por ejemplo, si consideramos genes de tamaño 2, en gen CC no está presente en la caneda, en cambio, el gen AA se presenta 2 veces en la cadena.

La metodología que utilizaremos para resolver este problema es simple:

Vamos a considerar un árbol 4-ario de m niveles de profundidad. Los nodos internos pueden tener 4 hijos, puesto que son 4 las posibles letras, y las hojas contienen la lista de posiciones del gen G dentro de la secuencia S.

Considere la siguiente estructura del nodo interno y de las hojas:

Nodo{
  Nodo hijoA;
  Nodo hijoC;
  Nodo hijoG;
  Nodo hijoT;
}

Hoja {
  ListaInt pos;
}

Para la secuencia TACTAAGAAGC, con genes de tamaño 2, se tiene el siguiente árbol:

Como se dijo anteriormente el gen AA está en las posiciones 4 y 7 de la secuencia, y el gen CC no está presente en la secuencia.

Para usar esta estructura para buscar el gen que menos se repite, tenemos que hacer dos cosas:

  1. Generar el árbol (con las listas vacias) para el tamaño del gen buscado
  2. Leer el archivo y cargar las listas con las posiciones de los genes
Para cargar los genes en las lista tenemos que:
  1. Leer el gen i-ésimo
  2. Descender en el árbol segun las letras del gen i-esimo
  3. Una vez en la hoja, guardar la posición del gen (i) en la lista
Este ciclo lo hacemos para los n - m genes de la secuencia (ojo que el primer gen está en la posición 0).

Una vez que tenemos calculadas las posiciones de todos los genes de S, para encontrar el gen que menos se repite, basta con buscar la lista más corta. Si hay empate, se dejan los dos genes como los menos repetidos.

De acuerdo a lo anterior, en esta tarea se le solicita implementar la estructura para buscar genes dentro de una secuencia, de modo de determinar cuál o cuáles son los genes que menos se repiten, y mostrar las posiciones el o los genes menos repetidos (si el gen no está presente en la secuencia, la lista de posiciones es vacia).
 

Pruebas

Implemente la estructura para buscar genes de 8 caracteres, es decir, un árbol 4-ario de 8 niveles, y pruebe su programa con los archivos: Los datos vienen en una línea larga, terminada con un '\n'.

Puede utilizar el programa  getGen.class

$ java getGen pos archi

que muestra el gen en la posición pos del archivo archi, por ejemplo:

$ java getGen 20 dnacorto

para verificar los resultados de su programa (este programa estará disponible lo antes posible).

Restricciones

Hints

Tiene que implementar tanto el árbol general como las listas de enteros, ponga especial cuidado en los métodos: Junto con estos métodos, implemente todo lo demás que considere necesario (borrado de elementos, destructores, métodos para consultar si la lista esta vacia, etc.)

Ponderación

El informe equivale a un 50% de la nota de tarea.
El código equivale a un 50% de la nota de tarea.

Entrega de la tarea

 
La entrega de la tarea debe incluir un informe escrito donde se describa y documente el programa realizado, y se incluyan ejemplos de entradas y salidas.

El informe debe ser entregado en la Secretaría Docente de Computación (donde Magaly, tercer piso Edificio de Computación, hasta las 17:00 horas del último día de plazo), y el código fuente (junto a un archivo README que explique como compilar) debe ser enviado utilizando el Cursomático de cc30a.

El contenido del informe debe seguir la siguiente pauta común para todas las tareas:
 

  • Portada