Format Newick

En mathématiques et en phylogénétique , le format d'arbre de Newick (ou notation de Newick ou format d'arbre de New Hampshire ) est une manière de représenter des arbres de la théorie des graphes avec des longueurs d'arêtes en utilisant des parenthèses et des virgules. Il a été adopté par James Archie, William HE Day, Joseph Felsenstein , Wayne Maddison , Christopher Meacham, F. James Rohlf et David Swofford, lors de deux réunions en 1986, la seconde ayant eu lieu au restaurant Newick's à Dover , dans le New Hampshire, aux États-Unis. Le format adopté est une généralisation du format développé par Meacham en 1984 pour les premiers programmes de dessin d'arbres dans le package PHYLIP de Felsenstein .

L'arbre suivant :

pourrait être représenté au format Newick de plusieurs manières

(,,(,)); aucun nœud n'est nommé (A,B,(C,D)); les nœuds feuilles sont nommés (A,B,(C,D)E)F; tous les nœuds sont nommés (:0.1,:0.2,(:0.3,:0.4):0.5); tous sauf le nœud racine ont une distance au parent (:0.1,:0.2,(:0.3,:0.4):0.5):0.0; tous ont une distance au parent (A:0.1,B:0.2,(C:0.3,D:0.4):0.5); distances et noms de feuilles 
(populaires) (A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F; distances et tous les noms ((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A; un arbre enraciné sur un nœud de feuille 
(rare)

Le format Newick est généralement utilisé pour des outils comme PHYLIP et constitue une définition minimale d'un arbre phylogénétique .

Lorsqu'un arbre non enraciné est représenté en notation Newick, un nœud arbitraire est choisi comme racine. Qu'il soit enraciné ou non, la représentation d'un arbre est généralement enracinée sur un nœud interne et il est rare (mais légal) d'enraciner un arbre sur un nœud feuille.

Un arbre binaire enraciné qui est enraciné sur un nœud interne a exactement deux nœuds descendants immédiats pour chaque nœud interne. Un arbre binaire non enraciné qui est enraciné sur un nœud interne arbitraire a exactement trois nœuds descendants immédiats pour le nœud racine, et chaque autre nœud interne a exactement deux nœuds descendants immédiats. Un arbre binaire enraciné à partir d'une feuille a au plus un nœud descendant immédiat pour le nœud racine, et chaque nœud interne a exactement deux nœuds descendants immédiats.

Une grammaire pour analyser le format Newick (basée approximativement sur ) :

Arbre : Le format Newick d'entrée complet pour un arbre unique Sous- arbre : un nœud interne (et ses descendants) ou un nœud feuille Feuille : un nœud sans descendant Interne : un nœud et un ou plusieurs de ses descendants BranchSet : un ensemble d'une ou plusieurs branches Branche : une arête d'arbre et son sous-arbre descendant. Nom : le nom d'un nœud Longueur : la longueur d'une arête d'arbre. 

Remarque : « | » sépare les alternatives.

Arbre → Sous-arbre ";" Sous-arbre → Feuille | Feuille interne → Nom Interne → "(" BranchSet ")" Nom BranchSet → Branche | Branche "," BranchSet Branche → Sous-arbre Longueur Nom → vide | chaîne Longueur → vide | ":" nombre

Les espaces (espaces, tabulations, retours chariot et sauts de ligne) dans un nombre sont interdits. Les espaces dans une chaîne sont souvent interdits. Les espaces ailleurs sont ignorés. Parfois, la chaîne Name doit avoir une longueur fixe spécifiée ; sinon, les caractères de ponctuation de la grammaire (point-virgule, parenthèses, virgule et deux-points) sont interdits. La production Tree → Subtree ";" est à la place la production Tree → Branch ";" dans les cas où il est permis d'avoir l'arbre entier descendu de nulle part ; cela capture également la production remplacée car Length peut être vide .

Notez que lorsqu'un arbre ayant plus d'une feuille est enraciné à partir d'une de ses feuilles, une représentation qui est rarement vue dans la pratique, la feuille racine est caractérisée comme un nœud interne par la grammaire ci-dessus. En général, un nœud racine étiqueté comme interne doit être interprété comme réellement interne si et seulement s'il a au moins deux Branch dans son BranchSet . On peut créer une grammaire qui formalise cette distinction en remplaçant la règle de production Tree ci-dessus par

Arbre → RootLeaf ";" | RootInternal ";" RootLeaf → Nom | "(" Branch ")" Nom 
RootInternal → "(" Branch "," BranchSet ")" Nom

La première production RootLeaf concerne un arbre avec exactement une feuille. La deuxième production RootLeaf concerne l'enracinement d'un arbre à partir d'une de ses deux feuilles ou plus.

• Une chaîne sans guillemets ne peut pas contenir d'espaces, de parenthèses, de crochets, de guillemets simples, de deux points, de points-virgules ou de virgules. Les caractères de soulignement dans les chaînes sans guillemets sont convertis en espaces.
• Une chaîne peut également être citée en l'entourant de guillemets simples. Les guillemets simples dans la chaîne d'origine sont représentés par deux guillemets simples consécutifs.
• Les espaces peuvent apparaître n'importe où, sauf dans une chaîne sans guillemets ou une longueur.
• Les nouvelles lignes peuvent apparaître n'importe où, sauf dans une chaîne ou une longueur .
• Les commentaires sont placés entre crochets. Ils peuvent apparaître partout où les sauts de ligne sont autorisés. Les commentaires commençant par &sont généralement générés par ordinateur pour des données supplémentaires. Certains dialectes autorisent les commentaires imbriqués.

Le format New Hampshire X (NHX) est une extension de Newick qui ajoute des données clé-valeur (duplication de gènes, etc.) aux nœuds Newick. Cela se fait en mettant les données supplémentaires entre parenthèses dans les étiquettes des nœuds. Les parenthèses sont utilisées car elles représentent des commentaires dans le format de fichier Nexus , donc tout analyseur qui ne comprend pas ces informations supplémentaires les ignorera. [&&NHX:key=value:...]

Alors que la notation Newick standard est limitée aux arbres phylogénétiques, la notation Newick étendue (Perl Bio::PhyloNetwork) peut être utilisée pour coder des réseaux phylogénétiques explicites. Dans un réseau phylogénétique , qui est une généralisation d'un arbre phylogénétique , un nœud représente soit un événement de divergence ( cladogénèse ), soit un événement de réticulation tel que l'hybridation , l'introgression , le transfert horizontal (latéral) de gènes ou la recombinaison . Les nœuds qui représentent un événement de réticulation sont dupliqués, annotés en introduisant le symbole # dans le format Newick et numérotés consécutivement (en utilisant des valeurs entières commençant par 1).

Par exemple, si la feuille Y est le produit de l'hybridation (x) entre les lignées conduisant à C et D dans l'arbre ci-dessus,