3.2. Tree Traversal and Navigation

3.2.1. Tree Traversal

3.2.1.1. Iterating Over Nodes

The following example shows how you might evolve a continuous character on a tree by recursively visting each node, and setting the value of the character to one drawn from a normal distribution centered on the value of the character of the node’s ancestor and standard deviation given by the length of the edge subtending the node:

#! /usr/bin/env python

import random
import dendropy

def process_node(node, start=1.0):
    if node.parent_node is None:
        node.value = start
    else:
        node.value = random.gauss(node.parent_node.value, node.edge.length)
    for child in node.child_nodes():
        process_node(child)
    if node.taxon is not None:
        print("%s : %s" % (node.taxon, node.value))

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
process_node(mle.seed_node)

While the previous example works, it is probably clearer and more efficient to use one of the pre-defined node iterator methods:

preorder_node_iter

Iterates over nodes in a Tree object in a depth-first search pattern, i.e., “visiting” a node before visiting the children of the node. This is the same traversal order as the previous example. This traversal order is useful if you require ancestral nodes to be processed before descendent nodes, as, for example, when evolving sequences over a tree.

postorder_node_iter

Iterates over nodes in a Tree object in a postorder search pattern, i.e., visiting the children of the node before visiting the node itself. This traversal order is useful if you require descendent nodes to be processed before ancestor nodes, as, for example, when calculating ages of nodes.

level_order_node_iter

Iterates over nodes in a Tree object in a breadth-first search pattern, i.e., every node at a particular level is visited before proceeding to the next level.

leaf_iter

Iterates over the leaf or tip nodes of a Tree object.

The previous example would thus be better implemented as follows:

#! /usr/bin/env python

import random
import dendropy

def evolve_char(tree, start=1.0):
    for node in tree.preorder_node_iter():
        if node.parent_node is None:
            node.value = 1.0
        else:
            node.value = random.gauss(node.parent_node.value, node.edge.length)
    return tree

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
evolve_char(mle)
for node in mle.leaf_iter():
    print("%s : %s" % (node.taxon, node.value))

The nodes returned by each of these iterators can be filtered if a filter function is passed as a second argument to the iterator. This filter function should take a Node object as an argument, and return True if the node is to be returned or False if it is not. For example, the following iterates over all nodes that have more than two children:

#! /usr/bin/env python

import dendropy

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
multifurcating = lambda x: True if len(x.child_nodes()) > 2 else False
for nd in mle.postorder_node_iter(multifurcating):
    print(nd.description(0))

3.2.1.2. Iterating Over Edges

The Edge objects associated with each Node can be accessed through the edge attribute of the Node object. So it is possible to iterate over every edge on a tree by iterating over the nodes and referencing the edge attribute of the node when processing the node. But it is clearer and probably more convenient to use one of the Edge iterators:

preorder_edge_iter

Iterates over edges in a Tree object in a depth-first search pattern, i.e., “visiting” an edge before visiting the edges descending from that edge. This is the same traversal order as the previous example. This traversal order is useful if you require ancestral edges to be processed before descendent edges, as, for example, when calculating the sum of edge lengths from the root.

postorder_edge_iter

Iterates over edges in a Tree object in a postorder search pattern, i.e., visiting the descendents of the edge before visiting the edge itself. This traversal order is useful if you require descendent edges to be processed before ancestral edges, as, for example, when calculating the sum of edge lengths from the tip

level_order_edge_iter

Iterates over edges in a Tree object in a breadth-first search pattern, i.e., every edge at a particular level is visited before proceeding to the next level.

The following example sets the edge lengths of a tree to the proportions of the total tree length that they represent:

#! /usr/bin/env python

import dendropy

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
mle_len = mle.length()
for edge in mle.postorder_edge_iter():
    edge.length = float(edge.length)/mle_len
print(mle.as_string("newick"))

While this one removes the edge lengths entirely:

#! /usr/bin/env python

import dendropy

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
mle_len = mle.length()
for edge in mle.postorder_edge_iter():
    edge.length = None
print(mle.as_string("newick"))

Like the node iterators, the edge iterators also optionally take a filter function as a second argument, except here the filter function should take an Edge object as an argument. The following example shows how you might iterate over all edges with lengths less than some value:

#! /usr/bin/env python

import dendropy

mle = dendropy.Tree.get_from_path('pythonidae.mle.nex', 'nexus')
short = lambda edge: True if edge.length < 0.01 else False
for edge in mle.postorder_edge_iter(short):
    print(edge.length)

3.2.2. Finding Nodes on Trees

3.2.2.1. Nodes with Particular Taxa

To retrieve a node associated with a particular taxon, we can use the find_taxon_node method, which takes a filter function as an argument. The filter function should take a Taxon object as an argument and return True if the taxon is to be returned. For example:

#! /usr/bin/env python

import dendropy

tree = dendropy.Tree.get_from_path("pythonidae.mle.nex", "nexus")
filter = lambda taxon: True if taxon.label=='Antaresia maculosa' else False
node = tree.find_node_with_taxon(filter)
print(node.description())

Because we might find it easier to refer to Taxon objects by their labels, a convenience method that wraps the retrieval of nodes associated with Taxon objects of particular label is provided:

#! /usr/bin/env python

import dendropy

tree = dendropy.Tree.get_from_path("pythonidae.mle.nex", "nexus")
node = tree.find_node_with_taxon_label('Antaresia maculosa')
print(node.description())

3.2.2.2. Most Recent Common Ancestors

The MRCA (most recent common ancestor) of taxa or nodes can be retrieved by the instance method mrca. This method takes a list of Taxon objects given by the taxa keyword argument, or a list of taxon labels given by the taxon_labels keyword argument, and returns a Node object that corresponds to the MRCA of the specified taxa. For example:

#! /usr/bin/env python

import dendropy

tree = dendropy.Tree.get_from_path("pythonidae.mle.nex", "nexus")
taxon_labels=['Python sebae',
              'Python regius',
              'Python curtus',
              'Python molurus']
mrca = tree.mrca(taxon_labels=taxon_labels)
print(mrca.description())

Note that this method is inefficient when you need to resolve MRCA’s for multiple sets or pairs of taxa. In this context, the PatristicDistanceMatrix offers a more efficient approach, and should be preferred for applications such as calculating the patristic distances between all pairs of taxa.