formacie Newicka
| Rozszerzenia nazw plików | .drzewo |
|---|---|
| Rodzaj mediów internetowych | tekst/x-nh |
| Pierwsze wydanie | 24 czerwca 1986 |
| Typ formatu | drzewa grafowo-teoretyczne |
| Otwarty format ? | Tak |
W matematyce format drzewa Newick (lub notacja Newick lub format drzewa New Hampshire ) to sposób przedstawiania drzew teoretycznych z długościami krawędzi za pomocą nawiasów i przecinków. Został przyjęty przez Jamesa Archiego, Williama HE Daya, Josepha Felsensteina , Wayne'a Maddisona , Christophera Meachama, F. Jamesa Rohlfa i Davida Swofforda na dwóch spotkaniach w 1986 roku, z których drugie odbyło się w restauracji Newick's w Dover , New Hampshire, Stany Zjednoczone. Przyjęty format jest uogólnieniem formatu opracowanego przez Meachama w 1984 roku dla pierwszych programów do rysowania drzew w PHYLIP Felsensteina .
Przykłady
Następujące drzewo:
można przedstawić w formacie Newick na kilka sposobów
(,, (,)); żadne węzły nie są nazwane (A,B,(C,D)); węzły liści są nazywane (A,B,(C,D)E)F; wszystkie węzły mają nazwy (:0.1,:0.2,(:0.3,:0.4):0.5); wszystkie oprócz węzła głównego mają odległość do rodzica (:0.1,:0.2,(:0.3,:0.4):0.5):0.0; wszystkie mają dystans do rodzica (A:0,1,B:0,2,(C:0,3,D:0,4):0,5); odległości i nazwy liści (popularne) (A:0,1,B:0,2,(C:0,3,D:0,4)E:0,5)F; odległości i wszystkie nazwy ((B:0,2,(C:0,3,D:0,4)E:0,5)F:0,1)A; drzewo zakorzenione w węźle liścia (rzadko)
Format Newick jest zwykle używany w narzędziach takich jak PHYLIP i stanowi minimalną definicję drzewa filogenetycznego .
Drzewa ukorzenione, nieukorzenione i binarne
Gdy nieukorzenione drzewo jest reprezentowane w notacji Newick, jako jego korzeń wybierany jest dowolny węzeł. Niezależnie od tego, czy jest ukorzeniony, czy nie, zazwyczaj reprezentacja drzewa jest zakorzeniona w węźle wewnętrznym i rzadkie (ale legalne) jest ukorzenienie drzewa w węźle liścia.
Ukorzenione drzewo binarne , które jest zakorzenione w węźle wewnętrznym, ma dokładnie dwa bezpośrednie węzły potomne dla każdego węzła wewnętrznego. Nieukorzenione binarne , które jest zakorzenione w dowolnym węźle wewnętrznym, ma dokładnie trzy bezpośrednie węzły potomne dla węzła głównego, a każdy inny węzeł wewnętrzny ma dokładnie dwa bezpośrednie węzły potomne. Drzewo binarne zakorzenione z liścia ma co najwyżej jeden bezpośredni węzeł potomny dla węzła głównego, a każdy węzeł wewnętrzny ma dokładnie dwa bezpośrednie węzły potomne.
Gramatyka
Gramatyka do analizowania formatu Newick (z grubsza oparta na ):
Węzły gramatyczne
Drzewo : Pełny wejściowy format Newicka dla pojedynczego drzewa Poddrzewo : węzeł wewnętrzny (i jego potomkowie) lub węzeł liścia Liść : węzeł bez potomków Wewnętrzny : węzeł i jego jeden lub więcej potomków Zbiór gałęzi : zbiór jednego lub więcej Gałęzie Gałąź : krawędź drzewa i jego poddrzewo potomne. Nazwa : nazwa węzła Length : długość krawędzi drzewa.
Reguły gramatyczne
Uwaga, "|" oddziela alternatywy.
Drzewo → Poddrzewo ";" Poddrzewo → Liść | Liść wewnętrzny → Nazwa Wewnętrzny → „(„ Zestaw gałęzi ”)” Nazwa Zestaw gałęzi → Gałąź | Branch "," BranchSet Gałąź → Nazwa długości poddrzewa → pusty | ciąg Długość → pusty | ":" numer
Białe znaki (spacje, tabulatory, powrót karetki i wysuw wiersza) w numerze są zabronione. Białe znaki w łańcuchu są często zabronione. Białe znaki w innych miejscach są ignorowane. Czasami ciąg Nazwa musi mieć określoną stałą długość; w przeciwnym razie znaki interpunkcyjne z gramatyki (średnik, nawiasy, przecinek i dwukropek) są zabronione. Drzewo → Poddrzewo "; " zamiast tego produkcja to Drzewo → Gałąź ";" produkcja w tych przypadkach, w których dozwolone jest posiadanie całego drzewa pochodzącego znikąd; to przechwytuje również zastąpioną produkcję, ponieważ Długość może być pusta .
Zauważ, że kiedy drzewo mające więcej niż jeden liść jest zakorzenione z jednego z jego liści, reprezentacja rzadko spotykana w praktyce, liść korzenia jest charakteryzowany jako węzeł wewnętrzny przez powyższą gramatykę. Ogólnie rzecz biorąc, węzeł główny oznaczony jako Internal powinien być interpretowany jako faktycznie wewnętrzny wtedy i tylko wtedy, gdy ma co najmniej dwie gałęzie w swoim zbiorze gałęzi . Można stworzyć gramatykę, która formalizuje to rozróżnienie, zastępując powyższą regułę tworzenia drzewa
Drzewo → Korzeń Liść ";" | Główny wewnętrzny ";" RootLeaf → Imię | „(„ Gałąź ”)” Nazwa RootInternal → „(„ Gałąź "," BranchSet ")" Nazwa
Pierwsza produkcja RootLeaf dotyczy drzewa z dokładnie jednym liściem. Druga RootLeaf służy do ukorzeniania drzewa z jednego z dwóch lub więcej liści.
Notatki
- Ciąg niecytowany nie może zawierać spacji, nawiasów okrągłych, nawiasów kwadratowych, pojedynczych cudzysłowów, dwukropków, średników ani przecinków. Znaki podkreślenia w ciągach bez cudzysłowów są konwertowane na spacje.
- Ciąg można również ująć w cudzysłowy . Pojedyncze cudzysłowy w oryginalnym ciągu są reprezentowane jako dwa kolejne znaki pojedynczego cudzysłowu.
- Białe spacje mogą pojawić się w dowolnym miejscu poza niecytowanym łańcuchem lub długością
- Znaki nowej linii mogą pojawiać się w dowolnym miejscu poza łańcuchem lub długością .
- Komentarze są ujęte w nawiasy kwadratowe. Mogą pojawiać się wszędzie tam, gdzie dozwolone są znaki nowej linii. Komentarze zaczynające się od
&są zazwyczaj generowane komputerowo w celu uzyskania dodatkowych danych. Niektóre dialekty pozwalają na zagnieżdżone komentarze.
dialekty
Format New Hampshire X
Format New Hampshire X (NHX) jest rozszerzeniem Newick, które dodaje dane klucz-wartość (duplikacje genów itp.) do węzłów Newick. Odbywa się to poprzez umieszczenie dodatkowych danych w nawiasach [&&NHX: klucz = wartość :...] w etykietach węzłów. Nawiasy są używane, ponieważ reprezentują komentarze w pliku Nexus , więc każdy parser, który nie rozumie tych dodatkowych informacji, zignoruje je.
Rozszerzony Newick
Podczas gdy standardowa notacja Newicka jest ograniczona do drzew filogenetycznych, rozszerzona notacja Newick (Perl Bio::PhyloNetwork) może być używana do kodowania jawnych sieci filogenetycznych. W sieci filogenetycznej , która jest uogólnieniem drzewa filogenetycznego , węzeł reprezentuje zdarzenie dywergencji ( kladogeneza ) lub zdarzenie siatkowania, takie jak hybrydyzacja , introgresja , poziomy (boczny) transfer genów lub rekombinacja . Węzły reprezentujące zdarzenie siatkowania są powielane, opatrzone adnotacjami poprzez wprowadzenie symbolu # do formatu Newicka i numerowane kolejno (przy użyciu wartości całkowitych zaczynających się od 1).
Na przykład, jeśli liść Y jest produktem hybrydyzacji (x) między liniami prowadzącymi do C i D w powyższym drzewie,
|
|
można wyrazić tę sytuację, definiując dwa drzewa w standardowej notacji Newicka
(A,B,((C,Y)c,D)e)f; i (A,B,(C,(Y,D)d)e)f; standard Newick , wszystkie węzły są nazwane (wewnętrzne węzły są małe, pozostawia duże)
lub w rozszerzonej notacji Newicka
(A,B,((C,(Y)x#H1)c,(x#H1,D)d)e)f; rozszerzony Newick, wszystkie węzły są nazwane; 1 to liczba całkowita identyfikująca węzeł hybrydowy x
x #H1 tutaj jest węzłem hybrydowym. Po narysowaniu zostanie on połączony przez program w jeden węzeł. Oto obraz narysowany przez Dendroscope dla tego przykładu: 
Powyższe zasady produkcji zostały zmodyfikowane przez następujące elementy dotyczące etykietowania węzłów hybrydowych (ogólnie węzłów reprezentujących zdarzenia siatkowania):
Liść → Nazwa Hybryda Hybryda → pusta | "#" Type integer -- Część #i jest obowiązkowym identyfikatorem węzła hybrydowego Typ → pusty | struna -- rodzaj sieciowania, np. H = hybrydyzacja, LGT = boczny transfer genów, R = rekombinacja.
W wizualizacji zdarzeń LGT dla danego węzła siatkowatego jedna krawędź przychodząca jest zwykle rysowana jako krawędź „akceptorowa”, a wszystkie pozostałe krawędzie przychodzące są rysowane jako krawędzie „przenoszące”. Niektóre programy (np. Dendroscope i SplitsTree ) umożliwiają oznaczenie dokładnie jednej kopii węzła siatkowego za pomocą ## , aby wskazać, że odpowiada ona krawędzi akceptora.
Rozszerzony Newick jest kompatybilny wstecz: węzeł hybrydowy byłby po prostu interpretowany jako kilka węzłów o dziwnych nazwach dla starszych parserów.
Bogaty format Newicka
Format Rich Newick, znany również jako format Rice Newick, jest dalszym rozszerzeniem formatu Extended Newick. Dodaje wsparcie dla:
- Filogenezy nieukorzenione. Robi się to po prostu przez napisanie nieukorzenionego drzewa jak zwykle (tj. wybranie dowolnego korzenia w binarnym punkcie rozgałęzienia) i dodanie przedrostka
[&U]do łańcucha.[&R], z drugiej strony, może być użyte do wymuszenia ukorzenionego drzewa. - Bootstrapowe wartości i prawdopodobieństwa. Odbywa się to poprzez dodanie dodatkowych
:[bootstrap]:[prob]po długości; pola mogą pozostać puste, o ile obecne są dwukropki. Może to być niezgodne z poprzednimi wersjami.
Rozszerzenia ad hoc
Niektóre inne programy, takie jak NWX, używają komentarzy zaczynających się od & do kodowania dodatkowych informacji w sposób ad hoc:
- MrBayes i BEAST dodają do węzłów dodatkowe informacje, takie jak prawdopodobieństwo, długość w latach, odchylenie standardowe wartości. Używają również
[%U].
Wyobrażanie sobie
Opublikowano wiele narzędzi do wizualizacji danych drzewa Newick. Konkretne przykłady obejmują zestaw narzędzi ETE („Środowisko eksploracji drzew”) i T-REX . Pakiety oprogramowania filogenetycznego, takie jak SplitsTree i przeglądarka drzew Dendroscope , a także narzędzie do przeglądania drzew online IcyTree mogą obsługiwać standardową i rozszerzoną notację Newick, podczas gdy oprogramowanie sieci filogenetycznej PhyloNet wykorzystuje zarówno format Extended Newick, jak i Rich Newick.
Zobacz też
- filoXML
- T-REX (Webserver) umożliwia obsługę drzew i sieci filogenetycznych w formacie Newick.
- Smart Game Format to aplikacja formatu Newick i jest szeroko stosowana do nagrywania gier planszowych.
Linki zewnętrzne
- Miyamoto i Goodman's Phylogram of Eutherian Mammals Przykład dużego filogramu z reprezentacją w formacie Newick.
- Przeglądarka drzewa filogenetycznego (newick) (autor: Huerta-Cepas i in. 2016)