arbre de mutation de l'ADNmt

13

Contexte:

L'ADNmt fait partie de l'ADN humain transmis d'une mère à un enfant et il mute rarement. Étant donné que cela est vrai pour tous les humains, il est possible de créer un énorme arbre qui visualise comment tous les humains sont liés les uns aux autres à travers leur ascendance maternelle jusqu'à la veille EVE hypothétique. Chaque mutation dans l'ADNmt à la naissance d'un enfant crée une nouvelle sous-branche à partir de sa branche parent dans l'arbre.

Pour en savoir plus sur l'ADN mitochondrial (ADNmt) ici: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Objectif:

Votre programme reçoit une liste du nombre de mutations des branches d'arbre mtDNA et votre programme devrait en fournir une vue arborescente

Exemple d'entrée et de sortie:

L'entrée est une table séparée par des points-virgules à 3 colonnes avec une ligne pour chaque branche. Exemple:

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

Votre programme doit générer une arborescence de gauche à droite incluant certains nombres en fonction de l'entrée. Sur la base de l'exemple d'entrée, il s'agit d'une sortie valide:

  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]

Entrée: Détails

La table d'entrée n'est pas triée dans un ordre particulier. Si nous réorganisons au hasard les lignes d'entrée, la sortie doit rester la même.

Chaque ligne dans l'entrée représente une branche d'arbre mtDNA ou une branche d'arbre hypothétique. La table d'entrée peut avoir n'importe quel nombre de lignes.

Entrée: Détails - Colonne A (nom de la branche):

La première colonne est le nom réel de la branche. Le nom divise les lignes d'entrée en 2 groupes de types de lignes qui doivent être traités différemment (expliqués plus loin):

  • Type 1: le nom consiste en un 'ou le suffixeNL
  • Type 2: le nom ne se compose d'aucun 'ou du suffixe NL.

Le nom peut contenir jusqu'à 20 caractères.

Entrée: Détails - Colonne B (nom de la branche parent):

La deuxième colonne contient un pointeur sur le nom de la branche parent. Plusieurs lignes (branches) peuvent partager le même parent. Il y a toujours exactement 1 nom de branche parent distinct dans la table d'entrée qui pointe vers un parent qui n'est pas représenté parmi les lignes d'entrée, ce nom de branche parent est la racine de l'arborescence. Dans l'entrée exemple qui est la troisième ligne pointe vers la racine: mtEVE. Si l'entrée a plus d'une racine ou de boucles sans fin, il s'agit d'une entrée non valide.

Entrée: Détails - Colonne C (# de mutations):

La troisième colonne est le nombre total de mutations que cette branche particulière a eu à compter de la racine. L'ADNmt humain n'a pas muté plus de 100 fois en une seule ligne à partir de la racine maternelle hypothétique (ancêtre humain / chimpanzé EVE), mais votre programme devrait être capable de gérer un nombre de mutations à 3 chiffres, jusqu'à 999.

À partir de l'entrée, vous pouvez calculer une branche # de mutations uniques en soustrayant son # de mutations de son parent # de mutations.

Sortie: Détails

Votre programme devrait générer 1 sur 3 messages d'erreur différents si l'entrée n'est pas valide selon la description de l'entrée.

  • Message d'erreur 1, si l'entrée a plus d'une racine: ERROR: Multiple roots
  • Message d'erreur 2, si les pointeurs parent en entrée bouclent: ERROR: Endless loop
  • Message d'erreur 3, tout autre élément invalide concernant l'entrée: ERROR: Invalid input

Si l'entrée ne contient aucune erreur, votre programme doit sortir l'arborescence selon les contraintes suivantes: Chaque ligne se compose de 5 parties A, B, C, D et E:

  • A: 5 caractères, 3 caractères alignés à droite # de mutations, un caractère de ligne verticale: |et 1 espace vide
  • B: [max # de mutations] arbre large de caractères + 1 espace vide
  • C: 20 caractères, nom de branche aligné à gauche
  • D: 5 caractères, 3 caractères alignés à droite # de mutations uniques pour la branche encapsulée entre [et ]. (Des mutations uniques seront expliquées ci-dessous).
  • E: 5 caractères, 3 caractères alignés à droite max # de mutations totales pour cette branche et toutes les branches enfants encapsulées entre [et ].

Une branche # de mutations uniques est la différence entre le nombre de mutations de la branche actuelle et le nombre de mutations de sa branche parent. La première ligne est la racine et elle devrait être représentée avec 0pour # de mutations et # de mutations uniques.

Sortie: Détails - ordre / tri des lignes

Si deux sous-branches ou plus partagent le même parent, les branches sont ordonnées par le nombre maximum de sous-branches du nombre total de mutations dans l'ordre décroissant. Dans notre exemple L0a1'4, L0a3et L0a2partage les parents: L0a.

Dans l'arborescence, l'ordre de haut en bas est le nombre maximal de sous-branches du nombre total de mutations entre parenthèses: L0a3(53), L0a1'4(55), L0a2(60).

Si deux sous-branches ou plus partagent le même nombre maximal de mutations sur les branches enfants, elles sont alignées verticalement et ramifiées à partir de leur parent au même endroit, l'ordre des lignes entre ces sous-branches est alphabétique.

Sortie: Détails - arbre (partie B)

L'arbre doit être établi avec les caractères ascii suivants: └, ─, ┬, ┐, ├, │,♦

La logique de l'arbre est que toutes les mutations doivent être représentées. Une branche d'une branche parente: ┬ou ┐représente 1 mutation. Des mutations uniques supplémentaires sur la même branche sont représentées par: ♦et elles doivent être alignées à gauche et placées avant la première sous-branche.

Les sous-branches sont ramifiées à partir de leur parent le long de l'axe des x et la position est déterminée par le nombre maximal de mutations parmi toutes les branches enfants suivantes.

Comme indiqué précédemment, l'entrée a 2 types de lignes d'entrée différents. Tapez 1 avec n'importe quel caractère ou le suffixe NL dans le nom de la branche, ne doit pas remplir la ligne horizontale à l'extrême droite de leur ligne mais se termine par un ┐sur la dernière sous-branche. Dans l'exemple, il est appliqué aux branches suivantes:

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

J'espère que l'exemple d'entrée et de sortie répond à toutes les questions supplémentaires sur la façon dont l'arbre doit être dessiné, considérez que cela fait partie du défi de comprendre la logique.

Inspiration

Vous êtes invités à essayer ma version javascript (non-golfée) pour inspiration: http://artificial.se/DNA/mtDNAmutationTree3.html (il manque une vérification des erreurs, et certaines statistiques sont ajoutées qui ne font pas partie de ce défi particulier) .

Une version complète de l'arbre mtDNA [basée sur http://www.phylotree.org/ mtDNA tree Build 16 (19 février 2014)] peut être trouvée ici:

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

Le fichier de données utilisé pour l'arborescence complète:

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

Il s'agit d'un défi de code-golf.

code-golf ascii-art tree-traversal Plarsen
la source
L0d1ne doit pas être placé avant L0d2, selon la règle de tri: "... ordre décroissant ..."
guy777
L0a1'4n'est pas (55) mais (39), L0a2n'est pas (60) mais (47) ... Pourriez-vous clarifier cela?
guy777
L0d1 et L0d2 sont tous deux 46, donc l'ordre alphabétique est appliqué
Plarsen
L0a4 55 et un enfant de L0a1'4 donc les mutations maximales pour L0a1'4 sont 55
Plarsen
J'ai quelques questions: 1) Est-ce un vrai projet? J'ai l'impression que quelque chose comme ça pourrait valoir de l'argent réel. 2) Comment avez-vous obtenu l'exemple de sortie? 3) Pourquoi la partie A a-t-elle 8 caractères au lieu de 5? 4) Pourquoi la partie D a-t-elle 6 caractères au lieu de 5? 5) Pourquoi "L0a1 NL" a-t-il "4" dans la partie D?
aditsu quitte car SE est EVIL

Réponses:

6

Python 3, 925 octets

Oui, moins de 1 Ko! Probablement encore de la place pour le 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 quitte parce que SE est MAL
la source