Formato Newick

En matemáticas, el formato de árbol Newick (o notación Newick , o formato de árbol de Nuevo Hampshire) es una manera de representar árboles utilizando paréntesis y comas. Fue adoptado por James Archie, William H. E. Día, Joseph Felsenstein, Wayne Maddison, Christopher Meacham, F. James Rohlf, y David Swofford, durante dos reuniones en 1986, la segunda de las cuales transcurrió en el restaurante Newick de Dover, Nuevo Hampshire, EE.UU. Este formato es una generalización del formato desarrollado por Meacham en 1984 para el primer programa de dibujo de árboles, incluido en el paquete de programas PHYLIP.​

Ejemplos

El árbol siguiente:

podría ser representado en el formato Newick de varias formas

(,,(,));                            vértices sin nombre
(A,B,(C,D));                        hojas con nombre
(A,B,(C,D)E)F;                      todos los vértices con nombre     
(:0.1,:0.2,(:0.3,:0.4):0.5);        vértices(excepto la raíz) con distancias al vértice parental     
(:0.1,:0.2,(:0.3,:0.4):0.5):0.0;    vértices con distancias al vértice parental    
(A:0.1,B:0.2,(C:0.3,D:0.4):0.5);    distancias y nombres (hojas)
(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F;  distancias y   nombres (todos)

El formato Newick es típicamente utilizado en herramientas como PHYLIP y es una definición mínima para un árbol filogenético.

Árboles con raíz, sin raíz y binarios

Cuándo un árbol sin raíz se representa en notación Newick, se elige como raíz un vértice arbitrario. Tanto si tiene raíz como si no, normalmente la representación de un árbol tiene la raíz asignada a un vértice interno o punto de ramificación y es muy raro encontrarla asignada a un vértice externo u hoja.

En un árbol binario que tiene la raíz asignada en un vértice interno, cada uno de estos vértices internos se ramifica en dos vértices. En cambio, en un árbol binario sin raíz al que se le ha asignado la raíz aleatoriamente, el vértice raíz se ramifica en tres vértices y cada uno de los vértices internos se ramifica en dos vértices. En un árbol binario con raíz asignada a una hoja, el vértice raíz tiene como mucho un vértice que desciende de él, y cada vértice interno se ramifica en dos vértices.

Gramática

Vocabulario

   Tree: La entrada en formato Newick para un árbol completo
   Subtree: un vértice interno (y sus descendientes) o un vértice hoja
   Leaf: un vértice sin descendientes
   Internal: un vértice y su/s descendiente/s
   BranchSet: un conjunto de una o más ramas
   Branch: una rama del árbol y su descendiente subárbol
   Name: el nombre de un vértice
   Length: la longitud de una rama del árbol

Nota: "|" separa alternativas.

   Tree → Subtree ";" | Branch ";"
   Subtree → Leaf | Internal
   Leaf → Name
   Internal → "(" BranchSet ")" Name
   BranchSet → Branch | Branch "," BranchSet
   Branch → Subtree Length
   Name → vacío | string
   Length → vacío | ":" número

Los espacios en blanco dentro del número están prohibidos. Los espacios en blanco dentro de string están a menudo prohibidos. Espacios en blanco en cualquier otro lugar son ignorados. A veces el string tiene que ser de una determinada longitud para que los signos de puntuación (punto y coma, coma, paréntesis) estén admitidos. El Tree --> Branch ";" a veces está prohibido, ya que produce que la descendencia proceda de la nada, lo cuál no tiene sentido.

Presta atención a que cuando a un árbol con más de una hoja se le asigna la raíz a una de sus hojas (algo que ocurre rara vez en la práctica), dicha hoja raíz se caracteriza como un vértice Internal según la gramática explicada anteriormente. Generalmente, un vértice raíz etiquetado como Internal debe ser tratado como una hoja si y solo si tiene exactamente un Branch en su BranchSet. Uno puede hacer una gramática que fortalezca esta distinción reemplazando la anterior regla de producción de Tree con:

   Tree → RootLeaf ";" | RootInternal ";" | Branch ";"
   RootLeaf → Name | "(" Branch ")" Name
   RootInternal → "(" Branch "," BranchSet ")" Name

El primer RootLeaf la producción es para un árbol con exactamente una hoja. El segundo RootLeaf la producción es para arraigar un árbol de uno de su dos o más hojas.

Visualización

Varias herramientas han sido publicadas para visualizar datos de árboles Newick, como el ETE toolkit ("Entorno para Exploración de Árbol") y T-REX.​​

Enlaces externos

• Gary Olsen's Interpretation of the "Newick's 8:45" Tree Format Standard [1]
• Miyamoto and Goodman's Phylogram of Eutherian Mammals An example of a large phylogram with its Newick format representation.
• Phylogenetic tree (newick) viewer (By Huerta-Cepas et al. 2016)