stringtranslate.com

Формат Ньюик

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

Примеры

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

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

(,,(,)); ни один узел не назван
(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; дерево, укорененное в конечных узлах  (редко)

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

Укорененные, неукорененные и бинарные деревья

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

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

Грамматика

Грамматика для анализа формата Newick (примерно основана на [3] ):

Грамматические узлы

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

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

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

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

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

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

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

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

Примечания

Диалекты

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

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

Расширенный Ньюик

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

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

Пример филогенетической сети

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

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

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

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

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

Вот x#H1гибридный узел. Он будет объединен программой в один узел при рисовании. Это изображение, нарисованное Dendroscope для этого примера:Сеть, нарисованная Dendroscope


Правила производства, указанные выше, изменяются следующим образом для маркировки гибридных узлов (в общем случае узлов, представляющих события ретикулирования): [6]

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

При визуализации событий LGT для заданного узла ретикулята одно входящее ребро обычно рисуется как ребро «акцептора», а все остальные входящие ребра рисуются как ребра «передачи». Некоторые программы (например, Dendroscope и SplitsTree ) позволяют пометить ровно одну копию узла ретикулята, ##чтобы указать, что он соответствует ребру акцептора.

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

Богатый формат Newick

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

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

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

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

Было опубликовано множество инструментов для визуализации данных деревьев Newick. Конкретные примеры включают набор инструментов ETE («Environment for Tree Exploration») [9] и T-REX . [10] Филогенетические программные пакеты, такие как SplitsTree и средство просмотра деревьев Dendroscope , а также онлайн-инструмент просмотра деревьев IcyTree, могут обрабатывать стандартную и расширенную нотацию Newick, в то время как программное обеспечение филогенетической сети PhyloNet использует как формат Extended Newick, так и Rich Newick.

Смотрите также

Ссылки

  1. ^ Домашняя страница Newick's Lobster House
  2. ^ «Формат дерева Ньюика».
  3. ^ abcd Олсен, Гэри (30 августа 1990 г.). «Интерпретация формата дерева «Newick's 8:45»».
  4. ^ Змасек, Кристиан М. (1999). «Нью-Гэмпширский X-формат (NHX)» (PDF) .
  5. ^ Кардона, Габриэль; Россельо, Франсеск; Валиенте, Габриэль (2008-03-27). "Пакет perl и инструмент выравнивания для филогенетических сетей". BMC Bioinformatics . 9 : 175. doi : 10.1186/1471-2105-9-175 . ISSN  1471-2105. PMC 2330044. PMID 18371228  . 
  6. ^ Кардона, Габриэль; Россельо, Франсеск; Валиенте, Габриэль (2008). «Расширенный Ньюик: пришло время для стандартного представления филогенетических сетей». BMC Bioinformatics . 9 : 532. doi : 10.1186/1471-2105-9-532 . PMC 2621367. PMID  19077301 . 
  7. ^ Барнетт, Роберт Мэтью (16 февраля 2012 г.). «Rich Newick Format». Вики Университета Райса .
  8. ^ Ю, Гуанчуан. «Глава 1 Импорт дерева с данными». Интеграция данных, манипулирование и визуализация филогенетического дерева .
  9. ^ Уэрта-Сепас, Хайме; Серра, Франсуа; Борк, Пир (июнь 2016 г.). «ETE 3: Реконструкция, анализ и визуализация филогеномных данных». Молекулярная биология и эволюция . 33 (6): 1635–1638. doi :10.1093/molbev/msw046. ISSN  0737-4038. PMC 4868116. PMID 26921390  . 
  10. ^ Boc, Alix; Diallo, Alpha Boubacar; Makarenkov, Vladimir (июль 2012 г.). "T-REX: веб-сервер для вывода, проверки и визуализации филогенетических деревьев и сетей". Nucleic Acids Research . 40 (выпуск веб-сервера): W573–579. doi :10.1093/nar/gks485. ISSN  1362-4962. PMC 3394261. PMID  22675075 . 

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