Формат Newick

В математике формат дерева Ньюика (или нотация Ньюика или формат дерева Нью-Гэмпшира ) представляет собой способ представления теоретико-графовых деревьев с помощью длины краев в скобках и запятых. Он был принят Джеймсом Арчи, Уильямом Х. Дей, Джозефом Фельзенштейном, Уэйном Мэддисоном, Кристофером Мичемом, Ф. Джеймсом Рольфом и Дэвидом Своффордом на двух встречах в 1986 году, второй из который находился в ресторане Newick's в Дувре, Нью-Гэмпшир, США. Принятый формат является обобщением формата, разработанного Мичемом в 1984 году для первых программ рисования деревьев в пакете Felsenstein PHYLIP.

Содержание

• 1 Примеры
• 2 Корневые, некорневые и бинарные деревья
• 3 Грамматика
  • 3.1 Узлы грамматики
  • 3.2 Правила грамматики
  • 3.3 Примечания
• 4 Диалекты
  • 4.1 Нью-Хэмпширский формат X
  • 4.2 Расширенный Newick
  • 4.3 Rich Формат Ньюика
  • 4.4 Специальные расширения
• 5 Визуализация
• 6 См. Также
• 7 Ссылки
• 8 Внешние ссылки

Примеры

Следующее дерево:

может быть представлен в формате Ньюика несколькими способами

(,, (,)); никакие узлы не названы (A, B, (C, D)); листовые узлы называются (A, B, (C, D) E) F; все узлы имеют имена (: 0,1,: 0,2, (: 0,3,: 0,4): 0,5); все узлы, кроме корневого, имеют расстояние до родительского (: 0,1,: 0,2, (: 0,3,: 0,4): 0,5): 0,0; все имеют расстояние до родителя (A: 0,1, B: 0,2, (C: 0,3, D: 0,4): 0,5); расстояния и названия листьев (популярно) (A: 0,1, B: 0,2, (C: 0,3, D: 0,4) E: 0,5) F; расстояния и все названия ((B: 0,2, (C: 0,3, D: 0,4) E: 0,5) A: 0,1) F; дерево с корнем на листовом узле (редко)

Формат Ньюика обычно используется для таких инструментов, как PHYLIP и является минимальным определением для филогенетического дерева.

с корнями, без корней, и бинарные деревья

Когда некорневое дерево представлено в нотации Ньюика, произвольный узел выбирается в качестве его корня. Независимо от того, является ли оно корневым или некорневым, обычно представление дерева имеет корень на внутреннем узле, и редко (но законно) укоренить дерево на листовом узле.

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

Грамматика

Грамматика для синтаксического анализа формата Ньюика (примерно на основе):

Узлы грамматики

Дерево : полный входной формат Ньюика для одиночное дерево Поддерево : внутренний узел (и его потомки) или листовой узел Лист : узел без потомков Внутренний : узел и его один или несколько Потомки BranchSet : набор из одной или нескольких ветвей Branch : край дерева и его дочернее поддерево. Имя : имя узла Длина : длина ребра дерева.

Правила грамматики

Примечание, «|» разделяет альтернативы.

Дерево → Поддерево ";" | Филиал ";" Поддерево → Лист | ВнутреннийЛист → ИмяВнутренний → "(" BranchSet ")" Имя BranchSet → Branch | Ветвь "," BranchSetВетвь → ПоддеревоДлинаИмя → пусто | строка Длина → пусто | ":" число

Пробелы (пробелы, табуляторы, символы возврата каретки и переводы строки) в числе запрещены. Пробелы в строке часто запрещены. Пробелы в других местах игнорируются. Иногда строка Имя должна иметь указанную фиксированную длину; в противном случае знаки препинания из грамматики (точка с запятой, круглые скобки, запятая и двоеточие) запрещены. Дерево-->Ветвь ";" production делает все дерево потомком из ниоткуда, что может быть бессмысленным, а иногда и запрещено.

Обратите внимание, что когда дерево, имеющее более одного листа, коренится в одном из его листьев, что редко встречается на практике, корневой лист определяется как Внутренний узел выше грамматики. Обычно корневой узел, помеченный как Internal, следует рассматривать как лист тогда и только тогда, когда он имеет ровно одну Branch в его BranchSet . Можно создать грамматику, которая формализует это различие, заменив указанное выше правило производства Tree на

Tree → RootLeaf ";" | RootInternal ";" | Филиал ";" RootLeaf → Имя | "(" Branch ")" NameRootInternal → "(" Branch "," BranchSet ") «Имя

Первая продукция RootLeaf предназначена для дерева с ровно одним листом. Вторая продукция RootLeaf предназначена для укоренения дерева на одном из двух или более листьев.

Примечания

• Строка без кавычек не может содержать пробелов, круглых скобок, квадратных скобок, одинарных_цифров, двоеточий, точек с запятой или запятых. Знаки подчеркивания в строках без кавычек преобразуются в пробелы. Строку
• A также можно заключить в кавычки, заключив ее в одинарные кавычки. Одиночные кавычки в исходной строке представлены как два последовательных символа одинарных кавычек.
• Пробелы могут появляться где угодно, кроме строки без кавычек или Длина
• Новые строки могут появляться где угодно, кроме внутри строки или Длина .
• Комментарии заключаются в квадратные скобки. Они могут появляться везде, где разрешены символы новой строки. Комментарии, начинающиеся с , обычно генерируются компьютером для дополнительных данных. Некоторые диалекты допускают вложенные комментарии.

Диалекты

Нью-Хэмпширский формат X

Нью-гэмпширский X (NHX) формат является расширением Newick, которое добавляет данные значения ключа (дупликация гена и т. д.) в узлы Ньюика. Это делается путем помещения дополнительных данных в скобки [NHX: key = value:...]в метках узлов. Скобки используются потому, что они представляют комментарии в формате файла Nexus, поэтому любой синтаксический анализатор, не понимающий эту дополнительную информацию, проигнорирует их.

Расширенный Newick

Хотя стандартный Newick нотация ограничена филогенетическими деревьями, Extended Newick (Perl Bio :: PhyloNetwork) может использоваться для кодирования явных филогенетических сетей. В филогенетической сети, которая является обобщением филогенетического дерева, узел либо представляет событие дивергенции (кладогенез ), либо событие ретикуляции, такое как гибридизация, интрогрессия, горизонтальный (латеральный) перенос гена или рекомбинация. Узлы, которые представляют событие ретикуляции, дублируются, аннотируются путем введения символа # в формате Ньюика и нумеруются последовательно (с использованием целочисленных значений, начинающихся с 1).

Например, если лист Y является продуктом гибридизации (x) между линиями, ведущими к C и D в дереве выше,

можно выразить эту ситуацию, определив два дерева в стандартной нотации Ньюика

(A, B, ((C, Y) c, D) e) f; и (A, B, (C, (Y, D) d) e) f; по стандарту Ньюика, все узлы названы (внутренние узлы в нижнем регистре, листья в верхнем регистре)

или в расширенной нотации Ньюика

(A, B, ((C, (Y) x # 1) c, (x # 1, D) d) e) f; расширенный Newick, все узлы названы; 1 - целое число, идентифицирующее гибридный узел x

. x # 1здесь - гибридный узел. Когда он будет нарисован, он будет объединен программой в один узел. Приведенные выше производственные правила изменены следующим образом для маркировки гибридных узлов (в общем, узлов, представляющих события ретикуляции):

Leaf → NameHybridHybrid → пусто | «#» Тип целое число - Часть #i является обязательным идентификатором для гибридного узла Тип → пусто | строка - тип ретикуляции, например, H = гибридизация, LGT = латеральный перенос гена, R = рекомбинация.

Расширенный Newick обратно совместим: гибридный узел будет просто интерпретироваться как несколько узлов со странными названиями для устаревших синтаксических анализаторов.

Формат Rich Newick

Формат Rich Newick, также известный как Rice формат Newick, является дальнейшим расширением Extended Newick. Добавлена ​​поддержка:

• некорневых филогений. Это просто делается путем записи дерева без корня как обычно (т. Е. Выбора произвольного корня в двоичной точке ветвления) и добавления к строке префикса [U]. [R], с другой стороны, можно использовать для принудительного создания корневого дерева.
• Значения и вероятности начальной загрузки. Это делается путем добавления дополнительных полей : [bootstrap]: [prob]после длины; поля можно оставить пустыми, пока присутствуют двоеточия. Это может быть обратно несовместимо.

Специальные расширения

Некоторые другие программы, такие как NWX, используют комментарии, начинающиеся с , для специального кодирования дополнительной информации:

• MrBayes и BEAST добавляют в узлы дополнительную информацию, такую ​​как вероятность, длина в годах, стандартное отклонение значений. Они также используют [% U].

Визуализация

Для визуализации данных дерева Ньюика было опубликовано множество инструментов. Конкретные примеры включают набор инструментов ETE («Среда для исследования дерева») и T-REX. Пакеты филогенетического программного обеспечения, такие как SplitsTree и средство просмотра дерева Dendroscope, а также онлайн-инструмент просмотра дерева IcyTree могут обрабатывать стандартные и расширенные нотации Ньюика, в то время как филогенетические сетевое программное обеспечение PhyloNet использует форматы Extended Newick и Rich Newick.

См. Также

• phyloXML
• T-REX (Webserver) позволяет обрабатывать филогенетические деревья и сети в формате Newick.
• Smart Game Format - это приложение формата Newick и широко используется для записи настольных игр.

Литература

Внешние ссылки

• Филограмма евтерийских млекопитающих Миямото и Гудмана Пример большой филограммы с ее представлением в формате Ньюика.
• Филогенетика. просмотрщик дерева (newick) (Автор: Huerta-Cepas et al., 2016).