Working With Tree Data Structures — ETE Toolkit - analysis and visualization of trees

Trees are a widely-used type of data structure that emulates a tree design with a set of linked nodes. Formally, a tree is considered an acyclic and connected graph. Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees grow down, not up as they do in nature). A node that has a child is called the child’s parent node (or ancestor node, or superior). A node has at most one parent.
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).
In bioinformatics, trees are the result of many analyses, such as phylogenetics or clustering. Although each case entails specific considerations, many properties remains constant among them. In this respect, ETE is a python toolkit that assists in the automated manipulation, analysis and visualization of any type of hierarchical trees. It provides general methods to handle and visualize tree topologies, as well as specific modules to deal with phylogenetic and clustering trees.
The Newick format is one of the most widely used standard representation of trees in bioinformatics. It uses nested parentheses to represent hierarchical data structures as text strings. The original newick standard is able to encode information about the tree topology, branch distances and node names. Nevertheless, it is not uncommon to find slightly different formats using the newick standard.
ETE can read and write many of them:
Formats labeled as flexible allow for missing information. For instance, format 0 will be able to load a newick tree even if it does not contain branch support information (it will be initialized with the default value). However, format 2 would raise an exception. In other words, if you want to control that your newick files strictly follow a given pattern you should use strict format definitions.
In order to load a tree from a newick text string you can use the constructor TreeNode or its Tree alias, provided by the main module ete3. You will only need to pass a text string containing the newick structure and the format that should be used to parse it (0 by default). Alternatively, you can pass the path to a text file containing the newick string.
Any ETE tree instance can be exported using newick notation using the Tree.write() method, which is available in any tree node instance. It also allows for format selection (Reading and Writing Newick Trees), so you can use the same function to convert between newick formats.
Any tree topology can be represented as a succession of nodes connected in a hierarchical way. Thus, for practical reasons, ETE makes no distinction between tree and node concepts, as any tree can be represented by its root node. This allows to use any internal node within a tree as another sub-tree instance.
Once trees are loaded, they can be manipulated as normal python objects. Given that a tree is actually a collection of nodes connected in a hierarchical way, what you usually see as a tree will be the root node instance from which the tree structure is hanging. However, every node within a ETE’s tree structure can be also considered a subtree. This means, for example, that all the operational methods that we will review in the following sections are available at any possible level within a tree. Moreover, this feature will allow you to separate large trees into smaller partitions, or concatenate several trees into a single structure. For this reason, you will find that the TreeNode and Tree classes are synonymous.
Each tree node has two basic attributes used to establish its position in the tree: TreeNode.up and TreeNode.children. The first is a pointer to parent’s node, while the later is a list of children nodes. Although it is possible to modify the structure of a tree by changing these attributes, it is strongly recommend not to do it. Several methods are provided to manipulate each node’s connections in a safe way (see Comparing Trees).
In addition, three other basic attributes are always present in any tree node instance:
In addition, several methods are provided to perform basic operations on tree node instances:
This is an example on how to access such attributes:
When a tree is loaded from external sources, a pointer to the top-most node is returned. This is called the tree root, and it will exist even if the tree is conceptually considered as unrooted. This is, the root node can be considered as the master node, since it represents the whole tree structure. Unrooted trees can be identified as trees in which master root node has more than two children.
One of the most basic operations for tree analysis is tree browsing. This is, essentially, visiting nodes within a tree. ETE provides a number of methods to search for specific nodes or to navigate over the hierarchical structure of a tree.
TreeNode instances contain several functions to access their descendants. Available methods are self explanatory:
Often, when processing trees, all nodes need to be visited. This is called tree traversing. There are different ways to traverse a tree structure depending on the order in which children nodes are visited. ETE implements the three most common strategies: preorder, levelorder and postorder. The following scheme shows the differences in the strategy for visiting nodes (note that in both cases the whole tree is browsed):
Every node in a tree includes a TreeNode.traverse() method, which can be used to visit, one by one, every node node under the current partition. In addition, the TreeNode.iter_descendants() method can be set to use either a post- or a preorder strategy. The only different between TreeNode.traverse() and TreeNode.iter_descendants() is that the first will include the root node in the iteration.
strategy can take one of the following values: "postorder", "preorder" or "levelorder"
Additionally, you can implem