árbol de mutación de ADNmt

13

Antecedentes:

El MtDNA es una parte del ADN humano que se transmite de una madre a un niño y rara vez muta. Dado que esto es cierto para todos los humanos, es posible crear un árbol enorme que visualice cómo todos los humanos se relacionan entre sí a través de su ascendencia materna hasta el hipotético EVE. Cada mutación en el MtDNA cuando nace un niño crea una nueva sub-rama de su rama principal en el árbol.

Obtenga más información sobre el ADN mitocondrial (ADNmt) aquí: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Objetivo:

Su programa recibe una lista de recuento de mutaciones de ramas de árbol de ADNmt y su programa debe ofrecer una vista de árbol del mismo.

Ejemplo de entrada y salida:

La entrada es una tabla separada por punto y coma de 3 columnas con una línea para cada rama. Ejemplo:

L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0;mtEVE;10
L0a'b;L0a'b'f;30
L0a;L0a'b;38
L0a1'4;L0a;39
L0a1;L0a1'4;40
L0a1a;L0a1;42
L0a1a NL;L0a1a;43
L0a1a1;L0a1a NL;44
L0a1a2;L0a1a NL;45
L0a1a3;L0a1a NL;44
L0a1 NL;L0a1;41
L0a1b;L0a1 NL;44
L0a1b NL;L0a1b;45
L0a1b1;L0a1b NL;46
L0a1b1a;L0a1b1;47
L0a1b1a1;L0a1b1a;48
L0a1b2;L0a1b NL;48
L0a1b2a;L0a1b2;50
L0a1c;L0a1 NL;45
L0a1d;L0a1 NL;44
L0a4;L0a1'4;55
L0a2;L0a;47
L0a2a;L0a2;49
L0a2a1;L0a2a;50
L0a2a1a;L0a2a1;51
L0a2a1a1;L0a2a1a;53
L0a2a1a2;L0a2a1a;53
L0a2a2;L0a2a;53
L0a2a2a;L0a2a2;54
L0a2b;L0a2;57
L0a2b1;L0a2b;58
L0a2c;L0a2;60
L0a2d;L0a2;49
L0a3;L0a;53
L0b;L0a'b;48
L0f;L0a'b'f;37
L0f1;L0f;61
L0f2;L0f;41
L0f2a;L0f2;46
L0f2a1;L0f2a;59
L0f2b;L0f2;63
L0k;L0a'b'f'k;39
L0k1;L0k;48
L0k2;L0k;54
L0d;L0;21
L0d1'2;L0d;25
L0d1;L0d1'2;30
L0d1 NL;L0d1;31
L0d1a;L0d1 NL;38
L0d1a1;L0d1a;41
L0d1c;L0d1 NL;39
L0d1c1;L0d1c;45
L0d1c1a;L0d1c1;46
L0d1c1b;L0d1c1;46
L0d1b;L0d1 NL;36
L0d1b1;L0d1b;40
L0d2;L0d1'2;31
L0d2a'b;L0d2;32
L0d2a;L0d2a'b;42
L0d2a1;L0d2a;43
L0d2b;L0d2a'b;46
L0d2c;L0d2;45
L0d3;L0d;39

Su programa debería generar una vista de árbol de izquierda a derecha que incluya algunos números basados ​​en la entrada. Según la entrada de ejemplo, esta es una salida válida:

  0│ ┐                                                               mtEVE               [  0][ 63]
 10│ └♦♦♦♦♦♦♦♦♦┬────────────────┬─────────────────────────────────── L0                  [ 10][ 63]
 21│           │                └♦♦♦♦♦♦♦♦♦♦┬──────┬───────────────── L0d                 [ 11][ 46]
 39│           │                           │      └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d3                [ 18][ 39]
 25│           │                           └♦♦♦┐                     L0d1'2              [  4][ 46]
 30│           │                               ├♦♦♦♦┬─────────────── L0d1                [  5][ 46]
 31│           │                               │    └┬────┬┐         L0d1 NL             [  1][ 46]
 36│           │                               │     │    │└♦♦♦♦┬─── L0d1b               [  5][ 40]
 40│           │                               │     │    │     └♦♦♦ L0d1b1              [  4][ 40]
 38│           │                               │     │    └♦♦♦♦♦♦┬── L0d1a               [  7][ 41]
 41│           │                               │     │           └♦♦ L0d1a1              [  3][ 41]
 39│           │                               │     └♦♦♦♦♦♦♦┬────── L0d1c               [  8][ 46]
 45│           │                               │             └♦♦♦♦♦┬ L0d1c1              [  6][ 46]
 46│           │                               │                   ├ L0d1c1a             [  1][ 46]
 46│           │                               │                   └ L0d1c1b             [  1][ 46]
 31│           │                               └♦♦♦♦♦┬┬───────────── L0d2                [  6][ 46]
 45│           │                                     │└♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2c               [ 14][ 45]
 32│           │                                     └┬──┐           L0d2a'b             [  1][ 46]
 42│           │                                      │  └♦♦♦♦♦♦♦♦♦┬ L0d2a               [ 10][ 43]
 43│           │                                      │            └ L0d2a1              [  1][ 43]
 46│           │                                      └♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2b               [ 14][ 46]
 14│           └♦♦♦┬────────┐                                        L0a'b'f'k           [  4][ 63]
 39│               │        └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦┬─────┬──────── L0k                 [ 25][ 54]
 48│               │                                 │     └♦♦♦♦♦♦♦♦ L0k1                [  9][ 48]
 54│               │                                 └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0k2                [ 15][ 54]
 23│               └♦♦♦♦♦♦♦♦┬──┐                                     L0a'b'f             [  9][ 63]
 30│                        │  └♦♦♦♦♦♦┬───────────┐                  L0a'b               [  7][ 60]
 48│                        │         │           └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0b                 [ 18][ 48]
 38│                        │         └♦♦♦♦♦♦♦┬────┬─┬────────────── L0a                 [  8][ 60]
 53│                        │                 │    │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a3                [ 15][ 53]
 39│                        │                 │    └┬────┐           L0a1'4              [  1][ 55]
 40│                        │                 │     │    └┬────┬──── L0a1                [  1][ 50]
 42│                        │                 │     │     │    └♦┬── L0a1a               [  2][ 45]
 43│                        │                 │     │     │      └┬┐ L0a1a NL            [  1][ 45]
 44│                        │                 │     │     │       │├ L0a1a1              [  1][ 44]
 44│                        │                 │     │     │       │└ L0a1a3              [  1][ 44]
 45│                        │                 │     │     │       └♦ L0a1a2              [  2][ 45]
 41│                        │                 │     │     └┬────┬┐   L0a1 NL             [  1][ 50]
 44│                        │                 │     │      │    │└♦♦ L0a1d               [  3][ 44]
 45│                        │                 │     │      │    └♦♦♦ L0a1c               [  4][ 45]
 44│                        │                 │     │      └♦♦┬───── L0a1b               [  3][ 50]
 45│                        │                 │     │         └┬─┐   L0a1b NL            [  1][ 50]
 46│                        │                 │     │          │ └┬─ L0a1b1              [  1][ 48]
 47│                        │                 │     │          │  └┬ L0a1b1a             [  1][ 48]
 48│                        │                 │     │          │   └ L0a1b1a1            [  1][ 48]
 48│                        │                 │     │          └♦♦┬─ L0a1b2              [  3][ 50]
 50│                        │                 │     │             └♦ L0a1b2a             [  2][ 50]
 55│                        │                 │     └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a4                [ 16][ 55]
 47│                        │                 └♦♦♦♦♦♦♦♦┬─┬───┬────┬─ L0a2                [  9][ 60]
 49│                        │                          │ │   │    └♦ L0a2d               [  2][ 49]
 49│                        │                          │ │   └♦┬┬─── L0a2a               [  2][ 54]
 50│                        │                          │ │     │└┬── L0a2a1              [  1][ 53]
 51│                        │                          │ │     │ └┬─ L0a2a1a             [  1][ 53]
 53│                        │                          │ │     │  ├♦ L0a2a1a1            [  2][ 53]
 53│                        │                          │ │     │  └♦ L0a2a1a2            [  2][ 53]
 53│                        │                          │ │     └♦♦♦┬ L0a2a2              [  4][ 54]
 54│                        │                          │ │         └ L0a2a2a             [  1][ 54]
 57│                        │                          │ └♦♦♦♦♦♦♦♦♦┬ L0a2b               [ 10][ 58]
 58│                        │                          │           └ L0a2b1              [  1][ 58]
 60│                        │                          └♦♦♦♦♦♦♦♦♦♦♦♦ L0a2c               [ 13][ 60]
 37│                        └♦♦♦♦♦♦♦♦♦♦♦♦♦┬─┬─────────────────────── L0f                 [ 14][ 63]
 61│                                      │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f1                [ 24][ 61]
 41│                                      └♦♦♦┬───┬───────────────── L0f2                [  4][ 63]
 46│                                          │   └♦♦♦♦┬──────────── L0f2a               [  5][ 59]
 59│                                          │        └♦♦♦♦♦♦♦♦♦♦♦♦ L0f2a1              [ 13][ 59]
 63│                                          └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f2b               [ 22][ 63]

Entrada: detalles

La tabla de entrada no está ordenada en ningún orden en particular. Si reordenamos aleatoriamente las líneas de entrada, la salida debería permanecer igual.

Cada línea en la entrada representa una rama de árbol de ADNmt o una rama de árbol hipotética. La tabla de entrada podría tener cualquier número de líneas de longitud.

Entrada: Detalles - Columna A (nombre de rama):

La primera columna es el nombre real de la rama. El nombre divide las líneas de entrada en 2 grupos de tipos de línea que deben manejarse de manera diferente (explicada más adelante) entre sí:

  • Tipo 1: el nombre consta de cualquiera 'o el sufijoNL
  • Tipo 2: el nombre no consiste en ninguno 'o el sufijo NL.

El nombre puede tener hasta 20 caracteres de longitud.

Entrada: Detalles - Columna B (nombre de la rama principal):

La segunda columna contiene un puntero al nombre de la rama principal. Varias líneas (ramas) pueden compartir el mismo padre. Siempre hay exactamente 1 nombre de rama padre distinto en la tabla de entrada que apunta a un padre que no está representado entre las líneas de entrada, ese nombre de rama padre es la raíz del árbol. En la entrada de ejemplo, que es la tercera línea que apunta a la raíz: mtEVE. Si la entrada tiene más de una raíz o bucles sin fin, es una entrada no válida.

Entrada: Detalles - Columna C (# de mutaciones):

La tercera columna es el número total de mutaciones que una rama en particular ha tenido contando desde la raíz. El ADNmt humano no ha mutado más de 100 veces en una sola línea desde la hipotética raíz materna (EVE ancestro humano / chimpancé), pero su programa debería ser capaz de manejar 3 dígitos # de mutaciones, hasta 999.

A partir de la entrada, puede calcular una rama # de mutaciones únicas restando su # de mutaciones de su padre # de mutaciones.

Salida: detalles

Su programa debería generar 1 de 3 mensajes de error diferentes si la entrada no es válida de acuerdo con la descripción de la entrada.

  • Mensaje de error 1, si la entrada tiene más de una raíz: ERROR: Multiple roots
  • Mensaje de error 2, si los punteros principales de entrada repiten: ERROR: Endless loop
  • Mensaje de error 3, cualquier otra cosa no válida sobre la entrada: ERROR: Invalid input

Si la entrada no contiene errores, su programa debería generar el árbol de acuerdo con las siguientes restricciones: Cada línea consta de 5 partes A, B, C, D y E:

  • A: 5 caracteres, 3 caracteres alineados a la derecha # de mutaciones, un carácter de línea vertical: |y 1 espacio en blanco
  • B: [número máximo de mutaciones] caracteres árbol ancho + 1 espacio en blanco
  • C: 20 caracteres, nombre de rama alineado a la izquierda
  • D: 5 caracteres, 3 caracteres alineados a la derecha # de mutaciones únicas para la rama encapsulada entre [y ]. (Las mutaciones únicas se explicarán a continuación).
  • E: 5 caracteres, número máximo de mutaciones totales alineadas a la derecha de 3 caracteres para esta rama y todas las ramas secundarias encapsuladas entre [y ].

Una rama # de mutaciones únicas es la diferencia en la cantidad de mutaciones que tiene la rama actual de la cantidad de mutaciones que tiene su rama madre. La primera línea es la raíz y debe representarse con 0# de mutaciones y # de mutaciones únicas.

Salida: Detalles - orden de línea / clasificación

Si dos o más subramas comparten el mismo padre, las ramas se ordenan por el número máximo de subramas de mutaciones totales en orden descendente. En nuestro ejemplo L0a1'4, L0a3y L0a2acciones del padre: L0a.

En la vista de árbol, el orden de arriba a abajo es el número máximo de subramas de mutaciones totales entre paréntesis: L0a3(53), L0a1'4(55), L0a2(60).

Si dos o más subramas comparten el mismo número máximo de mutaciones en las ramas secundarias, se alinean verticalmente y se ramifican desde sus padres desde el mismo lugar, el orden de las líneas entre esas subramas es alfabético.

Salida: Detalles - árbol (parte B)

El árbol debe ser dibujado con los caracteres ASCII siguiente: └, ─, ┬, ┐, ├, │,♦

La lógica del árbol es que todas las mutaciones deben estar representadas. Una rama de una rama principal: ┬o ┐representa 1 mutación. Las mutaciones únicas adicionales en la misma rama están representadas por: ♦y deben alinearse a la izquierda y colocarse antes de la primera sub-rama.

Las subramas se ramifican desde su padre a lo largo del eje xy la posición está determinada por el número máximo de mutaciones entre todas las ramas secundarias posteriores.

Como se indicó antes, la entrada tiene 2 tipos diferentes de líneas de entrada. El tipo 1 con cualquier carácter 'o el sufijo NL en el nombre de la rama, no debe llenar la línea horizontal en el extremo derecho de su línea, sino terminar con una ┐en la última sub-rama. En el ejemplo se aplica a las siguientes ramas:

L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0a'b;L0a'b'f;30
L0a1'4;L0a;39
L0a1a NL;L0a1a;43
L0a1 NL;L0a1;41
L0a1b NL;L0a1b;45
L0d1'2;L0d;25
L0d1 NL;L0d1;31
L0d2a'b;L0d2;32

Esperemos que el ejemplo de entrada y salida responda a cualquier pregunta adicional sobre cómo se debe dibujar el árbol, considérelo parte del desafío descubrir la lógica.

Inspiración

Le invitamos a probar mi versión de JavaScript (sin golf) para inspirarse: http://artificial.se/DNA/mtDNAmutationTree3.html (carece de comprobación de errores, y se agregan algunas estadísticas que no son parte de este desafío en particular) .

Una versión completa del árbol de ADNmt [basada en http://www.phylotree.org/ árbol de ADNmt Build 16 (19 de febrero de 2014)] se puede encontrar aquí:

http://artificial.se/DNA/mtDNAfull.html

El archivo de datos utilizado para el árbol completo:

http://artificial.se/DNA/mtDNA_full.txt

Este es un desafío de código de golf.

code-golf ascii-art tree-traversal Plarsen
fuente
L0d1no debe colocarse antes L0d2, de acuerdo con la regla de clasificación: "... orden descendente ..."
guy777
L0a1'4no es (55) sino (39), L0a2no es (60) sino (47) ... ¿Podría aclarar esto?
guy777
L0d1 y L0d2 son ambos 46, por lo que se aplica el orden alfabético
Plarsen
L0a4 55 y un hijo de L0a1'4, por lo que las mutaciones máximas para L0a1'4 son 55
Plarsen
Tengo algunas preguntas: 1) ¿Es este un proyecto real? Tengo la impresión de que algo como esto podría valer dinero real. 2) ¿Cómo obtuviste el resultado de ejemplo? 3) ¿Por qué la parte A tiene 8 caracteres en lugar de 5? 4) ¿Por qué la parte D tiene 6 caracteres en lugar de 5? 5) ¿Por qué "L0a1 NL" tiene "4" en la parte D?
Aditsu renunció porque SE es MAL

Respuestas:

6

Python 3, 925 bytes

¡Sí, menos de 1 KB! Probablemente todavía hay espacio para jugar al golf ...

import sys
class L:
 def __init__(x,**k):x.__dict__.update(k)
m={}
def e(x):print('ERROR: '+x);exit()
try:
 for x in sys.stdin:a,b,c=x.split(';');m[a]=L(s=a,p=b,m=int(c),l=0)
except:e('Invalid input')
a=set()
def k(x):
 if x.l<0:e('Endless loop')
 if x.l<1:y=m.get(x.p);x.l=-1;k(y)if y else a.add(x.p);x.l=1
for x in m:k(m[x])
r=L(s=a.pop(),p=0,m=0)
if a:e('Multiple roots')
m[r.s]=r
c={}
def u(x):
 c[x.s]=[m[y]for y in m if m[y].p==x.s];x.x=x.m
 for y in c[x.s]:u(y);x.x=max(x.x,y.x)
u(r)
o=[]
def f(p,x,o=o):
 d=x.m-p.m;j=p.m+r.x-x.x;s=x.s;x.i=len(o);l=sorted(c[s],key=lambda t:(t.x,t.s));q=' '*j+'└'+'♦'*(d-1);z='─'
 if"'"in s or s[-2:]=='NL'or x==r:q+=z*(x.x-l[0].x);z=' '
 o+=list("%3d│ "%x.m+q+z*(r.x-len(q))+' %-20s[%3d][%3d]'%(s,d,x.x)),;j+=5;o[p.i][j]='┐┬'[o[p.i][j]in'─┬']
 for i in range(p.i+1,x.i):o[i][j]='├│'[o[i][j]in' │']
 for y in l:f(x,y)
f(r,r)
print('\n'.join(''.join(x)for x in o))
aditsu renunció porque SE es MALO
fuente