Tree operations

Tree-related operations.

Sorting, changing the root to a node, moving branches, removing (prunning)…

class Walker(root)

Represents the position when traversing a tree.

add_next_branch(self)
property first_visit
go_back(self)
property has_unvisited_branches
property node
property node_id
add_branch_values(root, dist_fn, support_fn)

Add distances and support values to the branches.

add_leaf_names(root, names)

Add names to the leaves.

assert_root_consistency(root, bprops=None)

Raise AssertionError if the root node of a tree looks inconsistent.

common_ancestor(nodes)

Return the last node common to the lineages of the given nodes.

If the given nodes don’t have a common ancestor, it will return None.

Parameters:

nodes – List of nodes whose common ancestor we want to find.

create_dichotomic_sister(tree)

Make tree start with a dichotomy, with the old tree and a new sister.

farthest(tree, topological=False)

Return the farthest nodes and the diameter of the tree.

farthest_descendant(tree, topological=False)

Return the farthest descendant and its distance.

insert_intermediate(node, intermediate, bprops=None, dist=None)

Insert, between node and its parent, an intermediate node.

interchange_references(node1, node2)

Interchange the references of the given nodes.

node1 will point where node2 was, and viceversa.

join_branch(node, bprops=None)

Substitute node for its only child.

ladderize(tree, topological=False, reverse=False)

Sort branches according to the size of each partition.

Parameters:

  • topological – If True, the distance between nodes will be the number of nodes between them (instead of the sum of branch lenghts).

  • reverse – If True, sort with biggest partitions first.

Example:

t = Tree('(f,((d,((a,b),c)),e));')
print(t)
#   ╭╴f
# ──┤     ╭╴d
#   │  ╭──┤  ╭──┬╴a
#   ╰──┤  ╰──┤  ╰╴b
#      │     ╰╴c
#      ╰╴e

t.ladderize()
print(t)
# ──┬╴f
#   ╰──┬╴e
#      ╰──┬╴d
#         ╰──┬╴c
#            ╰──┬╴a
#               ╰╴b
make_name(i, chars='abcdefghijklmnopqrstuvwxyz')

Return a short name corresponding to the index i.

midpoint(tree, topological=False)

Return the node in the middle and its distance from the exact center.

move(node, shift=1)

Change the position of the current node with respect to its parent.

populate(tree, size, names=None, model='yule', dist_fn=None, support_fn=None)

Populate tree with a dichotomic random topology.

Parameters:

  • size – Number of leaves to add. All necessary intermediate nodes will be created too.

  • names – Collection (list or set) of names to name the leaves. If None, leaves will be named using short letter sequences.

  • model –

    Model used to generate the topology. It can be:

    • ”yule” or “yule-harding”: Every step a randomly selected leaf grows two new children.

    • ”uniform” or “pda”: Every step a randomly selected node (leaf or interior) grows a new sister leaf.

  • dist_fn – Function to produce values to set as distance in newly created branches, or None for no distances.

  • support_fn – Function to produce values to set as support in newly created internal branches, or None for no supports.

populate_uniform(root, size)

Populate with the uniform model a topology with size leaves.

populate_yule(root, size)

Populate with the Yule-Harding model a topology with size leaves.

rehang(root, child_pos, bprops=None)

Rehang root on its child at position child_pos and return it.

remove(node)

Remove the given node from its tree.

resolve_polytomy(tree, descendants=True)

Convert tree to a series of dicotomies if it is a polytomy.

A polytomy is a node that has more than 2 children. This function changes them to a ladderized series of dicotomic branches. The tree topology modification is arbitrary (no important results should depend on it!).

Parameters:

descendants – If True, resolve all polytomies in the tree, including all root descendants. Otherwise, do it only for the root.

root_at(node, bprops=None)

Set the given node as the root of the tree.

The original root node will be used as the new root node, so any reference to it in the code will still be valid.

Parameters:

  • node – Node to set as root. Its reference will be lost.

  • bprops – List of branch properties (other than “dist” and “support”).

set_midpoint_outgroup(tree, topological=False)
set_outgroup(node, bprops=None, dist=None)

Change tree so the given node is set as outgroup.

The original root node will be used as the new root node, so any reference to it in the code will still be valid.

Parameters:

  • node – Node to set as outgroup (future first child of the root).

  • bprops – List of branch properties (other than “dist” and “support”).

  • dist – Distance from the node, where we put the new root of the tree.

sort(tree, key=None, reverse=False)

Sort the tree in-place.

swap_props(n1, n2, props)

Swap properties between nodes n1 and n2.

to_dendrogram(tree)

Convert tree to dendrogram (remove all distance values).

to_ultrametric(tree, topological=False)

Convert tree to ultrametric (all leaves equidistant from root).

traverse(tree, order=-1, is_leaf_fn=None)

Traverse the tree and yield nodes in pre (< 0) or post (> 0) order.

traverse_bfs(tree, is_leaf_fn=None)

Yield nodes with a breadth-first search (level order traversal).

unroot(tree, bprops=None)

Unroot the tree (make the root not have 2 children).

The convention in phylogenetic trees is that if the root has 2 children, it is a “rooted” tree (the root is a real ancestor). Otherwise (typically a root with 3 children), the root is just an arbitrary place to hang the tree.

update_size(node)

Update the size of the given node.

update_sizes_all(tree)

Update sizes of all the nodes in the tree.

update_sizes_from(node)

Update the sizes from the given node to the root of the tree.

walk(tree)

Yield an iterator as it traverses the tree.