Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Формат Ньюика
Расширения имени файла.tree
Тип интернет-СМИtext/x-nh
Первый выпуск24 июня 1986 (34 года назад) ( 1986-06-24 )
Тип формататеоретико-графовые деревья
Открытый формат ?да

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

Примеры [ править ]

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

NewickExample.svg

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

(,, (,)); никакие узлы не названы
(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) F: 0,1) A; дерево с корнем на листовом узле  (редко)

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

Корневые, некорневые и бинарные деревья [ править ]

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

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

Грамматика [ править ]

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

Узлы грамматики [ править ]

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

Грамматические правила [ править ]

Обратите внимание, "|" разделяет альтернативы.

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

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

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

Дерево → RootLeaf ";" | RootInternal ";"RootLeaf → Имя | "(" Branch ")" Name RootInternal → "(" Branch "," BranchSet ")" Name

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

Заметки [ править ]

  • Кавычки строка не может содержать пробелы, скобки, квадратные скобки, single_quotes, двоеточие, точку с запятой или запятые. Символы подчеркивания в некотируемой строке с преобразуются в пробела. [2]
  • Строка может также быть в кавычках, заключив его в одинарных кавычках. Одиночные кавычки в исходной строке представлены как два последовательных символа одинарных кавычек. [2]
  • Пробелы могут появляться где угодно, кроме строки без кавычек или длины.
  • Новые строки могут появляться где угодно, кроме строки или длины .
  • Комментарии заключаются в квадратные скобки. Они могут появляться везде, где разрешены символы новой строки. [2] Комментарии, начинающиеся с &, обычно генерируются компьютером для дополнительных данных. Некоторые диалекты допускают вложенные комментарии.

Диалекты [ править ]

Формат X в Нью-Гэмпшире [ править ]

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

Расширенный Ньюик [ править ]

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

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

ж
 

А

 
 

B

 
е
c
 

C

 
 

Y

 
 
 

D

 
 
 
ж
 

А

 
 

B

 
е
 

C

 
d
 

Y

 
 

D

 
 
 
 
Два дерева в стандартном Ньюике

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

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

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

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

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

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

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

Расширенный формат Newick [ править ]

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

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

Специальные расширения [ править ]

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

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

Визуализация [ править ]

Основная статья: Список программ визуализации филогенетического дерева

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Формат дерева Ньюика.
  2. ^ a b c d Олсен, Гэри (30 августа 1990 г.). "Интерпретация" формата дерева "Ньюика 8:45" .
  3. ^ Zmasek, Кристиан М. (1999). «Нью-Гэмпширский формат X (NHX)» (PDF) .
  4. ^ Кардона, Габриэль; Росселло, Франсеск; Валиенте, Габриэль (27 марта 2008 г.). «Пакет Perl и инструмент выравнивания для филогенетических сетей» . BMC Bioinformatics . 9 : 175. DOI : 10,1186 / 1471-2105-9-175 . ISSN 1471-2105 . PMC 2330044 . PMID 18371228 .   
  5. ^ Кардона, Габриэль; Росселло, Франсеск; Валиенте, Габриэль (2008). «Расширенный Ньюик: пришло время для стандартного представления филогенетических сетей» . BMC Bioinformatics . 9 : 532. DOI : 10,1186 / 1471-2105-9-532 . PMC 2621367 . PMID 19077301 .  
  6. ^ Барнетт, Роберт Мэтью (16 февраля 2012 г.). «Богатый формат Ньюика» . Wiki Университета Райса .
  7. ^ Ю, Гуанчуан. «Глава 1 Импорт дерева с данными» . Интеграция данных, манипуляции и визуализация филогенетического дерева .
  8. ^ Уэрта-Сепас, Хайме; Серра, Франсуа; Борк, Пер (июнь 2016 г.). «ETE 3: реконструкция, анализ и визуализация филогеномных данных» . Молекулярная биология и эволюция . 33 (6): 1635–1638. DOI : 10.1093 / molbev / msw046 . ISSN 0737-4038 . PMC 4868116 . PMID 26921390 .   
  9. ^ Boc, Аликс; Диалло, Альфа Бубакар; Макаренков, Владимир (июль 2012 г.). «T-REX: веб-сервер для вывода, проверки и визуализации филогенетических деревьев и сетей» . Исследования нуклеиновых кислот . 40 (выпуск веб-сервера): W573–579. DOI : 10.1093 / NAR / gks485 . ISSN 1362-4962 . PMC 3394261 . PMID 22675075 .   

Внешние ссылки [ править ]

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