Del árbol genealógico al algoritmo

Un árbol genealógico es un grafo. En cuanto lo ves así, comprobar un patrón de herencia se reduce a un solo recorrido por los nodos.

El problema

Un árbol genealógico es un conjunto de personas, cada una con un sexo y un estado de afectación, conectadas por relaciones de parentesco. Queremos una función que reciba un árbol genealógico y devuelva verdadero si es compatible con un patrón de herencia dado, y falso si alguna relación lo contradice.

Trabajaremos con un patrón: el autosómico recesivo. Los otros cinco siguen la misma estructura, con una sola regla diferente dentro del bucle.

La regla

La herencia autosómica recesiva necesita dos copias del alelo recesivo para producir el fenotipo afectado. El genotipo aa es afectado, AA y Aa no lo son. Hay un emparejamiento que produce una violación segura: si ambos padres son aa, todos los hijos deben ser aa también, ya que ninguno de los padres tiene un alelo A que transmitir. Un emparejamiento de afectado con afectado que produce un hijo no afectado rompe la regla. Dos padres no afectados que tienen un hijo afectado no la rompen, eso son simplemente dos portadores.

El código

Representamos a cada persona como un registro con cuatro campos: id, affected, father y mother, donde father y mother apuntan a otros registros, o a nil si se desconoce. Basta con visitar a cada persona una vez y comprobar la regla con sus padres. No importa el orden de recorrido, ya que la regla solo mira a una persona y a sus dos padres inmediatos.

Ocho líneas, una sola comprobación real. Se ejecuta en tiempo O(n), un solo recorrido, trabajo constante por persona.

Los otros cinco patrones

Misma función, diferente línea 6. El patrón recesivo ligado al cromosoma X comprueba un hijo afectado con un padre afectado y una madre no afectada, ya que el cromosoma X de un hijo nunca proviene de su padre. El patrón autosómico dominante invierte la regla: la violación es una persona afectada con dos padres no afectados, no una persona no afectada con dos padres afectados. Los patrones ligados al cromosoma Y y mitocondrial solo miran a uno de los padres, ya que estos patrones solo provienen de un lado.

La herramienta ejecuta estos seis patrones en un solo recorrido cada uno, e informa de cuáles resultaron verdaderos. Cuando más de uno lo hace, esa es la respuesta honesta para un árbol genealógico pequeño, no algo que resolver adivinando.

Si quieres que te expliquemos los patrones de herencia desde el principio, lee nuestro artículo de fundamentos de genética. Para un ejemplo práctico de herencia recesiva ligada al cromosoma X en una enfermedad real, consulta distrofia muscular de Duchenne.