mtDNA-Mutationsbaum

13

Hintergrund:

MtDNA ist ein Teil der menschlichen DNA, die von einer Mutter an ein Kind weitergegeben wird und selten mutiert. Da dies für alle Menschen zutrifft, ist es möglich, einen riesigen Baum zu erstellen, der visualisiert, wie alle Menschen durch ihre mütterliche Abstammung bis zum hypothetischen EVE miteinander verwandt sind. Jede Mutation in der MtDNA, wenn ein Kind geboren wird, erstellt einen neuen Unterzweig aus dem übergeordneten Zweig im Baum.

Weitere Informationen zur mitochondrialen DNA (mtDNA) finden Sie hier: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Zielsetzung:

Ihrem Programm wird eine Liste mit der Anzahl der Mutationen von mtDNA-Ästen bereitgestellt, und Ihr Programm sollte eine Baumansicht davon liefern

Beispiel Ein- und Ausgabe:

Die Eingabe ist eine durch Semikolons getrennte Tabelle mit drei Spalten und einer Zeile für jeden Zweig. Beispiel:

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

Ihr Programm sollte eine Strukturansicht von links nach rechts mit einigen Zahlen basierend auf der Eingabe ausgeben. Basierend auf der Beispieleingabe ist dies eine gültige Ausgabe:

  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]

Eingabe: Details

Die Eingangstabelle ist nicht in einer bestimmten Reihenfolge sortiert. Wenn wir die Eingabezeilen zufällig neu anordnen, sollte die Ausgabe dieselbe bleiben.

Jede Zeile in der Eingabe repräsentiert einen mtDNA-Baumzweig oder einen hypothetischen Baumzweig. Die Eingabetabelle kann eine beliebige Anzahl von Zeilen enthalten.

Eingabe: Details - Spalte A (Zweigname):

Die erste Spalte ist der tatsächliche Filialname. Der Name unterteilt die Eingabezeilen in zwei Gruppen von Zeilentypen, die unterschiedlich (später erklärt) behandelt werden sollen:

  • Typ 1: Name besteht aus einem 'oder dem SuffixNL
  • Typ 2: Name besteht nicht aus einem 'oder dem Suffix NL.

Der Name kann bis zu 20 Zeichen lang sein.

Eingabe: Details - Spalte B (Name des übergeordneten Zweigs):

Die zweite Spalte enthält einen Zeiger auf den übergeordneten Zweignamen. Mehrere Zeilen (Zweige) können dasselbe übergeordnete Element verwenden. In der Eingabetabelle befindet sich immer genau 1 eindeutiger übergeordneter Zweigname, der auf einen übergeordneten Zweig verweist, der nicht in den Eingabezeilen dargestellt wird. Dieser übergeordnete Zweigname ist der Stamm des Baums. In dem Beispiel , das die dritte Eingangsleitung mit der Wurzel zeigt ist: mtEVE. Wenn die Eingabe mehr als eine Wurzel oder Endlosschleifen enthält, handelt es sich um eine ungültige Eingabe.

Eingabe: Details - Spalte C (Anzahl Mutationen):

Die dritte Spalte gibt die Gesamtzahl der Mutationen an, die ein bestimmter Zweig von der Wurzel aus gezählt hat. Menschliche mtDNA hat nicht mehr als 100-mal in einer einzigen Zeile von der hypothetischen Mutterwurzel (Mensch / Schimpanse-Vorfahr EVE) mutiert, aber Ihr Programm sollte in der Lage sein, 3-stellige Mutationen (bis zu 999) zu verarbeiten.

Aus der Eingabe können Sie eine Verzweigungsanzahl eindeutiger Mutationen berechnen, indem Sie die Anzahl der Mutationen von der übergeordneten Anzahl der Mutationen abziehen.

Ausgabe: Details

Ihr Programm sollte 1 von 3 verschiedenen Fehlermeldungen ausgeben, wenn die Eingabe gemäß der Eingabebeschreibung ungültig ist.

  • Fehlermeldung 1, wenn die Eingabe mehr als eine Wurzel hat: ERROR: Multiple roots
  • Fehlermeldung 2, wenn der übergeordnete Eingabezeiger Schleifen durchläuft: ERROR: Endless loop
  • Fehlermeldung 3, alles andere an der Eingabe ungültig: ERROR: Invalid input

Wenn die Eingabe keine Fehler enthält, sollte Ihr Programm den Baum gemäß den folgenden Einschränkungen ausgeben: Jede Zeile besteht aus 5 Teilen A, B, C, D und E:

  • A: 5 Zeichen, 3 Zeichen |rechtsbündige Anzahl von Mutationen, ein vertikales Linienzeichen : und 1 Leerzeichen
  • B: [max. Anzahl Mutationen] Zeichenbreite + 1 Leerzeichen
  • C: 20 Zeichen, linksbündiger Zweigname
  • D: 5 Zeichen, 3 Zeichen rechtsbündige Anzahl eindeutiger Mutationen für den zwischen [und eingeschlossenen Zweig ]. (Eindeutige Mutationen werden unten erklärt).
  • E: 5 Zeichen, maximal 3 Zeichen rechtsbündig für diesen Zweig und alle untergeordneten Zweige, die zwischen [und eingeschlossen sind ].

Ein Zweig mit eindeutigen Mutationen ist der Unterschied zwischen der Anzahl der Mutationen des aktuellen Zweigs und der Anzahl der Mutationen des übergeordneten Zweigs. Die erste Zeile ist die Wurzel und sollte mit dargestellt werden0 # der Mutationen und # der eindeutigen Mutationen dargestellt werden.

Ausgabe: Details - Zeilenreihenfolge / Sortierung

Wenn zwei oder mehr Unterzweige dasselbe übergeordnete Element teilen, werden die Zweige nach der maximalen Anzahl von Mutationen in absteigender Reihenfolge der Unterzweige sortiert. In unserem Beispiel L0a1'4, L0a3und L0a2Aktien der Mutter: L0a.

In der Baumansicht ist die Reihenfolge von oben nach unten die maximale Anzahl von Unterverzweigungen in Klammern: L0a3(53), L0a1'4(55), L0a2(60).

Wenn zwei oder mehr Unterzweige dieselbe maximale Anzahl von Mutationen in untergeordneten Zweigen aufweisen, werden sie vertikal ausgerichtet und von ihrem übergeordneten Zweig an derselben Stelle verzweigt. Die Zeilenreihenfolge zwischen diesen Unterzweigen ist alphabetisch.

Ausgabe: Details - Baum (Teil B)

Der Baum sollte mit den folgenden ASCII - Zeichen gezogen werden: └, ─, ┬, ┐, ├, │,♦

Die Logik des Baumes ist, dass alle Mutationen dargestellt werden sollen. Ein Zweig von einem Elternzweig: ┬oder steht ┐für 1 Mutation. Zusätzliche eindeutige Mutationen auf demselben Zweig werden dargestellt durch: ♦und sie müssen linksbündig ausgerichtet und vor dem ersten Unterzweig platziert werden.

Unterzweige werden von ihrem Elternteil entlang der x-Achse verzweigt und die Position wird durch die maximale Anzahl von Mutationen unter allen nachfolgenden untergeordneten Zweigen bestimmt.

Wie zuvor angedeutet, hat der Eingang 2 verschiedene Arten von Eingangsleitungen. Geben Sie 1 mit beliebigen 'Zeichen oder dem NL-Suffix im Zweignamen ein, und füllen Sie die horizontale Linie ganz rechts in ihrer Linie nicht aus, sondern enden Sie mit einem ┐in dem letzten Unterzweig. Im Beispiel wird es auf die folgenden Zweige angewendet:

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

Hoffentlich beantwortet die Beispieleingabe und -ausgabe zusätzliche Fragen dazu, wie der Baum gezeichnet werden soll. Betrachten Sie es als Teil der Herausforderung, die Logik herauszufinden.

Inspiration

Sie können gerne meine (nicht Golf spielende) Javascript-Version ausprobieren, um sich inspirieren zu lassen: http://artificial.se/DNA/mtDNAmutationTree3.html (es fehlt Fehlerprüfung, und einige Statistiken hinzugefügt wird, die nicht Teil dieser besonderen Herausforderung ist) .

Eine vollständige Version des mtDNA-Baums [basierend auf http://www.phylotree.org/ mtDNA-Baum Build 16 (19. Februar 2014)] finden Sie hier:

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

Die für den vollständigen Baum verwendete Datendatei:

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

Dies ist eine Code-Golf-Herausforderung.

code-golf ascii-art tree-traversal Plarsen
quelle
L0d1sollte nicht vorher platziert werden L0d2, gemäß der Sortierregel: "... absteigende Reihenfolge ..."
guy777
L0a1'4ist nicht (55) sondern (39), L0a2ist nicht (60) sondern (47) ... Könnten Sie das klären?
guy777
L0d1 und L0d2 sind beide 46, daher wird die alphabetische Reihenfolge angewendet
Plarsen
L0a4 55 und ein Kind von L0a1'4. Die maximale Mutation für L0a1'4 beträgt 55
Plarsen
Ich habe ein paar Fragen: 1) Ist das ein echtes Projekt? Ich habe den Eindruck, dass so etwas echtes Geld wert sein könnte. 2) Wie haben Sie die Beispielausgabe erhalten? 3) Warum hat Teil A 8 statt 5 Zeichen? 4) Warum hat Teil D 6 anstatt 5 Zeichen? 5) Warum hat "L0a1 NL" in Teil D "4"?
Aditsu

Antworten:

6

Python 3, 925 Bytes

Ja, unter 1 KB! Wahrscheinlich noch Platz zum Golfen ...

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
quelle