Code along video
Learning objectives
In this code along, we will write a recursive method that converts a tree into Newick format, a standard way of representing trees as strings. This will allow us to save the trees that UPGMA produces and visualize them with other software.
Code along summary
Setup
We will continue working in the upgma directory, in datatypes.py, io_util.py, and main.py.
From trees to file formats
Our implementation of UPGMA is now complete, and the provided function read_matrix_from_file() in io_util.py can read a distance matrix and its species names from one of our data files. For example, the first row of the hemoglobin matrix says that the echidna has distance 0 to itself, distance 46 to the goat, distance 63 to the plumed whistling duck, and so on.
But once UPGMA returns a tree, all we have is a list of Node objects living inside our program. We usually want a picture of the tree, and drawing a tree ourselves is a much harder task than the drawings we made earlier in the course.
This is a standard problem in data science. Recall that when we first declared classes, we wrote a __repr__ method that converted a rectangle into a string with a consistent format. Here, we need to do something similar for a tree, except that we need every biologist in the world to agree on the format. This is the role of a file format. Fortunately, biologists have already agreed on a few formats for trees, and the most famous one is called Newick format.
Here is the Newick format for our sample tree from the previous lesson.
((A:3, B:3):1, C:4);
This string may look hideous, but if you gave it to me, I could reconstruct the tree: there is a root connected to the leaf C by an edge of weight 4, and to an internal node by an edge of weight 1, which in turn is connected to A and B by edges of weight 3. As for the name, the biologists who devised the format named it after the place where they were having lunch, Newick’s Lobster House in Dover, New Hampshire. If Newick’s were big fans of recursion, they would probably put up a plaque, because as we will see, Newick format is all about recursion.
Converting a tree to Newick format
In datatypes.py, the Node method to_newick_ages() takes self and returns a string. Like __repr__, it converts an object into a string; specifically, it returns the Newick format of the tree whose root is the current node, without the final semicolon, which we will ignore for now.
The easy case, as usual, is that we are at a leaf. If our tree consisted only of the node C, then its Newick format would just be C. So in our base case, we return the label of the current node.
For the inductive step, let’s consider the simplest possible internal node, internal1, whose two children are both leaves. The Newick format of the tree rooted at internal1 is (A:3, B:3): the Newick format of the left child, a colon, and the weight of the edge leading to it, followed by a comma, followed by the same information for the right child, all in parentheses. The format is cleverly defined so that the same pattern holds as we move up the tree. At the root, the Newick format of the left child is (A:3, B:3), with branch length 1, and the Newick format of the right child is C, with branch length 4.
So, in general, if we are at an internal node, we return a string of the form (Newick format of left child:branch length of left child, Newick format of right child:branch length of right child). The branch length to each child is our age minus the child’s age, and we can obtain the Newick format of each child with a recursive call to to_newick_ages(). In the video, Phillip mentions that a persnickety programmer would take the maximum of each branch length and 0.0, so that rounding errors can never produce a negative branch length; we do so below. We will also use f-strings to format each branch length to six decimal places.
def to_newick_ages(self) -> str:
"""
Recursively serialize this subtree to Newick with branch lengths,
where each branch length = parent.age - child.age.
Returns:
Newick string for this subtree (no trailing semicolon).
"""
if self.is_leaf():
return self.label
left = ""
right = ""
if self.child1 is not None:
branch_length1 = max(self.age - self.child1.age, 0.0)
left = f"{self.child1.to_newick_ages()}:{branch_length1:.6f}"
if self.child2 is not None:
branch_length2 = max(self.age - self.child2.age, 0.0)
right = f"{self.child2.to_newick_ages()}:{branch_length2:.6f}"
return f"({left},{right})"
This method is remarkably short, and yet it can convert any tree into Newick format, whether the tree has three nodes or a thousand. Note that we only label the leaves; our internal nodes have labels like Ancestor Species: 4, but these labels do not appear in the Newick string.
Testing our method
Let’s test to_newick_ages() on our sample tree in main.py. To get the right branch lengths, we need to set the ages of the two internal nodes, which are 3 and 4. Let’s also move the code for our sample tree out of main() and into its own function, sample_tree().
def sample_tree():
leaf1 = Node(label="A")
leaf2 = Node(label="B")
leaf3 = Node(label="C")
internal1 = Node(child1=leaf1, child2=leaf2, age=3)
root = Node(child1=internal1, child2=leaf3, age=4)
print("Total number of leaves:", root.count_leaves())
print("Number of leaves in the tree whose root is A is", leaf1.count_leaves())
print("Number of leaves in tree with root internal1:", internal1.count_leaves())
print("Newick format of tree:", root.to_newick_ages())
When we call sample_tree() from main() and run our code, we obtain the Newick format of the sample tree, except for the final semicolon.
Newick format of tree: ((A:3.000000,B:3.000000):1.000000,C:4.000000)
Adding the semicolon
Newick format demands a semicolon at the end of the string. It is tempting to add the semicolon inside to_newick_ages(), but then a semicolon would appear every time the method is called recursively, including at every internal node. Instead, the semicolon belongs to the tree as a whole, and the provided function to_newick() in io_util.py handles it for us. This function assumes that the root is the last node of the tree, which is the case for the trees that UPGMA produces. Remember that tree[-1] is the same as tree[len(tree)-1].
def to_newick(tree: Tree) -> str:
"""
Convert an entire tree to a Newick-formatted string.
Args:
tree: The phylogenetic tree (root is at tree[-1]).
Returns:
The Newick representation of the tree, terminated with a semicolon.
"""
return f"({tree[-1].to_newick_ages()});"
The provided function write_newick_to_file() in the same file calls to_newick() and writes the result to a file, which is how we will save the trees that UPGMA produces.
Looking ahead
We can now build a tree with UPGMA and convert it into a standard format. In the next code along, we will finish main.py so that we can run UPGMA on real biological datasets from the command line and write the resulting trees to file.
