Formato Newick

En matemáticas y filogenética , el formato de árbol de Newick (o notación de Newick o formato de árbol de New Hampshire ) es una forma de representar árboles de teoría de grafos con longitudes de aristas usando paréntesis y comas. Fue adoptado por James Archie, William HE Day, Joseph Felsenstein , Wayne Maddison , Christopher Meacham, F. James Rohlf y David Swofford, en dos reuniones en 1986, la segunda de las cuales fue en el restaurante Newick's ^[1] en Dover , New Hampshire, EE. UU. El formato adoptado es una generalización del formato desarrollado por Meacham en 1984 para los primeros programas de dibujo de árboles en el paquete PHYLIP de Felsenstein . ^[2]

El siguiente árbol:

Podría representarse en formato Newick de varias maneras.

(,,(,)); ningún nodo tiene nombre
(A,B,(C,D)); los nodos hoja tienen nombre
(A,B,(C,D)E)F; todos los nodos tienen nombre
(:0.1,:0.2,(:0.3,:0.4):0.5); todos excepto el nodo raíz tienen una distancia al padre
(:0.1,:0.2,(:0.3,:0.4):0.5):0.0; todos tienen una distancia al padre
(A:0.1,B:0.2,(C:0.3,D:0.4):0.5); distancias y nombres de hojas  (populares)
(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F; distancias y todos los nombres
((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A; un árbol enraizado en un nodo de hoja  (raro)

El formato Newick se utiliza normalmente para herramientas como PHYLIP y es una definición mínima de un árbol filogenético .

Cuando se representa un árbol sin raíz en notación Newick, se elige un nodo arbitrario como su raíz. Ya sea con raíz o sin raíz, normalmente la representación de un árbol tiene su raíz en un nodo interno y es poco frecuente (pero legal) tener una raíz en un nodo de hoja.

Un árbol binario enraizado que tiene su raíz en un nodo interno tiene exactamente dos nodos descendientes inmediatos para cada nodo interno. Un árbol binario sin raíz que tiene su raíz en un nodo interno arbitrario tiene exactamente tres nodos descendientes inmediatos para el nodo raíz, y cada uno de los demás nodos internos tiene exactamente dos nodos descendientes inmediatos. Un árbol binario enraizado a partir de una hoja tiene como máximo un nodo descendiente inmediato para el nodo raíz, y cada nodo interno tiene exactamente dos nodos descendientes inmediatos.

Una gramática para analizar el formato Newick (basada aproximadamente en ^[3] ):

Árbol : el formato Newick de entrada completo para un solo árbol Subárbol : un nodo interno (y sus descendientes) o un nodo hoja Hoja : un nodo sin descendientes Interno : un nodo y uno o más descendientes Conjunto de ramas : un conjunto de una o más ramas Rama : una arista de un árbol y su subárbol descendiente. Nombre : el nombre de un nodo Longitud : la longitud de una arista de un árbol.

Tenga en cuenta que "|" separa las alternativas.

Árbol → Subárbol ";" Subárbol → Hoja | Hoja interna → Nombre Interno → "(" BranchSet ")" Nombre BranchSet → Rama | Rama "," BranchSet Rama → Subárbol Longitud Nombre → vacío | cadena Longitud → vacío | ":" número 

Los espacios en blanco (espacios, tabulaciones, retornos de carro y saltos de línea) dentro de un número están prohibidos. Los espacios en blanco dentro de una cadena suelen estar prohibidos. Los espacios en blanco en otros lugares se ignoran. A veces, la cadena Nombre debe tener una longitud fija especificada; de lo contrario, los caracteres de puntuación de la gramática (punto y coma, paréntesis, coma y dos puntos) están prohibidos. La producción Árbol → Subárbol ";" es en cambio la producción Árbol → Rama ";" en aquellos casos en los que se permite que todo el árbol descienda de la nada; esto también captura la producción reemplazada porque Longitud puede estar vacía .

Tenga en cuenta que cuando un árbol que tiene más de una hoja tiene su raíz en una de sus hojas, una representación que rara vez se ve en la práctica, la hoja raíz se caracteriza como un nodo interno por la gramática anterior. En general, un nodo raíz etiquetado como interno debe interpretarse como realmente interno si y solo si tiene al menos dos Branch es en su BranchSet . Se puede crear una gramática que formalice esta distinción reemplazando la regla de producción de árbol anterior con

Árbol → RootLeaf ";" | RootInternal ";" RootLeaf → Nombre | "(" Rama ")" Nombre RootInternal → "(" Rama "," ConjuntoDeRama ")" Nombre

La primera producción de RootLeaf es para un árbol con exactamente una hoja. La segunda producción de RootLeaf es para enraizar un árbol a partir de una de sus dos o más hojas.

• Una cadena sin comillas no puede contener espacios en blanco, paréntesis, corchetes, comillas simples, dos puntos, punto y coma ni comas. Los caracteres de subrayado en cadenas sin comillas se convierten en espacios en blanco. ^[3]
• También es posible poner entre comillas simples una cadena ^{de caracteres. Las comillas simples en la cadena original se representan como dos caracteres de comillas simples consecutivos. [3]}
• Los espacios en blanco pueden aparecer en cualquier lugar excepto dentro de una cadena sin comillas o una longitud.
• Las nuevas líneas pueden aparecer en cualquier lugar excepto dentro de una cadena o una longitud .
• Los comentarios se incluyen entre corchetes y pueden aparecer en cualquier lugar donde se permitan nuevas líneas. ^[3] Los comentarios que comienzan con &son generalmente generados por computadora para obtener datos adicionales. Algunos dialectos permiten comentarios anidados.

El formato New Hampshire X (NHX) es una extensión de Newick que agrega datos de clave-valor (duplicación de genes, etc.) a los nodos de Newick. Esto se hace colocando los datos adicionales entre corchetes en las etiquetas de los nodos. Los corchetes se utilizan porque representan comentarios en el formato de archivo Nexus , por lo que cualquier analizador que no comprenda esta información adicional los ignorará. ^[4][&&NHX:key=value:...]

Si bien la notación Newick estándar se limita a los árboles filogenéticos, se puede utilizar Newick extendido (Perl Bio::PhyloNetwork) para codificar redes filogenéticas explícitas. ^[5] En una red filogenética , que es una generalización de un árbol filogenético , un nodo representa un evento de divergencia ( cladogénesis ) o un evento de reticulación como hibridación , introgresión , transferencia genética horizontal (lateral) o recombinación . Los nodos que representan un evento de reticulación se duplican, se anotan introduciendo el símbolo # en el formato Newick y se numeran consecutivamente (usando valores enteros que comienzan con 1).

Por ejemplo, si la hoja Y es el producto de la hibridación (x) entre linajes que conducen a C y D en el árbol anterior,

Se puede expresar esta situación definiendo dos árboles en notación Newick estándar.

(A,B,((C,Y)c,D)e)f; y (A,B,(C,(Y,D)d)e)f; Newick estándar , todos los nodos tienen nombre (los nodos internos en minúsculas, las hojas en mayúsculas) 

o en notación Newick extendida

(A,B,((C,(Y)x#H1)c,(x#H1,D)d)e)f; Newick extendido, todos los nodos tienen nombre; 1 es el entero que identifica al nodo híbrido x

Aquí x#H1hay un nodo híbrido. El programa los unirá para formar un solo nodo cuando se dibujen. Esta es la imagen dibujada por Dendroscope para este ejemplo:

Las reglas de producción anteriores se modifican de la siguiente manera para etiquetar nodos híbridos (en general, nodos que representan eventos de reticulación): ^[6]

Hoja → Nombre  Híbrido Híbrido → vacío | "#" Tipo entero -- La parte #i es un identificador obligatorio para un nodo híbrido Tipo → vacío | cadena -- tipo de reticulación, p. ej., H = hibridación, LGT = transferencia lateral de genes, R = recombinación. 

En la visualización de eventos LGT, para un nodo reticular dado, un borde entrante se dibuja generalmente como borde "aceptor" y todos los demás bordes entrantes se dibujan como bordes "transferibles". Algunos programas (por ejemplo, Dendroscope y SplitsTree ) permiten etiquetar exactamente una copia del nodo reticular con ##para indicar que corresponde al borde aceptor.

Newick extendido es compatible con versiones anteriores: un nodo híbrido simplemente se interpretaría como unos pocos nodos con nombres extraños para analizadores heredados.

El formato Rich Newick, también conocido como formato Rice Newick, es una extensión adicional de Extended Newick. ^[7] Agrega soporte para:

• Filogenias sin raíz. Esto se hace simplemente escribiendo un árbol sin raíz como de costumbre (es decir, eligiendo una raíz arbitraria en un punto de ramificación binario) y anteponiendo [&U]la cadena. [&R], por otro lado, se puede utilizar para forzar un árbol con raíz.
• Valores y probabilidades de Bootstrap. Esto se hace agregando :[bootstrap]:[prob]campos adicionales después de la longitud; los campos se pueden dejar vacíos siempre que estén presentes los dos puntos. Esto puede ser incompatible con versiones anteriores.

Algunos otros programas, como NWX, utilizan comentarios que comienzan con &para codificar información adicional de manera ad hoc: ^[8]

• MrBayes y BEAST añaden información adicional como probabilidad, duración en años y desviación estándar de los valores a los nodos. También utilizan [%U].

Se han publicado muchas herramientas para visualizar datos de árboles de Newick. Algunos ejemplos específicos incluyen el kit de herramientas ETE ("Environment for Tree Exploration") ^[9] y T-REX . ^[10] Los paquetes de software filogenético como SplitsTree y el visualizador de árboles Dendroscope, así como la herramienta de visualización de árboles en línea IcyTree, pueden manejar la notación Newick estándar y extendida, mientras que el software de red filogenética PhyloNet utiliza tanto el formato Newick extendido como el formato Newick rico.

• filoXML
• T-REX (servidor web) permite manejar árboles filogenéticos y redes en el formato Newick.
• Smart Game Format es una aplicación del formato Newick y se utiliza ampliamente para grabar juegos de mesa.

• Filograma de mamíferos euterios de Miyamoto y Goodman Un ejemplo de un filograma grande con su representación en formato Newick.
• Visualizador de árboles filogenéticos (Newick) (Por Huerta-Cepas et al. 2016)