Newick-Format

In der Mathematik und Phylogenetik ist das Newick-Baumformat (auch Newick-Notation oder New - Hampshire-Baumformat genannt ) eine Methode zur Darstellung graphentheoretischer Bäume mit Kantenlängen in Klammern und Kommas. Es wurde 1986 von James Archie, William H. E. Day, Joseph Felsenstein , Wayne Maddison , Christopher Meacham, F. James Rohlf und David Swofford auf zwei Treffen eingeführt, das zweite davon in Newicks Restaurant ^{[ 1 ]} in Dover , New Hampshire, USA. Das eingeführte Format ist eine Verallgemeinerung des von Meacham 1984 für die ersten Baumdarstellungsprogramme in Felsensteins PHYLIP- Paket entwickelten Formats. ^{[ 2 ]}

Der folgende Baum:

könnte im Newick-Format auf verschiedene Weisen dargestellt werden

(,,(,)); keine Knoten sind benannt (A,B,(C,D)); Blattknoten sind benannt (A,B,(C,D)E)F; alle Knoten sind benannt (:0.1,:0.2,(:0.3,:0.4):0.5); alle Knoten außer dem Wurzelknoten haben eine Distanz zum Elternknoten (:0.1,:0.2,(:0.3,:0.4):0.5):0.0; alle haben eine Distanz zum Elternknoten (A:0.1,B:0.2,(C:0.3,D:0.4):0.5); Distanzen und Blattnamen (häufig) (A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F; Distanzen und alle Namen ((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A; ein Baum mit einem Blattknoten als Wurzel (selten)

Das Newick-Format wird typischerweise für Tools wie PHYLIP verwendet und stellt eine minimale Definition für einen phylogenetischen Baum dar .

Wird ein wurzelloser Baum in Newick-Notation dargestellt, wird ein beliebiger Knoten als Wurzel gewählt. Ob gewurzelt oder wurzellos, typischerweise wird ein Baum an einem inneren Knoten gewurzelt; es ist selten (aber zulässig), einen Blattknoten als Wurzel zu verwenden.

Ein gewurzelter Binärbaum , dessen Wurzel ein innerer Knoten ist, hat genau zwei direkte Nachfolgerknoten für jeden inneren Knoten. Ein ungewurzelter Binärbaum, dessen Wurzel ein beliebiger innerer Knoten ist, hat genau drei direkte Nachfolgerknoten für die Wurzel und genau zwei direkte Nachfolgerknoten für jeden anderen inneren Knoten. Ein Binärbaum, dessen Wurzel ein Blatt ist, hat höchstens einen direkten Nachfolgerknoten für die Wurzel und genau zwei direkte Nachfolgerknoten für jeden inneren Knoten.

Eine Grammatik zum Parsen des Newick-Formats (grob basierend auf ^{[ 3 ]} ):

Baum : Die vollständige Eingabe im Newick-Format für einen einzelnen Baum. Teilbaum : Ein innerer Knoten (und seine Nachfolger) oder ein Blattknoten. Blatt : Ein Knoten ohne Nachfolger. Intern : Ein Knoten und seine einen oder mehrere Nachfolger. Zweiggruppe : Eine Gruppe von einem oder mehreren Zweigen. Zweig : Eine Baumkante und ihr Nachfolger-Teilbaum. Name : Der Name eines Knotens. Länge : Die Länge einer Baumkante. 

Hinweis: Das Zeichen "|" trennt Alternativen.

Baum → Teilbaum ";" Teilbaum → Blatt | Internes Blatt → Name Intern → "(" Zweiggruppe ")" Name Zweiggruppe → Zweig | Zweig "," Zweiggruppe Zweig → Teilbaum Länge Name → leer | Zeichenkette Länge → leer | ":" Zahl

Leerzeichen (Leerzeichen, Tabulatoren, Wagenrückläufe und Zeilenvorschübe) innerhalb von Zahlen sind nicht zulässig. Leerzeichen innerhalb von Zeichenketten sind häufig ebenfalls nicht zulässig. Leerzeichen an anderer Stelle werden ignoriert. Manchmal muss die Namenszeichenkette eine festgelegte Länge haben; andernfalls sind die Satzzeichen der Grammatik (Semikolon, Klammern, Komma und Doppelpunkt) nicht zulässig. Die Produktion „ Baum → Teilbaum “ wird in Fällen, in denen der gesamte Baum von einem beliebigen Punkt aus erstellt werden darf, durch die Produktion „ Baum → Zweig “ ersetzt; dies erfasst auch die ersetzte Produktion, da die Länge leer sein kann .

Beachten Sie, dass, wenn ein Baum mit mehreren Blättern von einem seiner Blätter aus gewurzelt ist – eine in der Praxis selten anzutreffende Darstellung –, das Wurzelblatt gemäß der obigen Grammatik als interner Knoten charakterisiert wird. Im Allgemeinen sollte ein als intern gekennzeichneter Wurzelknoten genau dann als tatsächlich intern interpretiert werden, wenn er mindestens zwei Zweige in seiner Zweigmenge besitzt . Man kann eine Grammatik erstellen, die diese Unterscheidung formalisiert, indem man die obige Baumproduktionsregel durch folgende ersetzt:

Baum → Wurzelblatt ";" | Wurzelinneres ";" Wurzelblatt → Name | "(" Zweig ")" Name Wurzelinneres → "(" Zweig "," Zweiggruppe ")" Name

Die erste RootLeaf -Produktion dient der Bewurzelung eines Baumes mit genau einem Blatt. Die zweite RootLeaf- Produktion dient der Bewurzelung eines Baumes aus einem seiner zwei oder mehr Blätter.

• Eine nicht in Anführungszeichen gesetzte Zeichenkette darf keine Leerzeichen, Klammern, eckigen Klammern, einfachen Anführungszeichen, Doppelpunkte, Semikolons oder Kommas enthalten. Unterstriche in nicht in Anführungszeichen gesetzten Zeichenketten werden in Leerzeichen umgewandelt. ^{[ 3 ]}
• Eine Zeichenkette kann auch durch Einschließen in einfache Anführungszeichen zitiert werden. Einfache Anführungszeichen in der ursprünglichen Zeichenkette werden als zwei aufeinanderfolgende einfache Anführungszeichen dargestellt. ^{[ 3 ]}
• Leerzeichen dürfen überall vorkommen, außer innerhalb einer nicht in Anführungszeichen gesetzten Zeichenkette oder einer Längenangabe.
• Zeilenumbrüche dürfen überall außer innerhalb einer Zeichenkette oder einer Längenangabe vorkommen .
• Kommentare stehen in eckigen Klammern. Sie können überall dort stehen, wo Zeilenumbrüche erlaubt sind. ^{[ 3 ]} Kommentare, die mit einem Punkt beginnen, &werden in der Regel computergeneriert und enthalten zusätzliche Informationen. Einige Dialekte erlauben verschachtelte Kommentare.

Knotenbezeichnungen müssen vor dem Schreiben in Newick maskiert werden. Die folgenden Beispiele zeigen, wie eine Knotenbezeichnung (links) vor dem Schreiben (rechts) transformiert wird.

• abc→abc
• a b→ a_boder'a b'
• a_b→'a_b'
• a (b→'a (b'
• a()[],; :->'a()[],; :'
• a'b→'a''b'
• a''b→'a''''b'

Die umgekehrte Transformation muss beim Lesen eines Newick-Baums durchgeführt werden. Software, die diese Transformationen nicht implementiert, implementiert das Newick-Format nicht korrekt.

Das New Hampshire X (NHX)-Format ist eine Erweiterung des Newick-Formats, die Newick-Knoten um Schlüssel-Wert-Paare (z. B. Genduplikationen) ergänzt. Dies geschieht durch die Angabe der zusätzlichen Daten in eckigen Klammern innerhalb der Knotenbezeichnungen. Die Klammern werden verwendet, da sie im Nexus-Dateiformat Kommentare darstellen . Parser, die diese zusätzlichen Informationen nicht interpretieren, ignorieren sie daher. ^{[ 4 ]}[&&NHX:key=value:...]

Manche phylogenetische Software unterscheidet zwischen Knoten- und Astannotationen. Das Standard-Newick-Format ist hingegen:

<node_label>:<branch_length> 

Knoten- und Zweigannotationen lassen sich dadurch unterscheiden, dass die Knotenattribute vor dem Doppelpunkt und die Zweigattribute nach dem Doppelpunkt platziert werden:

node4[&node_age=10,node_color=blue]:[&branch_posterior_probability=0.7]1.0 

oder

node4[&node_age=10,node_color=blue]:1.0[&branch_posterior_probability=0.7] 

Attributes represent key=value pairs that are separated by commas.

Some software packages do not distinguish between node and branch comments. BEAST does distinguish between them, although only for Newick trees contained in a NEXUS file ^[5]. IQ-TREE likewise distinguishes between node and branch comments.

If commas are used to separate key=value pairs, then a special mechanism is required to allow values that contain commas. BEAST allows values to contain multiple elements separated by commas if surrounded by curly braces:

tip1:[&colour={0, 8.0, 1, 12.0, 0}] 20.0 

IQ-TREE instead uses double-quotes to protect values:

:0.0022086528[&gCF="33.33",gCF/gDF1/gDF2/gDFP="33.33/0/33.33/33.33"] 

While the standard Newick notation is limited to phylogenetic trees, Extended Newick (Perl Bio::PhyloNetwork) can be used to encode explicit phylogenetic networks.^[6] In a phylogenetic network, which is a generalization of a phylogenetic tree, a node either represents a divergence event (cladogenesis) or a reticulation event such as hybridization, introgression, horizontal (lateral) gene transfer or recombination. Nodes that represent a reticulation event are duplicated, annotated by introducing the # symbol into the Newick format, and numbered consecutively (using integer values starting with 1).

For example, if leaf Y is the product of hybridisation (x) between lineages leading to C and D in the tree above,

one can express this situation by defining two trees in standard Newick notation

(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)

or in extended Newick notation

(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 here is a hybrid node. It will be joined by the program into a single node when drawn. This is the picture drawn by Dendroscope for this example:

The production rules above is modified by the following for labelling hybrid nodes (in general, nodes representing reticulation events):^[7]

Blatt → Name Hybrid Hybrid → leer | "#" Typ Ganzzahl -- Der Teil #i ist ein obligatorischer Bezeichner für einen Hybridknoten Typ → leer | Zeichenkette -- Art der Retikulation, z. B. H = Hybridisierung, LGT = lateraler Gentransfer, R = Rekombination. 

Bei der Visualisierung von LGT-Ereignissen wird für einen gegebenen retikulären Knoten üblicherweise eine eingehende Kante als „Akzeptorkante“ und alle anderen eingehenden Kanten als „Transferkanten“ dargestellt. Einige Programme (z. B. Dendroscope und SplitsTree ) erlauben es, genau eine Kopie des retikulären Knotens mit einem Symbol zu kennzeichnen, ##um anzuzeigen, dass sie der Akzeptorkante entspricht.

Die erweiterte Newick-Architektur ist rückwärtskompatibel: Ein Hybridknoten würde von älteren Parsern einfach als eine Ansammlung seltsam benannter Knoten interpretiert werden.

Das Rich-Newick-Format, auch bekannt als Rice- Newick-Format, ist eine Weiterentwicklung des Extended-Newick-Formats. ^{[ 8 ]} Es bietet zusätzliche Unterstützung für:

• Unwurzelte Phylogenien. Dies geschieht einfach, indem man wie gewohnt einen unwurzelten Baum zeichnet (d. h. eine beliebige Wurzel an einem binären Verzweigungspunkt wählt) und [&U]dem String ein Präfix voranstellt. [&R]kann hingegen verwendet werden, um einen gewurzelten Baum zu erzwingen.
• Bootstrap-Werte und -Wahrscheinlichkeiten werden berechnet. Dies geschieht durch Hinzufügen weiterer :[bootstrap]:[prob]Felder nach der Längenangabe; Felder können leer bleiben, solange Doppelpunkte vorhanden sind. Dies kann zu Inkompatibilitäten mit älteren Systemen führen.

Einige andere Programme, wie NWX, verwenden Kommentare, die mit beginnen &, um zusätzliche Informationen ad hoc zu kodieren: ^{[ 9 ].}

• MrBayes und BEAST fügen den Knoten zusätzliche Informationen wie Wahrscheinlichkeit, Länge in Jahren und Standardabweichung der Werte hinzu. Sie verwenden außerdem [%U].

Zur Visualisierung von Newick-Baumdaten wurden zahlreiche Werkzeuge veröffentlicht. Beispiele hierfür sind das ETE-Toolkit („Environment for Tree Exploration“) ^{[ 10 ]} und T-REX ^{[ 11 ]} . Phylogenetische Softwarepakete wie SplitsTree und der Baumbetrachter Dendroscope sowie das Online-Tool IcyTree unterstützen sowohl die Standard- als auch die erweiterte Newick-Notation, während die Software PhyloNet für phylogenetische Netzwerke sowohl das Extended-Newick- als auch das Rich-Newick-Format verwendet.

• Es gibt keine Standardmethode, um festzulegen, dass in Newick-Kommentaren angegebene Attribute der entsprechenden Kante und nicht dem Knoten zugeordnet werden. Werden Kantenattribute als Knotenattribute behandelt, landen sie nach dem Neuverwurzeln des Baums auf der falschen Kante.
• Es gibt keine Standardmethode, um Attribute anzugeben, die enthalten ], oder ,. ]würde den Kommentar beenden und ,wird häufig als Attributtrennzeichen verwendet.

• phyloXML
• NeXML-Format
• Das Smart Game Format ist eine Anwendung des Newick-Formats und wird häufig zur Aufzeichnung von Brettspielen verwendet.

• Phylogramm der Höheren Säugetiere nach Miyamoto und Goodman. Ein Beispiel für ein großes Phylogramm mit seiner Darstellung im Newick-Format.
• Phylogenetischer Baum-Viewer (Newick) (Von Huerta-Cepas et al. 2016)