pohon mutasi mtDNA

13

Latar Belakang:

MtDNA adalah bagian dari DNA manusia yang ditularkan dari ibu ke anak dan jarang bermutasi. Karena ini berlaku untuk semua manusia, dimungkinkan untuk membuat pohon besar yang memvisualisasikan bagaimana semua manusia berhubungan satu sama lain melalui nenek moyang ibu mereka sepanjang perjalanan kembali ke EVE hipotetis. Setiap mutasi dalam MtDNA ketika seorang anak dilahirkan menciptakan cabang pembantu baru dari cabang induknya di pohon.

Cari tahu lebih lanjut tentang DNA Mitochondrial (mtDNA) di sini: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Objektif:

Program Anda disajikan daftar jumlah mutasi cabang pohon mtDNA dan program Anda akan menampilkannya

Contoh input dan output:

Input adalah tabel terpisah semi-kolon 3 kolom dengan garis untuk setiap cabang. Contoh:

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

Program Anda harus menampilkan tampilan hierarki kiri-ke-kanan termasuk beberapa angka berdasarkan input. Berdasarkan contoh input, ini adalah output yang valid:

  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]

Input: Detail

Tabel input tidak diurutkan dalam urutan tertentu. Jika kita secara acak menyusun ulang jalur input, output harus tetap sama.

Setiap baris dalam input mewakili cabang pohon mtDNA atau cabang pohon hipotetis. Tabel input dapat berupa jumlah panjang baris.

Input: Detail - Kolom A (nama cabang):

Kolom pertama adalah nama cabang aktual. Nama membagi garis input menjadi 2 kelompok tipe garis yang harus ditangani berbeda (dijelaskan nanti) satu sama lain:

  • Tipe 1: Nama terdiri dari sembarang 'atau akhiranNL
  • Tipe 2: Nama tidak mengandung sembarang 'atau akhiran NL.

Panjangnya bisa hingga 20 karakter.

Input: Detail - Kolom B (nama cabang induk):

Kolom kedua berisi pointer ke nama cabang induk. Beberapa baris (cabang) dapat berbagi induk yang sama. Selalu ada tepat 1 nama cabang induk yang berbeda di tabel input yang menunjuk ke induk yang tidak terwakili di antara baris input, bahwa nama cabang induk adalah root untuk struktur pohon. Dalam contoh input, itu adalah baris ketiga yang menunjuk ke root:mtEVE . Jika input memiliki lebih dari satu root, atau loop tanpa akhir, itu adalah input yang tidak valid.

Input: Detail - Kolom C (# mutasi):

Kolom ketiga adalah jumlah total mutasi yang telah dihitung cabang dari akar. MtDNA manusia belum bermutasi lebih dari 100 kali dalam satu baris dari akar keibuan hipotetis (EVE leluhur manusia / simpanse), tetapi program Anda harus mampu menangani 3 digit # mutasi, hingga 999.

Dari input Anda dapat menghitung cabang # mutasi unik dengan mengurangkan # mutasi dari # mutasi induknya.

Output: Detail

Program Anda harus menampilkan 1 dari 3 pesan kesalahan yang berbeda jika input tidak valid sesuai dengan deskripsi input.

  • Pesan kesalahan 1, jika input memiliki lebih dari satu root: ERROR: Multiple roots
  • Pesan kesalahan 2, jika pointer orangtua input loop: ERROR: Endless loop
  • Pesan kesalahan 3, hal lain yang tidak valid tentang input: ERROR: Invalid input

Jika input tidak mengandung kesalahan, program Anda harus menampilkan pohon sesuai dengan batasan berikut: Setiap baris terdiri dari 5 bagian A, B, C, D, dan E:

  • A: 5 karakter, 3 karakter # mutasi yang diluruskan kanan, karakter garis vertikal: |dan 1 spasi kosong
  • B: [maks # mutasi] karakter pohon lebar + 1 spasi kosong
  • C: 20 karakter, nama cabang selaras kiri
  • D: 5 karakter, 3 karakter rata kanan # mutasi unik untuk cabang yang dienkapsulasi antara [dan ]. (Mutasi unik akan dijelaskan di bawah).
  • E: 5 karakter, 3 karakter max-aligned max maksimum dari total mutasi untuk cabang ini dan semua cabang anak dienkapsulasi antara [dan ].

Cabang # mutasi unik adalah perbedaan dalam # mutasi yang dimiliki cabang saat ini dari # mutasi yang dimiliki cabang induknya. Baris pertama adalah root dan harus diwakili dengan 0# mutasi dan # mutasi unik.

Output: Detail - urutan / penyortiran baris

Jika dua atau lebih cabang pembantu berbagi induk yang sama, cabang-cabang diperintahkan oleh maksimum # cabang pembantu dari total mutasi dalam urutan menurun. Dalam contoh kita L0a1'4, L0a3dan L0a2saham induk: L0a.

Pada tampilan hierarki urutan dari atas ke bawah adalah, maksimum # cabang dari total mutasi dalam tanda kurung: L0a3(53), L0a1'4(55), L0a2(60).

Jika dua atau lebih sub-cabang memiliki # mutasi maksimum yang sama pada cabang anak, mereka akan disejajarkan secara vertikal dan bercabang dari induknya dari tempat yang sama, urutan baris di antara cabang-cabang tersebut menurut abjad.

Output: Detail - pohon (bagian B)

Pohon itu harus digambar dengan karakter ascii berikut: └, ─, ┬, ┐, ├, │,♦

Logikanya pohon adalah bahwa semua mutasi harus diwakili. Cabang dari cabang induk: ┬atau ┐mewakili 1 mutasi. Mutasi unik tambahan pada cabang yang sama diwakili oleh: ♦dan mereka harus dibariskan kiri dan ditempatkan sebelum cabang pertama.

Sub-cabang bercabang dari induknya sepanjang sumbu-x dan posisinya ditentukan oleh # mutasi maksimum di antara semua cabang anak berikutnya.

Seperti yang ditunjukkan sebelumnya input memiliki 2 jenis jalur input yang berbeda. Ketik 1 dengan karakter apa pun atau akhiran NL dalam nama cabang, tidak boleh mengisi garis horizontal ke kanan di baris mereka, tetapi akhiri dengan huruf a ┐pada cabang pembantu terakhir. Dalam contoh ini diterapkan ke cabang-cabang berikut:

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

Mudah-mudahan contoh input dan output menjawab pertanyaan tambahan tentang bagaimana pohon itu harus ditarik, anggap itu bagian dari tantangan untuk mencari tahu logika.

Inspirasi

Anda dipersilakan untuk mencoba versi javascript (tidak-golf) saya untuk mendapatkan inspirasi: http://artificial.se/DNA/mtDNAmutationTree3.html (tidak memiliki pengecekan kesalahan, dan beberapa statistik ditambahkan yang bukan bagian dari tantangan khusus ini) .

Versi lengkap mtDNA-tree [berdasarkan http://www.phylotree.org/ mtDNA tree Build 16 (19 Feb 2014)] dapat ditemukan di sini:

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

File data yang digunakan untuk pohon lengkap:

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

Ini adalah tantangan kode-golf.

code-golf ascii-art tree-traversal Plarsen
sumber
L0d1tidak boleh ditempatkan sebelumnya L0d2, sesuai dengan aturan penyortiran: "... urutan menurun ..."
guy777
L0a1'4bukan (55) tetapi (39), L0a2bukan (60) tetapi (47) ... Bisakah Anda menjelaskannya?
guy777
L0d1 dan L0d2 sama-sama 46, oleh karena itu urutan abjad diterapkan
Plarsen
L0a4 55 dan anak L0a1'4 sehingga mutasi maksimum untuk L0a1'4 adalah 55
Plarsen
Saya punya beberapa pertanyaan: 1) Apakah ini proyek nyata? Saya mendapat kesan bahwa sesuatu seperti ini bisa bernilai uang aktual. 2) Bagaimana Anda mendapatkan contoh output? 3) Mengapa bagian A memiliki 8 karakter, bukan 5? 4) Mengapa bagian D memiliki 6 karakter, bukan 5? 5) Mengapa "L0a1 NL" memiliki "4" di bagian D?
Aditsu berhenti karena SE adalah JAHAT

Jawaban:

6

Python 3, 925 byte

Yay, di bawah 1 KB! Mungkin masih ada ruang untuk bermain 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 berhenti karena SE adalah JAHAT
sumber