Download Tarea 3: Análisis Genético Objetivos Introducción

Universidad Técnica Federico Santa María
Departamento de Informática
Campus Santiago San Joaquín
Tarea 3: Análisis Genético
Estructura de Datos, Segundo semestre 2011
9 al 23 de Enero de 2012
Profesor:
Diego Arroyuelo ([email protected])
Ayudantes: Alex Arenas ([email protected])
Ignacio Ureta ([email protected])
Objetivos
Implementar en C el TAD Árbol Binario y para el análisis estadístico de ciertas
características utilizando recorridos en profundidad.
Introducción
Los genes determinan nuestras características físicas y sicológicas de acuerdo a las
combinaciones que puedan hacer dependiendo de nuestros padres y ancestros.
Un gen está compuesto por una parte de cada uno de los padres y esta parte puede ser
dominante o recesiva. Por ejemplo, para el caso del gen que determina el color de ojos la
condición dominante en el ser humano es el color café y la condición recesiva es el color
azul, si un padre y una madre tienen los ojos azules (recesivo) el hijo resultante de ellos
dos tendrá los ojos azules y tendrá 100% de posibilidades de heredar sus ojos azules. Si
un padre tiene los ojos azules (recesivo) y la madre los ojos cafés (dominante) su hijo
tendrá los ojos cafés y tendrá 50% de posibilidades de heredar ojos azules. Si un padre y
una madre tienen los ojos cafés (dominante) su hijo tendrá los ojos cafés y un 0% de
heredar ojos azules. Lo mismo ocurre para el caso del gen que determina el color del pelo
(dominante: castaño, recesivo: rubio) y de la piel (dominante: morena, recesivo: blanca).
Color de ojos
Madre
Padre
Cafés
Azules
Cafés
Cafés
Cafés
(0% heredar azul)
(50% heredar azul)
Azules
Cafés
Azules
(50% heredar azul)
(100% heredar azul)
Tarea 3: Análisis Genético (TAD Árbol Binario)
Estructura de Datos, Segundo Semestre 2011
Color de Pelo
Madre
Padre
Castaño
Rubio
Castaño
Castaño
Castaño
(0% heredar Rubio)
(50% heredar Rubio)
Rubio
Castaño
Rubio
(50% heredar Rubio)
(100% heredar Rubio)
Color de piel
Madre
Padre
Morena
Blanca
Morena
Morena
Morena
(0% heredar Blanca)
(50% heredar Blanca)
Blanca
Morena
Blanca
(50% heredar Blanca)
(100% heredar Blanca)
Los bebes recién nacidos pueden tener un color de ojos, pelo y piel que no
necesariamente será el que tendrán cuando sean adultos. Una familia desea saber cual
será el color de su primer hijo, basándose en análisis genéticos que lograron obtener de
los restos de los 16 tatarabuelos del niño.
Tareas a Realizar
Se debe reconstruir el árbol genealógico del niño con toda su familia partiendo desde él
(raíz) hasta llegar a sus tatarabuelos (incluye: niño, 2 padres, 4 abuelos, 8 bisabuelos y 16
tatarabuelos) para luego calcular la probabilidad de que el niño tenga un determinado
color de ojos, pelo y piel.
1. Se deben programar en C (en Linux, se compilará en los computadores del LPA o
LDS con S.O. Fedora 12 o 16) las principales funciones para el TAD Árbol Binario
(como mínimo insertarNodo, tieneHijoIzquierdo, tieneHijoDerecho, esHoja).
2. Se deberá leer un archivo llamado Tatarabuelos.txt, el cual contiene las
características genéticas de los 16 familiares del niño.
Página 2 de 5
Tarea 3: Análisis Genético (TAD Árbol Binario)
Estructura de Datos, Segundo Semestre 2011
El archivo Tatarabuelos.txt tiene el siguiente formato:
Ojos
Pelo
Piel
…
Ojos
Pelo
Piel
gen recesivo-recesivo
gen dominante-recesivo
gen dominante-dominante
gen dominante-dominante
gen dominante-recesivo
gen dominante-recesivo
El archivo debe tener 48 lineas (cada 3 lineas representa a un tatarabuelo) en donde
están contenidas las características genéricas de los 16 tatarabuelos.
3. Utilizando el TAD Árbol binario programado, construir el árbol genealógico teniendo la
precaución de hacerlo por niveles, es decir, primero se agrega el niño, luego los
padres, luego los abuelos, luego los bisabuelos y finalmente los tatarabuelos
(representando creativamente las características contenidas en el archivo).
4. Calcular a partir de los tatarabuelos (nodos hoja) la probabilidad en porcentaje (con
dos y solo dos decimales) de que cada integrante de la familia tenga los ojos, pelo
y piel de un determinado color. Para ello se deberá realizar un recorrido en
profundidad del árbol. (Pista: ¿Cómo se llama el recorrido en profundidad que recorre
hijo izquierdo, hijo derecho y después raíz?).
5. Por último el programa deberá generar un archivo de salida llamado Familia.txt el
cual contiene la probabilidad de cada integrante de la familia de tener los ojos, el pelo
y la piel de un determinado color, el formato esperado es el siguiente:
Tatarabuelo 1
Ojos
Azules
Pelo
Rubio
Piel
Blanca
...
Tatarabuelo 16
Ojos
Cafes
Pelo
Castanio
Piel
Blanca
Bisabuelo 1
Ojos
Azules
Pelo
Rubio
Piel
Blanca
...
75.00%
50.00%
100.00%
Cafes
Castanio
Morena
Página 3 de 5
25.00%
50.00%
0.00%
Tarea 3: Análisis Genético (TAD Árbol Binario)
Estructura de Datos, Segundo Semestre 2011
Bisabuelo 8
Ojos
Azules
Pelo
Rubio
Piel
Blanca
25.00%
50.00%
67.00%
Cafes
Castanio
Morena
50.00%
50.00%
56.00%
5
Azules
Rubio
Blanca
25.00%
50.00%
60.00%
Cafes
Castanio
Morena
50.00%
50.00%
40.00%
Padre
Ojos
Pelo
Piel
Azules
Rubio
Blanca
25.00%
50.00%
100.00%
Cafes
Castanio
Morena
50.00%
50.00%
0.00%
Madre
Ojos
Pelo
Piel
Azules
Rubio
Blanca
25.00%
50.00%
100.00%
Cafes
Castanio
Morena
50.00%
50.00%
0.00%
Ninio
Ojos
Pelo
Piel
Azules
Rubio
Blanca
5.00%
45.00%
34.00%
Cafes
Castanio
Morena
95.00%
55.00%
66.00%
...
Abuelo
Ojos
Pelo
Piel
...
Notar que solo los tatarabuelos tienen un color exacto de ojos, pelo y piel, el resto de la
familia tiene un porcentaje de tener cierto color. Se deben enumerar los tatarabuelos del 1
al 16, los bisabuelos del 1 al 8, los abuelos del 1 al 4. El padre, la madre y el niño
aparecen con su propio nombre (no como Padre 1, Padre 2, etc). Si se desea se puede
distinguir entre hombres y mujeres.
Página 4 de 5
Tarea 3: Análisis Genético (TAD Árbol Binario)
Estructura de Datos, Segundo Semestre 2011
Entrega
La tarea debe entregarse vía correo electrónico al mail del ayudante
[email protected] con el asunto “[EDD] Tarea 3 Grupo X” (sin las comillas y
reemplazando X por su número de grupo).
La tarea debe enviarse comprimida en un archivo TAR.GZ llamado GrupoX.tar.gz
(reemplazando X por su número de grupo) que debe contener:
-
El archivo compilable. (tarea3.c)
Nombre, ROL y que programó cada alumno. (nombres.txt)
Indicaciones de compilación de ser necesarias. (README.txt)
Archivo de entrada inventado por los integrantes del grupo con todos los
tatarabuelos necesarios para que haya podido nacer el niño. (Tatarabuelos.txt)
El plazo máximo para la entrega de esta tarea es el día lunes 23 de enero de 2012 hasta
las 23:59:59 hrs. Habrá un bonus de 5 puntos para quienes la entreguen antes del
viernes 20 de enero de 2012 hasta las 23:59:59 hrs.
Se descontarán 30 puntos por cada día de retraso o fracción.
Restricciones y Consideraciones
Las tareas deben compilar en los computadores que se encuentran en el LPA o LDS
(Fedora 12 o 16). Si la tarea no compila, no será revisada. La tarea será compilada con el
comando
gcc –Wall tarea3.c –o salida
Por cada Warning en la compilación se descontarán 5 puntos.
La tarea debe funcionar al menos con el archivo Tatarabuelos.txt proporcionado por
cada grupo.
Se debe respetar la integridad de los TAD Árbol Binario, accesos inmediatos a las
estructuras se considerará como una violación grave del TAD y será evaluado con nota
cero.
Se deben respetar al pie de la letra los formatos de los archivos Tatarabuelos.txt,
Familia.txt y formatos de entrega especificados en este enunciado.
La tarea debe enviarse desde un correo electrónico institucional, @alumnos.usm.cl o
@alumnos.inf.utfsm.cl.
Si se detecta Copia, la tarea será evaluada con nota cero.
Tareas que no cumplan con alguna de estas restricciones arriesgan descuentos e incluso
la no revisión.
Página 5 de 5