Module Expr Str ImportFrom alias alias ImportFrom alias Assign NameStore Call NameLoad Str FunctionDef arguments args NameParam defaults body Assign NameStore Call NameLoad Str Assign NameStore NameLoad Assign NameStore Str Assign NameStore Num TryExcept body For TupleStore NameStore NameStore Call NameLoad Call NameLoad NameLoad Call NameLoad Num body If CompareNotIn NameLoad NameLoad body Pass orelse If BoolOpAnd CompareEq NameLoad Str CompareNotEq NameLoad Str CompareGt NameLoad Num body Pass orelse If BoolOpAnd CompareEq NameLoad Str CompareNotEq NameLoad Str body Pass orelse If BoolOpAnd CompareEq NameLoad Str CompareNotEq NameLoad Str CompareEq NameLoad Num body Pass orelse If BoolOpAnd CompareEq NameLoad Str CompareNotEq NameLoad Str body AugAssignSub NameStore Num orelse If BoolOpAnd CompareEq NameLoad Str BoolOpOr CompareEq NameLoad Str CompareEq NameLoad Str body AugAssignAdd NameStore Num orelse Raise Call NameLoad Assign NameStore NameLoad Assign NameStore NameLoad handlers ExceptHandler type NameLoad body Return TupleLoad NameLoad Dict Return TupleLoad UnaryOpNot NameLoad Dict decorator_list Call AttributeLoad NameLoad attr FunctionDef arguments args NameParam NameParam defaults NameLoad body Assign NameStore ListLoad Assign NameStore Num Assign NameStore Str Assign NameStore NameLoad Assign NameStore Call NameLoad Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad For NameStore Call NameLoad NameLoad keyword NameLoad body If CompareNotIn NameLoad Str body If UnaryOpNot NameLoad body Assign AttributeStore SubscriptLoad SubscriptLoad NameLoad Index Num Index Num attr IfExp NameLoad NameLoad NameLoad orelse Assign NameStore NameLoad If CompareEq NameLoad Str body Assign NameStore NameLoad orelse If CompareEq NameLoad Str body TryExcept body Assign AttributeStore SubscriptLoad SubscriptLoad NameLoad Index Num Index Num attr Call NameLoad NameLoad handlers ExceptHandler type NameLoad body Raise Call NameLoad BinOpMod Str NameLoad orelse If CompareEq NameLoad Str body AugAssignAdd NameStore Num Expr Call AttributeLoad NameLoad attr TupleLoad Call NameLoad NameLoad orelse If CompareEq NameLoad Str body Expr Call AttributeLoad NameLoad attr TupleLoad Call NameLoad NameLoad orelse If CompareEq NameLoad Str body If CompareLt Call NameLoad NameLoad Num body Raise Call NameLoad Str Assign NameStore ListLoad While CompareEq NameLoad SubscriptLoad SubscriptLoad NameLoad Index Num Index Num body Assign TupleStore NameStore NameStore Call AttributeLoad NameLoad attr Expr Call AttributeLoad NameLoad attr Num NameLoad Assign NameStore SubscriptLoad SubscriptLoad NameLoad Index Num Index Num If AttributeLoad NameLoad attr body Raise Call NameLoad Str For NameStore NameLoad body Assign AttributeStore NameLoad attr NameLoad Assign AttributeStore NameLoad attr NameLoad AugAssignSub NameStore Num orelse If CompareEq NameLoad Str body If CompareEq Call NameLoad NameLoad Num body Return NameLoad Break Assign NameStore NameLoad Raise Call NameLoad Str decorator_list Call AttributeLoad NameLoad attr NameLoad FunctionDef arguments args NameParam NameParam defaults body Assign NameStore Call NameLoad Str Assign NameStore Num Assign NameStore ListLoad TupleLoad NameLoad Num While CompareGt Call NameLoad NameLoad Num body Assign NameStore Call AttributeLoad NameLoad attr Assign TupleStore NameStore NameStore NameLoad If BoolOpAnd AttributeLoad NameLoad attr CompareGtE NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr Str Expr Call AttributeLoad NameLoad attr NameLoad AugAssignAdd NameStore GeneratorExp TupleLoad NameLoad BinOpAdd NameLoad Num comprehension NameStore Call NameLoad AttributeLoad NameLoad attr Assign NameStore BinOpAdd NameLoad Num orelse If CompareLt NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr Str AugAssignSub NameStore Num If AttributeLoad NameLoad attr body Assign NameStore BinOpMod Str Call AttributeLoad AttributeLoad NameLoad attr attr Str Str If Call NameLoad GeneratorExp CompareIn NameLoad NameLoad comprehension NameStore AttributeLoad NameLoad attr body Expr Call AttributeLoad NameLoad attr Str Expr Call AttributeLoad NameLoad attr NameLoad Expr Call AttributeLoad NameLoad attr Str orelse Expr Call AttributeLoad NameLoad attr Call AttributeLoad NameLoad attr Str Str If CompareIsNot AttributeLoad NameLoad attr NameLoad body Expr Call AttributeLoad NameLoad attr Str Expr Call AttributeLoad NameLoad attr BinOpMod Str AttributeLoad NameLoad attr If BoolOpAnd NameLoad CompareEq SubscriptLoad SubscriptLoad NameLoad Index Num Index Num NameLoad body Expr Call AttributeLoad NameLoad attr Str Expr Call AttributeLoad NameLoad attr Str decorator_list Call AttributeLoad NameLoad attr NameLoad FunctionDef arguments args NameParam NameParam defaults NameLoad body Assign NameStore Call NameLoad Str Assign NameStore NameLoad Assign NameStore NameLoad Assign NameStore Str Assign NameStore Str Assign NameStore Num Assign NameStore ListLoad For NameStore NameLoad body For NameStore NameLoad body If BoolOpAnd CompareEq NameLoad Str NameLoad body If BoolOpOr CompareNotEq NameLoad Str CompareEq NameLoad Num body AugAssignAdd NameStore Num If CompareGt NameLoad Num body If BoolOpAnd CompareEq NameLoad Str CompareNotEq NameLoad Str body AugAssignSub NameStore Num Assign NameStore NameLoad Continue If BoolOpAnd NameLoad CompareIn NameLoad NameLoad body Assign NameStore NameLoad Assign NameStore Call AttributeLoad Str attr NameLoad If BoolOpOr CompareEq NameLoad Str UnaryOpNot NameLoad body Expr Yield NameLoad orelse If NameLoad body Expr Yield Call AttributeLoad NameLoad attr Str Str Assign NameStore ListLoad Expr Yield NameLoad orelse If CompareEq NameLoad Str body Assign NameStore UnaryOpNot NameLoad Assign NameStore NameLoad If CompareEq NameLoad Str body Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Str Assign NameStore Str Continue orelse If BoolOpOr UnaryOpNot Call AttributeLoad NameLoad attr UnaryOpNot NameLoad body If BoolOpAnd NameLoad Call AttributeLoad NameLoad attr NameLoad body Raise Call NameLoad Str Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore NameLoad orelse If NameLoad body Assign NameStore NameLoad Continue Assign NameStore NameLoad Assign NameStore NameLoad decorator_list
N/A N/A 
Newick format (:mod:`skbio.io.format.newick`)
=============================================

.. currentmodule:: skbio.io.format.newick

Newick format (``newick``) stores spanning-trees with weighted edges and node
names in a minimal file format [1]_. This is useful for representing
phylogenetic trees and taxonomies. Newick was created as an informal
specification on June 26, 1986 [2]_.

Format Support
--------------
**Has Sniffer: Yes**

+------+------+---------------------------------------------------------------+
|Reader|Writer|                          Object Class                         |
+======+======+===============================================================+
|Yes   |Yes   |:mod:`skbio.tree.TreeNode`                                     |
+------+------+---------------------------------------------------------------+

Format Specification
--------------------
A Newick file represents a tree using the following grammar. See below for an
explanation of the format in plain English.

Formal Grammar
^^^^^^^^^^^^^^
.. code-block:: none

          NEWICK ==> NODE ;
            NODE ==> FORMATTING SUBTREE FORMATTING NODE_INFO FORMATTING
         SUBTREE ==> ( CHILDREN ) | null
       NODE_INFO ==> LABEL | LENGTH | LABEL FORMATTING LENGTH | null
      FORMATTING ==> [ COMMENT_CHARS ] | whitespace | null
        CHILDREN ==> NODE | CHILDREN , NODE
           LABEL ==> ' ALL_CHARS ' | SAFE_CHARS
          LENGTH ==> : FORMATTING NUMBER
   COMMENT_CHARS ==> any
       ALL_CHARS ==> any
      SAFE_CHARS ==> any except: ,;:()[] and whitespace
          NUMBER ==> a decimal or integer

.. note:: The ``_`` character inside of SAFE_CHARS will be converted to a
   blank space in ``skbio.tree.TreeNode`` and vice versa.

   ``'`` is considered the escape character. To escape ``'`` use a
   preceding ``'``.

   The implementation of newick in scikit-bio allows nested comments. To
   escape ``[`` or ``]`` from within COMMENT_CHARS, use a preceding ``'``.

Explanation
^^^^^^^^^^^
The Newick format defines a tree by creating a minimal representation of nodes
and their relationships to each other.

Basic Symbols
~~~~~~~~~~~~~
There are several symbols which define nodes, the first of which is the
semi-colon (``;``). The semi-colon creates a root node to its left. Recall that
there can only be one root in a tree.

The next symbol is the comma (``,``), which creates a node to its right.
However, these two alone are not enough. For example imagine the following
string: ``, , , ;``. It is evident that there is a root, but the other 3 nodes,
defined by commas, have no relationship. For this reason, it is not a valid
Newick string to have more than one node at the root level.

To provide these relationships, there is another structure:
paired parenthesis (``( )``). These are inserted at the location of an existing
node and give it the ability to have children. Placing ``( )`` in a node's
location will create a child inside the parenthesis on the left-most
inner edge.

Application of Rules
~~~~~~~~~~~~~~~~~~~~
Adding a comma within the parenthesis will create two children: ``( , )``
(also known as a bifurcating node). Notice that only one comma is needed
because the parenthesis have already created a child. Adding more commas will
create more children who are siblings to each other. For example, writing
``( , , , )`` will create a multifurcating node with 4 child nodes who are
siblings to each other.

The notation for a root can be used to create a complete tree. The ``;`` will
create a root node where parenthesis can be placed: ``( );``. Adding commas
will create more children: ``( , );``. These rules can be applied recursively
ad. infinitum: ``(( , ), ( , ));``.

Adding Node Information
~~~~~~~~~~~~~~~~~~~~~~~
Information about a node can be added to improve the clarity and meaning of a
tree. Each node may have a label and/or a length (to the parent). Newick always
places the node information at the right-most edge of a node's position.

Starting with labels, ``(( , ), ( , ));`` would become
``((D, E)B, (F, G)C)A;``. There is a named root ``A`` and the root's children
(from left to right) are ``B`` and ``C``. ``B`` has the children ``D`` and
``E``, and ``C`` has the children ``F`` and ``G``.

Length represents the distance (or weight of the edge) that connects a node to
its parent. This must be a decimal or integer. As an example, suppose ``D`` is
rather estranged from ``B``, and ``E`` is very close. That can be written as:
``((D:10, E:0.5)B, (F, G)C)A;``. Notice that the colon (``:``) separates the
label from the length. If the length is provided but the label is omitted, a
colon must still precede the length (``(:0.25,:0.5):0.0;``). Without this, the
length would be interpreted as a label (which happens to be a number).

.. note:: Internally scikit-bio will cast a length to ``float`` which
   technically means that even exponent strings (``1e-3``) are supported)

Advanced Label and Length Rules
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
More characters can be used to create more descriptive labels. When creating a
label there are some rules that must be considered due to limitations in the
Newick format. The following characters are not allowed within a standard
label: parenthesis, commas, square-brackets, colon, semi-colon, and whitespace.
These characters are also disallowed from occurring within a length, which has
a much stricter format: decimal or integer. Many of these characters are
symbols which define the structure of a Newick tree and are thus disallowed for
obvious reasons. The symbols not yet mentioned are square-brackets (``[ ]``)
and whitespace (space, tab, and newline).

What if these characters are needed within a label? In the simple case of
spaces, an underscore (``_``) will be translated as a space on read and vice
versa on write.

What if a literal underscore or any of the others mentioned are needed?
A label can be escaped (meaning that its contents are understood as regular
text) using single-quotes (``'``). When a label is surrounded by single-quotes,
any character is permissible. If a single-quote is needed inside of an escaped
label or anywhere else, it can be escaped with another single-quote.
For example, ``A_1`` is written ``'A_1'`` and ``'A'_1`` would be ``'''A''_1'``.

Inline Comments
~~~~~~~~~~~~~~~
Square-brackets define a comment, which are the least commonly used part of
the Newick format. Comments are not included in the generated objects and exist
only as human readable text ignored by the parser. The implementation in
scikit-bio allows for nested comments (``[comment [nested]]``). Unpaired
square-brackets can be escaped with a single-quote preceding the bracket when
inside an existing comment. (This is identical to escaping a single-quote).
The single-quote has the highest operator precedence, so there is no need to
worry about starting a comment from within a properly escaped label.

Whitespace
~~~~~~~~~~
Whitespace is not allowed within any un-escaped label or in any length, but it
is permitted anywhere else.

Caveats
~~~~~~~
Newick cannot always provide a unique representation of any tree, in other
words, the same tree can be written multiple ways. For example: ``(A, B);`` is
isomorphic to ``(B, A);``. The implementation in scikit-bio maintains the given
sibling order in its object representations.

Newick has no representation of an unrooted tree. Some biological packages make
the assumption that when a trifurcated root exists in an otherwise bifurcated
tree that the tree must be unrooted. In scikit-bio, ``skbio.tree.TreeNode``
will always be rooted at the ``newick`` root (``;``).

Format Parameters
-----------------
The only supported format parameter is `convert_underscores`. This is `True` by
default. When `False`, underscores found in unescaped labels will not be
converted to spaces. This is useful when reading the output of an external
program in which the underscores were not escaped. This parameter only affects
`read` operations. It does not exist for `write` operations; they will always
properly escape underscores.

Examples
--------
This is a simple Newick string.

>>> from io import StringIO
>>> from skbio import read
>>> from skbio.tree import TreeNode
>>> f = StringIO("((D, E)B, (F, G)C)A;")
>>> tree = read(f, format="newick", into=TreeNode)
>>> f.close()
>>> print(tree.ascii_art())
                    /-D
          /B-------|
         |          \-E
-A-------|
         |          /-F
          \C-------|
                    \-G

This is a complex Newick string.

>>> f = StringIO("[example](a:0.1, 'b_b''':0.2, (c:0.3, d_d:0.4)e:0.5)f:0.0;")
>>> tree = read(f, format="newick", into=TreeNode)
>>> f.close()
>>> print(tree.ascii_art())
          /-a
         |
-f-------|--b_b'
         |
         |          /-c
          \e-------|
                    \-d d

Notice that the node originally labeled ``d_d`` became ``d d``. Additionally
``'b_b'''`` became ``b_b'``. Note that the underscore was preserved in `b_b'`.

References
----------
.. [1] http://evolution.genetics.washington.edu/phylip/newick_doc.html
.. [2] http://evolution.genetics.washington.edu/phylip/newicktree.html

 skbio.io create_format NewickFormatError skbio.tree TreeNode N/A newick N/A create_format newick _newick_sniffer N/A N/A fh N/A N/A N/A operators N/A set ,;:() N/A empty True N/A last_token , N/A indent 0 N/A N/A N/A N/A token _ N/A zip N/A _tokenize_newick fh N/A range 100 N/A N/A N/A token operators N/A N/A N/A N/A N/A N/A token , N/A last_token : N/A indent 0 N/A N/A N/A N/A N/A N/A token : N/A last_token : N/A N/A N/A N/A N/A N/A token ; N/A last_token : N/A indent 0 N/A N/A N/A N/A N/A N/A token ) N/A last_token : N/A N/A indent 1 N/A N/A N/A N/A token ( N/A N/A last_token ( N/A last_token , N/A N/A indent 1 N/A N/A N/A NewickFormatError N/A last_token token N/A empty False N/A N/A N/A NewickFormatError N/A N/A N/A False N/A N/A N/A N/A empty N/A N/A N/A N/A newick sniffer _newick_to_tree_node N/A N/A fh convert_underscores N/A True N/A N/A tree_stack N/A N/A current_depth 0 N/A last_token N/A next_is_distance False N/A root N/A TreeNode N/A N/A N/A tree_stack append N/A root current_depth N/A token N/A _tokenize_newick fh convert_underscores convert_underscores N/A N/A N/A last_token (,): N/A N/A N/A next_is_distance N/A N/A N/A N/A N/A tree_stack N/A -1 N/A 0 name N/A last_token last_token None N/A N/A next_is_distance False N/A N/A token : N/A N/A next_is_distance True N/A N/A N/A last_token : N/A N/A N/A N/A N/A N/A N/A tree_stack N/A -1 N/A 0 length N/A float token N/A N/A N/A ValueError N/A N/A N/A NewickFormatError N/A Could not read length as numeric type: %s. token N/A N/A N/A token ( N/A N/A current_depth 1 N/A N/A N/A tree_stack append N/A N/A TreeNode current_depth N/A N/A N/A token , N/A N/A N/A N/A tree_stack append N/A N/A TreeNode current_depth N/A N/A N/A token ) N/A N/A N/A N/A len tree_stack 2 N/A N/A N/A NewickFormatError Could not parse file as newick. Parenthesis are unbalanced. N/A children N/A N/A N/A current_depth N/A N/A tree_stack N/A -1 N/A 1 N/A N/A N/A node _ N/A N/A tree_stack pop N/A N/A N/A children insert 0 node N/A parent N/A N/A tree_stack N/A -1 N/A 0 N/A N/A parent children N/A N/A N/A NewickFormatError Could not parse file as newick. Contains unnested children. N/A child children N/A N/A N/A child parent parent N/A N/A parent children children N/A current_depth 1 N/A N/A N/A token ; N/A N/A N/A N/A len tree_stack 1 N/A N/A root N/A N/A last_token token N/A N/A NewickFormatError Could not parse file as newick. `(Parenthesis)`, `'single-quotes'`, `[comments]` may be unbalanced, or tree may be missing its root. N/A N/A N/A newick reader TreeNode _tree_node_to_newick N/A N/A obj fh N/A N/A N/A operators N/A set ,:_;()[] N/A current_depth 0 N/A nodes_left N/A N/A obj 0 N/A N/A N/A len nodes_left 0 N/A N/A entry N/A N/A nodes_left pop N/A N/A node node_depth entry N/A N/A N/A node children N/A node_depth current_depth N/A N/A N/A N/A fh write ( N/A N/A N/A nodes_left append entry N/A nodes_left N/A N/A child N/A node_depth 1 N/A child N/A reversed N/A node children N/A current_depth N/A node_depth 1 N/A N/A N/A node_depth current_depth N/A N/A N/A N/A fh write ) N/A current_depth 1 N/A N/A node name N/A N/A escaped N/A %s N/A N/A N/A node name replace ' '' N/A N/A any N/A N/A t operators N/A t N/A node name N/A N/A N/A N/A fh write ' N/A N/A N/A fh write escaped N/A N/A N/A fh write ' N/A N/A N/A N/A fh write N/A N/A escaped replace _ N/A N/A N/A node length None N/A N/A N/A N/A fh write : N/A N/A N/A fh write N/A %s N/A node length N/A N/A nodes_left N/A N/A N/A nodes_left N/A -1 N/A 1 current_depth N/A N/A N/A N/A fh write , N/A N/A N/A fh write ;
 N/A N/A N/A newick writer TreeNode _tokenize_newick N/A N/A fh convert_underscores N/A True N/A N/A structure_tokens N/A set (),;: N/A not_escaped True N/A label_start False N/A last_non_ws_char N/A last_char N/A comment_depth 0 N/A metadata_buffer N/A N/A line fh N/A N/A character line N/A N/A N/A N/A character [ not_escaped N/A N/A N/A N/A last_non_ws_char ' N/A comment_depth 0 N/A N/A comment_depth 1 N/A N/A comment_depth 0 N/A N/A N/A N/A character ] N/A last_non_ws_char ' N/A N/A comment_depth 1 N/A last_non_ws_char character N/A N/A N/A not_escaped N/A character structure_tokens N/A N/A label_start False N/A metadata N/A N/A join metadata_buffer N/A N/A N/A last_non_ws_char ' N/A convert_underscores N/A N/A N/A metadata N/A N/A metadata N/A N/A N/A N/A N/A metadata replace _ N/A metadata_buffer N/A N/A N/A character N/A N/A N/A character ' N/A N/A not_escaped N/A not_escaped N/A label_start True N/A N/A last_non_ws_char ' N/A N/A N/A N/A metadata_buffer append character N/A last_non_ws_char N/A last_char N/A N/A N/A N/A N/A N/A N/A character isspace N/A not_escaped N/A N/A N/A label_start N/A N/A last_char isspace not_escaped N/A N/A N/A NewickFormatError Newick files cannot have unescaped whitespace in their labels. N/A N/A N/A metadata_buffer append character N/A label_start True N/A N/A True N/A N/A last_char character N/A N/A last_char character N/A last_non_ws_char character N/A