Drzewo mutacji mtDNA

13

Tło:

MtDNA jest częścią ludzkiego DNA przekazywaną z matki na dziecko i rzadko mutuje. Ponieważ dotyczy to wszystkich ludzi, możliwe jest stworzenie ogromnego drzewa, które wizualizuje, w jaki sposób wszyscy ludzie są ze sobą spokrewnieni poprzez macierzyńskie pochodzenie aż do hipotetycznej EVE. Każda mutacja w MtDNA, gdy rodzi się dziecko, tworzy nową pod-gałąź z gałęzi nadrzędnej w drzewie.

Dowiedz się więcej o mitochondrialnym DNA (mtDNA) tutaj: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Cel:

Wasz program ma listę liczników mutacji gałęzi drzewa mtDNA i powinien dostarczyć widok drzewa

Przykładowe dane wejściowe i wyjściowe:

Dane wejściowe to 3-kolumnowa tabela oddzielona średnikami z wierszem dla każdej gałęzi. Przykład:

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

Twój program powinien wyświetlać widok drzewa od lewej do prawej, w tym niektóre liczby oparte na danych wejściowych. W oparciu o przykładowe dane wejściowe jest to prawidłowe dane wyjściowe:

  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]

Dane wejściowe: szczegóły

Tabela wprowadzania nie jest sortowana w żadnej określonej kolejności. Jeśli losowo zmieniamy kolejność linii wejściowych, wynik powinien pozostać taki sam.

Każda linia na wejściu reprezentuje gałąź drzewa mtDNA lub hipotetyczną gałąź drzewa. Tabela wprowadzania może mieć dowolną liczbę wierszy.

Dane wejściowe: szczegóły - kolumna A (nazwa oddziału):

Pierwsza kolumna to rzeczywista nazwa oddziału. Nazwa dzieli linie wejściowe na 2 grupy rodzajów linii, które powinny być obsługiwane inaczej (wyjaśnione później):

  • Typ 1: Nazwa składa się z dowolnego 'przyrostkaNL
  • Typ 2: Nazwa nie składa się z żadnego 'przyrostka NL.

Nazwa może mieć długość do 20 znaków.

Dane wejściowe: szczegóły - kolumna B (nazwa oddziału nadrzędnego):

Druga kolumna zawiera wskaźnik do nazwy gałęzi nadrzędnej. Kilka linii (gałęzi) może dzielić tego samego rodzica. W tabeli wejściowej zawsze znajduje się dokładnie 1 odrębna nazwa gałęzi nadrzędnej, która wskazuje na rodzica, który nie jest reprezentowany wśród linii wejściowych, ta nazwa gałęzi nadrzędnej jest korzeniem drzewa. Na przykład wejście, które jest trzecia linia wskazując na root: mtEVE. Jeśli dane wejściowe mają więcej niż jeden katalog główny lub niekończące się pętle, jest to dane nieprawidłowe.

Dane wejściowe: szczegóły - kolumna C (liczba mutacji):

Trzecia kolumna to łączna liczba mutacji zliczonych przez daną gałąź od zera. Ludzki mtDNA nie zmutował więcej niż 100 razy w jednym wierszu od hipotetycznego korzenia matki (przodek człowieka / szympansa EVE), ale twój program powinien być w stanie obsłużyć 3-cyfrową liczbę mutacji, do 999.

Na podstawie danych wejściowych możesz obliczyć gałąź # unikalnych mutacji, odejmując jej # mutacji od jej rodzica # mutacji.

Wyjście: szczegóły

Twój program powinien wypisać 1 z 3 różnych komunikatów o błędach, jeśli dane wejściowe są nieprawidłowe zgodnie z opisem wejściowym.

  • Komunikat o błędzie 1, jeśli dane wejściowe mają więcej niż jeden katalog główny: ERROR: Multiple roots
  • Komunikat o błędzie 2, jeśli wejściowe wskaźniki nadrzędne zapętlają się: ERROR: Endless loop
  • Komunikat o błędzie 3, wszystko inne niepoprawne w danych wejściowych: ERROR: Invalid input

Jeśli dane wejściowe nie zawierają błędów, program powinien wypisać drzewo zgodnie z następującymi ograniczeniami: Każda linia składa się z 5 części A, B, C, D i E:

  • Odp .: 5 znaków, 3 mutacje wyrównane do prawej # mutacji, znak pionowej linii: |i 1 spacja
  • B: [maks. Liczba mutacji] szerokie drzewo znaków + 1 spacja
  • C: 20 znaków, nazwa gałęzi wyrównana do lewej
  • D: 5 znaków, 3 znaki wyrównane do prawej # unikatowych mutacji dla gałęzi otoczonej między [i ]. (Unikalne mutacje zostaną wyjaśnione poniżej).
  • E: 5 znaków, 3 znaki wyrównane do prawej maks. Całkowitej liczby mutacji dla tej gałęzi i wszystkich gałęzi potomnych zawartych między [i ].

Gałąź # unikalnych mutacji jest różnicą w # mutacjach, w których obecna gałąź ma od # mutacji, w których znajduje się gałąź macierzysta. Pierwszy wiersz jest pierwiastkiem i powinien być reprezentowany przez 0dla # mutacji i # unikalnych mutacji.

Wyjście: Szczegóły - kolejność / sortowanie linii

Jeśli dwie lub więcej gałęzi dzielą ten sam element nadrzędny, gałęzie są uporządkowane według maksymalnej liczby wszystkich mutacji w kolejności malejącej. W naszym przykładzie L0a1'4, L0a3oraz L0a2akcje jednostki dominującej: L0a.

W widoku drzewa kolejność od góry do dołu jest następująca: maksymalna liczba wszystkich mutacji w nawiasach: L0a3(53), L0a1'4(55), L0a2(60).

Jeśli dwie lub więcej gałęzi dzieli tę samą maksymalną liczbę mutacji na gałęziach potomnych, są one wyrównane pionowo i rozgałęzione od swojego rodzica z tego samego miejsca, kolejność linii między tymi gałęziami jest alfabetyczna.

Wyjście: Szczegóły - drzewo (część B)

Drzewo powinno być sporządzone ze znaków ASCII co następuje: └, ─, ┬, ┐, ├, │,♦

Logika drzewa polega na tym, że wszystkie mutacje powinny być reprezentowane. Gałąź z gałęzi nadrzędnej: ┬lub ┐reprezentuje 1 mutację. Dodatkowe unikalne mutacje w tej samej gałęzi są reprezentowane przez: ♦i muszą być wyrównane do lewej i umieszczone przed pierwszą gałęzią.

Podgałęzie są rozgałęzione od swojego rodzica wzdłuż osi x, a pozycję określa maksymalna liczba mutacji wśród wszystkich kolejnych gałęzi potomnych.

Jak wspomniano wcześniej, wejście ma 2 różne typy linii wejściowych. Wpisz 1 z dowolnymi znakami lub sufiksem NL w nazwie gałęzi, nie powinien wypełniać poziomej linii po prawej stronie linii, ale kończyć się ┐na ostatniej gałęzi. W tym przykładzie zastosowano go do następujących gałęzi:

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

Mamy nadzieję, że przykładowe dane wejściowe i wyjściowe odpowiedzą na wszelkie dodatkowe pytania dotyczące sposobu rysowania drzewa, uważając to za wyzwanie, aby zrozumieć logikę.

Inspiracja

Zapraszamy do wypróbowania mojej (nie golfowej) wersji javascript w poszukiwaniu inspiracji: http://artificial.se/DNA/mtDNAmutationTree3.html (brakuje jej kontroli błędów, a niektóre statystyki są dodawane, które nie są częścią tego konkretnego wyzwania) .

Kompletną wersję drzewa mtDNA [opartą na http://www.phylotree.org/ mtDNA Tree Build 16 (19 lutego 2014)] można znaleźć tutaj:

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

Plik danych użyty do pełnego drzewa:

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

To wyzwanie dla golfa.

code-golf ascii-art tree-traversal Plarsen
źródło
L0d1nie należy umieszczać wcześniej L0d2, zgodnie z regułą sortowania: „... kolejność malejąca ...”
guy777
L0a1'4nie jest (55), ale (39), L0a2nie jest (60), ale (47) ... Czy możesz to wyjaśnić?
guy777,
Zarówno L0d1, jak i L0d2 mają wartość 46, dlatego zastosowano kolejność alfabetyczną
Plarsen,
L0a4 55 i dziecko L0a1'4, więc maksymalne mutacje dla L0a1'4 wynoszą 55
Plarsen,
Mam kilka pytań: 1) Czy to prawdziwy projekt? Mam wrażenie, że coś takiego może być warte prawdziwych pieniędzy. 2) Jak uzyskałeś przykładowe wyjście? 3) Dlaczego część A ma 8 znaków zamiast 5? 4) Dlaczego część D ma 6 znaków zamiast 5? 5) Dlaczego „L0a1 NL” ma „4” w części D?
Aditsu zakończyło się, ponieważ SE to EVIL

Odpowiedzi:

6

Python 3, 925 bajtów

Tak, poniżej 1 KB! Prawdopodobnie nadal jest miejsce do gry w golfa ...

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 zrezygnowało, ponieważ SE jest ZŁEM
źródło