мутационное дерево мтДНК

13

Фон:

МтДНК - это часть ДНК человека, которая передается от матери ребенку и редко мутирует. Поскольку это верно для всех людей, можно создать огромное дерево, которое визуализирует, как все люди связаны друг с другом через их материнское происхождение вплоть до гипотетического EVE. Каждая мутация в MtDNA при рождении ребенка создает новую дочернюю ветвь из его родительской ветви в дереве.

Узнайте больше о митохондриальной ДНК (мтДНК) здесь: https://en.wikipedia.org/wiki/Mitochondrial_DNA

Задача:

Ваша программа получает список количества мутаций в ветвях дерева мтДНК, и ваша программа должна представить его в виде дерева

Пример ввода и вывода:

Входные данные представляют собой таблицу из трех столбцов, разделенных точкой с запятой, со строкой для каждой ветви. Пример:

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

Ваша программа должна выводить вид дерева слева направо, включая некоторые числа, основанные на вводе. Исходя из примера ввода, это допустимый вывод:

  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]

Вход: детали

Входная таблица не сортируется ни в каком конкретном порядке. Если мы случайным образом переупорядочим входные строки, выходные данные должны остаться прежними.

Каждая строка на входе представляет ветвь дерева мтДНК или гипотетическую ветвь дерева. Входная таблица может содержать любое количество строк.

Ввод: Подробности - столбец A (название филиала):

Первый столбец - это фактическое имя ветви. Имя делит входные строки на 2 группы типов линий, которые должны обрабатываться по-разному (объяснено позже) друг от друга:

  • Тип 1: Имя состоит из любого 'или суффиксаNL
  • Тип 2: Имя не состоит из какого-либо 'или суффикса NL.

Имя может быть длиной до 20 символов.

Ввод: Подробности - столбец B (имя родительской ветви):

Второй столбец содержит указатель на имя родительской ветви. Несколько строк (ветвей) могут совместно использовать одного и того же родителя. Во входной таблице всегда есть ровно 1 отдельное имя родительской ветви, которое указывает на родителя, который не представлен среди входных строк, это имя родительской ветви является корнем для дерева. В примере входные данные, это третья строка, указывающая на корень:mtEVE . Если вход имеет более одного корня или бесконечные циклы, это неверный ввод.

Ввод: Подробности - Столбец C (количество мутаций):

Третий столбец - это общее количество мутаций, которое имеет конкретная ветвь, считая от корня. МтДНК человека не мутировала более 100 раз в одной строке от гипотетического материнского корня (EVE предка человека / шимпанзе), но ваша программа должна быть способна обрабатывать 3-значное число # мутаций, вплоть до 999.

Исходя из входных данных, вы можете вычислить ветвь # уникальных мутаций, вычтя количество # мутаций из числа родительских # мутаций.

Выход: детали

Ваша программа должна выводить 1 из 3 различных сообщений об ошибках, если ввод неверен в соответствии с описанием ввода.

  • Сообщение об ошибке 1, если вход имеет более одного корня: ERROR: Multiple roots
  • Сообщение об ошибке 2, если входные родительские указатели зацикливаются: ERROR: Endless loop
  • Сообщение об ошибке 3, что-либо еще недопустимо в отношении ввода: ERROR: Invalid input

Если входные данные не содержат ошибок, ваша программа должна вывести дерево в соответствии со следующими ограничениями: Каждая строка состоит из 5 частей A, B, C, D и E:

  • A: 5 символов, 3 символа с выравниванием по правому краю # мутаций, символ вертикальной линии: |и 1 пробел
  • B: [макс. Количество мутаций] символов широкое дерево + 1 пробел
  • C: 20 символов, выровненное по левому краю название ветви
  • D: 5 символов, 3 символа по правому краю # уникальных мутаций для ветви, инкапсулированной между [и ]. (Уникальные мутации будут объяснены ниже).
  • E: 5 символов, 3 символа, выровненные по правому краю, максимальное количество мутаций для этой ветви и всех дочерних ветвей, заключенных между [и ].

Ветвь # уникальных мутаций представляет собой разницу в количестве мутаций, которые имеет текущая ветвь, с количеством мутаций, которые имеет родительская ветвь. Первая строка - это корень, и она должна быть представлена0 для # мутаций и # уникальных мутаций.

Вывод: Подробности - строка заказа / сортировки

Если две или более дочерние ветви совместно используют одного и того же родителя, ветви упорядочиваются по максимальному количеству мутаций в дочерних ветвях в порядке убывания. В нашем примере L0a1'4, L0a3и L0a2акции материнской компании : L0a.

В древовидной структуре порядок сверху вниз таков: максимальное количество мутаций в скобках: количество ветвей: L0a3(53), L0a1'4(55),L0a2 (60).

Если две или несколько дочерних ветвей имеют одинаковое максимальное количество мутаций в дочерних ветвях, они выровнены по вертикали и разветвлены от своего родителя в одном месте, упорядочение строк среди этих дочерних ветвей происходит в алфавитном порядке.

Вывод: детали - дерево (часть B)

Дерево должно быть обращено с персонажами следующего ASCii: └, ─, ┬, ┐, ├, │,♦

Логика дерева заключается в том, что все мутации должны быть представлены. Ветвь от родительской ветви: ┬или ┐представляет 1 мутацию. Дополнительные уникальные мутации в той же ветви представлены: ♦и они должны быть выровнены по левому краю и помещены перед первой дочерней ветвью.

Подветвия разветвляются от своего родителя вдоль оси x, и положение определяется максимальным числом мутаций среди всех последующих дочерних ветвей.

Как указывалось ранее, вход имеет 2 разных типа строк ввода. Тип 1 с любыми символами 'или суффиксом NL в имени ветви не должен заполнять горизонтальную линию в крайнем правом положении на их строке, а должен заканчиваться буквой a ┐в последней дочерней ветви. В примере он применяется к следующим веткам:

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

Надеемся, что пример ввода и вывода отвечает на любые дополнительные вопросы о том, как должно быть построено дерево, считая это частью задачи по выяснению логики.

вдохновение

Вы можете попробовать мою версию JavaScript (без игры в гольф) для вдохновения: http://artificial.se/DNA/mtDNAmutationTree3.html (в ней отсутствует проверка ошибок, и добавлена ​​некоторая статистика, которая не является частью этой конкретной задачи) ,

Полная версия дерева мтДНК [на основе http://www.phylotree.org/ дерева мтДНК, сборка 16 (19 февраля 2014 г.)] может быть найдена здесь:

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

Файл данных, используемый для полного дерева:

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

Это вызов для игры в гольф.

code-golf ascii-art tree-traversal Plarsen
источник
L0d1не следует размещать раньше L0d2, согласно правилу сортировки: «... в порядке убывания ...»
guy777
L0a1'4не (55), но (39), L0a2не (60), но (47) ... Не могли бы вы уточнить это?
guy777
L0d1 и L0d2 оба 46, поэтому применяется алфавитный порядок
Plarsen
L0a4 55 и потомок L0a1'4, поэтому максимальные мутации для L0a1'4 - 55
Пларсен
У меня есть несколько вопросов: 1) Это настоящий проект? У меня сложилось впечатление, что что-то подобное может стоить реальных денег. 2) Как вы получили пример вывода? 3) Почему часть А имеет 8 символов вместо 5? 4) Почему часть D имеет 6 символов вместо 5? 5) Почему "L0a1 NL" имеет "4" в части D?
Aditsu уйти, потому что SE зла

Ответы:

6

Python 3, 925 байт

Уу, под 1 кб! Вероятно, еще есть место для игры в гольф ...

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))
уйти, потому что SE это зло
источник