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.[1]

Ejemplos

editar

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

editar

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

editar


Vocabulario

editar
   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.

   TreeSubtree ";" | Branch ";"
   SubtreeLeaf | Internal
   LeafName
   Internal → "(" BranchSet ")" Name
   BranchSetBranch | Branch "," BranchSet
   BranchSubtree Length
   Namevacío | string
   Lengthvací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 cual 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:

   TreeRootLeaf ";" | RootInternal ";" | Branch ";"
   RootLeafName | "(" 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

editar

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

Referencias

editar
  1. The Newick tree format.
  2. Huerta-Cepas, Jaime; Serra, François; Bork, Peer (June 2016). «ETE 3: Reconstruction, Analysis, and Visualization of Phylogenomic Data». Molecular Biology and Evolution (en inglés) 33 (6): 1635-1638. ISSN 0737-4038. PMC 4868116. PMID 26921390. doi:10.1093/molbev/msw046. 
  3. Boc, Alix; Diallo, Alpha Boubacar; Makarenkov, Vladimir (July 2012). «T-REX: a web server for inferring, validating and visualizing phylogenetic trees and networks». Nucleic Acids Research 40 (Web Server issue): W573-579. ISSN 1362-4962. PMC 3394261. PMID 22675075. doi:10.1093/nar/gks485. 

Enlaces externos

editar