Формат Ньюика
| Расширения имен файлов | .tree |
|---|---|
| Тип интернет-СМИ | text/x-nh |
| Первоначальный выпуск | 24 июня 1986 г. |
| Тип формата | деревья теории графов |
| Открытый формат ? | Да |
В математике и формат филогенетике дерева Ньюика (или нотация Ньюика или формат дерева Нью-Гэмпшира ) — это способ представления теоретико-графовых деревьев с длинами ребер с использованием круглых скобок и запятых. Его приняли Джеймс Арчи, Уильям Х.Э. Дэй, Джозеф Фельзенштейн , Уэйн Мэддисон , Кристофер Мичем, Ф. Джеймс Рольф и Дэвид Суоффорд на двух встречах в 1986 году, вторая из которых состоялась в ресторане Ньюика. [1] в Дувре , Нью-Гэмпшир, США. Принятый формат является обобщением формата, разработанного Мичемом в 1984 году для первых программ рисования деревьев в пакете PHYLIP Фельзенштейна . [2]
Примеры
[ редактировать ]Следующее дерево:
может быть представлен в формате Ньюика несколькими способами
(,,(,)); no nodes are named (A,B,(C,D)); leaf nodes are named (A,B,(C,D)E)F; all nodes are named (:0.1,:0.2,(:0.3,:0.4):0.5); all but root node have a distance to parent (:0.1,:0.2,(:0.3,:0.4):0.5):0.0; all have a distance to parent (A:0.1,B:0.2,(C:0.3,D:0.4):0.5); distances and leaf names (popular) (A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F; distances and all names ((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A; a tree rooted on a leaf node (rare)
Формат Ньюика обычно используется для таких инструментов, как PHYLIP , и является минимальным определением филогенетического дерева .
Корневые, некорневые и бинарные деревья.
[ редактировать ]Когда некорневое дерево представлено в нотации Ньюика, в качестве его корня выбирается произвольный узел. Независимо от того, корневое или некорневое, представление дерева обычно основано на внутреннем узле, и корневое дерево редко (но законно) размещается на листовом узле.
Корневое двоичное дерево , корнем которого является внутренний узел, имеет ровно два узла-потомка для каждого внутреннего узла. Некорневое двоичное дерево, корнем которого является произвольный внутренний узел, имеет ровно три узла-потомка для корневого узла, а каждый второй внутренний узел имеет ровно два узла-потомка. Бинарное дерево, корнем которого является лист, имеет не более одного узла-потомка для корневого узла, а каждый внутренний узел имеет ровно два узла-потомка.
Грамматика
[ редактировать ]Грамматика для анализа формата Ньюика (примерно на основе [3] ):
Грамматические узлы
[ редактировать ]Tree: The full input Newick Format for a single tree Subtree: an internal node (and its descendants) or a leaf node Leaf: a node with no descendants Internal: a node and its one or more descendants BranchSet: a set of one or more Branches Branch: a tree edge and its descendant subtree. Name: the name of a node Length: the length of a tree edge.
Грамматические правила
[ редактировать ]Обратите внимание, "|" разделяет альтернативы.
Tree → Subtree ";"
Subtree → Leaf | Internal
Leaf → Name
Internal → "(" BranchSet ")" Name
BranchSet → Branch | Branch "," BranchSet
Branch → Subtree Length
Name → empty | string
Length → empty | ":" number
Пробелы (пробелы, табуляции, возвраты каретки и переводы строк) внутри номера запрещены. Пробелы внутри строки часто запрещены. Пробелы в других местах игнорируются. Иногда имени строка должна иметь указанную фиксированную длину; в противном случае символы пунктуации из грамматики (точка с запятой, круглые скобки, запятая и двоеточие) запрещены. Дерево " → Поддерево "; вместо этого производством является Дерево → Ветка ";" производство в тех случаях, когда допускается появление всего дерева из ниоткуда; это также фиксирует замененную продукцию, поскольку длина может быть пустой .
Обратите внимание, что когда дерево, имеющее более одного листа, основано на одном из его листьев (представление, которое редко встречается на практике), корневой лист характеризуется как внутренний узел в соответствии с приведенной выше грамматикой. Как правило, корневой узел, помеченный как Internal, должен рассматриваться как фактически внутренний тогда и только тогда, когда он имеет по крайней мере два Branch в своем BranchSet . Можно создать грамматику, которая формализует это различие, заменив приведенное выше правило создания дерева на
Tree → RootLeaf ";" | RootInternal ";"
RootLeaf → Name | "(" Branch ")" Name
RootInternal → "(" Branch "," BranchSet ")" Name
Первое производство RootLeaf предназначено для дерева, имеющего ровно один лист. Второе производство RootLeaf предназначено для укоренения дерева из одного из двух или более листьев.
Примечания
[ редактировать ]- Некотируемый Строка не может содержать пробелы, круглые, квадратные скобки, одинарные кавычки, двоеточия, точки с запятой или запятые. Подчеркивание символов без кавычек string . преобразуются в пробелы [3]
- А Строку также можно заключить в одинарные кавычки. Одинарные кавычки в исходной строке представлены как два последовательных символа одинарных кавычек. [3]
- Пробелы могут встречаться где угодно, кроме не заключенного в кавычки. строка или Длина
- Новые строки могут появляться где угодно, кроме строка или Длина .
- Комментарии заключаются в квадратные скобки. Они могут появляться везде, где разрешены символы новой строки. [3] Комментарии, начинающиеся с
&обычно генерируются компьютером для получения дополнительных данных. Некоторые диалекты допускают вложенные комментарии.
Диалекты
[ редактировать ]Формат Нью-Гэмпшир X
[ редактировать ]Формат New Hampshire X (NHX) — это расширение Newick, которое добавляет данные «ключ-значение» (дублирование генов и т. д.) к узлам Newick. Это делается путем помещения дополнительных данных в скобки. [&&NHX:key=value:...] в метках узлов. Скобки используются, поскольку они представляют комментарии в формате файла Nexus , поэтому любой синтаксический анализатор, не понимающий эту дополнительную информацию, будет их игнорировать. [4]
Расширенный Ньюик
[ редактировать ]Хотя стандартная нотация Ньюика ограничена филогенетическими деревьями, расширенная нотация Ньюика (Perl Bio::PhyloNetwork) может использоваться для кодирования явных филогенетических сетей. [5] В филогенетической сети , которая является обобщением филогенетического дерева , узел представляет либо событие дивергенции ( кладогенез ), либо событие ретикуляции, такое как гибридизация , интрогрессия , горизонтальный (латеральный) перенос генов или рекомбинация . Узлы, представляющие событие ретикуляции, дублируются, помечаются символом # в формате Ньюика и последовательно нумеруются (с использованием целочисленных значений, начинающихся с 1).
Например, если лист Y является продуктом гибридизации (x) между линиями, ведущими к C и D в дереве выше,
|
|
эту ситуацию можно выразить, определив два дерева в стандартной нотации Ньюика.
(A,B,((C,Y)c,D)e)f; and (A,B,(C,(Y,D)d)e)f; standard Newick, all nodes are named (internal nodes lowercase, leaves upper case)
или в расширенной нотации Ньюика
(A,B,((C,(Y)x#H1)c,(x#H1,D)d)e)f; extended Newick, all nodes are named; 1 is the integer identifying the hybrid node x
The x#H1 вот гибридный узел. При рисовании он будет объединен программой в один узел.
Это изображение, нарисованное Dendroscope для этого примера:
Приведенные выше правила производства изменены следующим образом для маркировки гибридных узлов (как правило, узлов, представляющих события ретикуляции): [6]
Leaf → Name Hybrid Hybrid → empty | "#" Type integer -- The #i part is an obligatory identifier for a hybrid node Type → empty | string -- type of reticulation, e.g., H = hybridisation, LGT = lateral gene transfer, R = recombination.
При визуализации событий LGT для данного сетчатого узла одно входящее ребро обычно рисуется как «акцепторное», а все остальные входящие ребра рисуются как «переносные». Некоторые программы (например, Dendroscope и SplitsTree ) позволяют пометить ровно одну копию сетчатого узла значком. ## чтобы указать, что он соответствует акцепторному краю.
Расширенный Newick обратно совместим: гибридный узел будет просто интерпретироваться как несколько узлов со странными именами для устаревших анализаторов.
Формат Рича Ньюика
[ редактировать ]Формат Рича Ньюика, также известный как формат Райса Ньюика, является дальнейшим расширением Расширенного Ньюика. [7] Он добавляет поддержку:
- Неукорененные филогении. Это просто делается путем написания некорневого дерева, как обычно (т. е. выбора произвольного корня в бинарной точке ветвления) и добавления префикса
[&U]к строке.[&R], с другой стороны, можно использовать для принудительного укоренения дерева. - Бутстрап-значения и вероятности. Это достигается добавлением дополнительных
:[bootstrap]:[prob]поля после длины; поля можно оставить пустыми, пока присутствуют двоеточия. Это может быть обратно несовместимо.
Специальные расширения
[ редактировать ]Некоторые другие программы, например NWX, используют комментарии, начинающиеся с & для кодирования дополнительной информации специальным образом: [8]
- MrBayes и BEAST добавляют в узлы дополнительную информацию, такую как вероятность, продолжительность в годах, стандартное отклонение значений. Они также используют
[%U].
Визуализация
[ редактировать ]Для визуализации данных дерева Ньюика было опубликовано множество инструментов. Конкретные примеры включают набор инструментов ETE («Среда для исследования деревьев»). [9] и Т-РЕКС . [10] Пакеты филогенетического программного обеспечения, такие как SplitsTree и программа просмотра деревьев Dendroscope , а также онлайн-инструмент просмотра деревьев IcyTree, могут обрабатывать стандартную и расширенную нотацию Ньюика, в то время как филогенетическое сетевое программное обеспечение PhyloNet использует форматы Extended Newick и Rich Newick.
См. также
[ редактировать ]- филоXML
- T-REX (веб-сервер) позволяет работать с филогенетическими деревьями и сетями в формате Ньюика.
- Формат Smart Game — это приложение формата Newick, широко используемое для записи настольных игр.
Ссылки
[ редактировать ]- ^ Домашняя страница Newick's Lobster House
- ^ «Формат дерева Ньюика» .
- ^ Jump up to: а б с д Олсен, Гэри (30 августа 1990 г.). «Интерпретация древовидного формата Ньюика 8:45» .
- ^ Змасек, Кристиан М. (1999). «Формат X Нью-Гэмпшира (NHX)» (PDF) .
- ^ Кардона, Габриэль; Росселло, Франческ; Валиенте, Габриэль (27 марта 2008 г.). «Пакет Perl и инструмент выравнивания филогенетических сетей» . БМК Биоинформатика . 9 :175. дои : 10.1186/1471-2105-9-175 . ISSN 1471-2105 . ПМК 2330044 . ПМИД 18371228 .
- ^ Кардона, Габриэль; Росселло, Франческ; Валиенте, Габриэль (2008). «Расширенный Ньюик: пришло время стандартного представления филогенетических сетей» . БМК Биоинформатика . 9 : 532. дои : 10.1186/1471-2105-9-532 . ПМЦ 2621367 . ПМИД 19077301 .
- ^ Барнетт, Роберт Мэтью (16 февраля 2012 г.). «Формат Рича Ньюика» . Wiki Университета Райса .
- ^ Ю, Гуанчуан. «Глава 1. Импорт дерева с данными» . Интеграция данных, манипулирование и визуализация филогенетического дерева .
- ^ Уэрта-Сепас, Хайме; Серра, Франсуа; Борк, Пер (июнь 2016 г.). «ETE 3: Реконструкция, анализ и визуализация филогеномных данных» . Молекулярная биология и эволюция . 33 (6): 1635–1638. дои : 10.1093/molbev/msw046 . ISSN 0737-4038 . ПМЦ 4868116 . ПМИД 26921390 .
- ^ Бок, Аликс; Диалло, Альфа Бубакар; Макаренков, Владимир (июль 2012 г.). «T-REX: веб-сервер для вывода, проверки и визуализации филогенетических деревьев и сетей» . Исследования нуклеиновых кислот . 40 (проблема с веб-сервером): W573–579. дои : 10.1093/nar/gks485 . ISSN 1362-4962 . ПМК 3394261 . ПМИД 22675075 .
Внешние ссылки
[ редактировать ]- Филограмма эвтерийских млекопитающих Миямото и Гудмана. Пример большой филограммы с представлением в формате Ньюика.
- Программа просмотра филогенетического дерева (ньюика) (автор: Huerta-Cepas et al., 2016)