SuchTree, much article

There are a lot of packages for working with and manipulating phylogenetic trees using python. Rather than compete with packages like dendropy and ete3 on the basis of features, SuchTree does one thing well -- its memory usage and algorithmic complexity scale linearly with the number of taxa in your tree. If you need to work with very large trees, this is very helpful.

Let's have a look at some useful things you can do with trees using the SuchTree class. First, let's get our modules loaded.

To run this notebook on an Ubuntu host, you will need the following system packages installed for ete3 to work :

• python3-pyqt4.qtopengl
• python3-pyqt5.qtopengl

and python packages :

• SuchTree
• pandas
• cython
• scipy
• numpy
• matplotlib
• seaborn
• fastcluster
• dendropy
• ete3

and obviously you'll want jupyter installed so you can run the notebook server. The Internet is full of opinions about how to set up your python environment. You should find one that works for you, but this guide is as good as any to get you started.

I'm going to start off by loading the required packages and suppressing some warnings that should be fixed in the next stable release of seaborn.

I'm going to assume that you are running this notebook out of a local copy of the SuchTree repository for any local file paths.

Let's have a look at some example data. Here is a tree of cichlid fishes from my dissertation :

Loading tree data into SuchTree is pretty simple -- just give it a path to a valid Newick file. Under the hood, SuchTree uses dendropy for parsing. I figured it was better to introduce another dependency than to inflict yet another Newick parser on the world (the Newick file format has some slight ambiguities that can lead to annoying incompatibilities).

The SuchTree object has a dictionary called leafs that maps leaf names onto their node ids. We'll make extensive use of this as we put the utility through its paces.

Calculating distances¶

SuchTree has two ways to calculate distances; one pair a time, or in batches. Batches are more efficient because it does each calculation without the interpreter's overhead.

Here's how to measure distances one at a time :

The distance() function will accept either node ids (which are integers), or taxon names (which are strings).

You can loop over all of the distances one at a time to construct a distance matrix...

Let's look at the distance matrix using a nice seaborn clustermap plot.

It's worth noting that seaborn is using scipy's cluster.hierarchy functions to build those dendrograms from the distance matrix. They aren't going to have exactly the same topology as the input tree, which was build with RAxML.

To calculate the distances in a batch, we can use the distances() function, which takes an $n \times 2$ array of node ids (make sure your array is representing them as integers).

We should get the same distance matrix and clustermap as before.

If you want to use taxon names instead, distances_by_name() accepts an $n \times 2$ list of tuples of taxon names, and looks up the node ids for you.

Loading data from URLs¶

SuchTree can also import data from the internets. Here is the distance matrix for the penguins, from the Global Phylogeny of Birds (I've copied some of their data into a Gist post because their data repository forbids programatic queries).

Comparing the topologies of two large trees¶

So far, we haven't done anything you couldn't do with other phylogenetics packages. SuchTree really shines when you have to do a lot of distance calculations on very large trees.

Here, we use SuchTree to compare the topology of a two trees containing the taxa but constructed with different methods (FastTree and neighbor joining). One million random pairs are sampled from each tree, and the distances compared.

The distances() function, which uses node ids rather than taxa names, would be a little bit faster. However, because the trees have different topologies, the taxa have different node ids in each tree. SuchTree's distances_by_name() function untangles the leaf name to leaf node id mappings for you.

Running with multiple threads¶

Another advantage of SuchTree's support for performing batches of distance calculations is that these calculations can run outside of Python's global interpreter lock. This makes it possible to parallelize with Threads. Python's Thread has less overhead than the multiprocessing package's Process, and Thread objects can access the same memory.

SuchTree intentionally does not allow the user to alter trees once they are created, and so distance calculations are always thread safe. This makes it possible to use only one instance of a tree for all threads, which ought to give you the best chance of keeping it within L3 cache.

First, let's create a Cython function that calls SuchTree outside of the GIL.

Let's set up two queues, one for uncompleted tasks, which we'll call work_q, and one for finished results, which we'll call done_q. The worker threads will pop tasks from the work_q, do some work, and push the results into the done_q.

Let's also push sentinels at the end of the work_q so the workers have a convenient way to know when to shut down.

The worker process takes the two queues as arguments, and returns True when it completes successfully.

Note that we're not using distances_by_name() because it requires a call to Python's dictionary object, which requires the GIL. Instead, we have looked up the node id for each taxon when we created the tasks we pushed onto work_q.

Now we can set up our thread pool, run it and print the results the threads pushed onto done_q.

Threaded algorithms are difficult to implement, and this is a very minimalist approach. It's really only good enough to demonstrate that you can call SuchTree from your worker threads without tripping the interpreter lock.

If you need this capability, you will probably want to study the documentation carefully.