Replacement tree splicer, date-aware, using ete

[lentinj]

The OneZoom tree is made up of lots of different parts:

• BespokeTree/include_noAutoOTT: A hand-curated set of trees (either original work or lifted from papers), missing OTT annotations, these are added and saved as BespokeTree/include_OTT3.7 (Capital PHY extension = need to add OTTs)
• OpenTreeParts/OpenTree_all: Chunks of the OpenTree that have been downloaded
• OpenTreeParts/OT_required: Orphan chunks of the OpenTree that were downloaded before, and no longer exist
• token_to_oz_tree_file_mapping.py: Mapping of splice name to full filename, a joining edge length & name for the root node (which the sub-tree probably doesn't have)

The newick format has been extended with a syntax to splice trees together, and starting from Base.PHY, this is what happens.

For generating a dated tree, we need to prototype a replacement splicer that:

• Uses ete to do this, and see how well it copes with this many trees in memory
• Translates subtrees from branchlength into date (A non-extinct leaf is date 0, the rest follows from branch length).
• Splices as-per the splicing syntax described
• Produces a tree with date annotations instead of branch lengths
• Writes out a date-annotated tree, which can then be thrown at the date interpolator in a subsequent step. Whether the rest of the pipeline keeps working with dates or we convert back to branch lengths is undecided atm.

Possibly we want to rework the syntax to be slightly more NHX-friendly (i.e. have annotations that include the splicing operations), but isn't essential.

For this to work, we'll also need to:

• Rework Base.PHY to contain date annotations instead of branch lengths (as the only internal subtree).

[lentinj]

The current splicing process is done by build_oz_tree, parsing of newick label format by oz_tokens, get_open_trees_from_one_zoom gets a subtree from the OpenTree.

[lentinj]

I tried both ete3 & ete4.

ete3 (the version that the docs are published for, maybe the stable version?):

• Takes around 30s to parse & iterate over all nodes
• No concept of comments at the beginning of files, had to be manually stripped
• Very angry about empty leaf nodes - bodging the source with a return gets most of them parsing
• ":2345" labels also confuse it
• Doesn't declare it's dependencies

ete4:

• Takes around 10s to parse & iterate over all nodes
• Empty leaf nodes are no longer a problem
• Doesn't choke on comments, but not sure if they end up part of the tree. Not obviously though.
• Uses 1.2 GB of RAM to do so

So using ete4 seems like it should have legs. @jrosindell It'd be good to know if Jonathan's code also uses ete4, or if he has any insider knowledge.

My throwaway script looks like:

# https://etetoolkit.org/docs/latest/tutorial/tutorial_trees.html#reading-and-writing-newick-trees
import argparse
import glob
import itertools
import tracemalloc
import time

import ete4

def main():
    phy_paths = itertools.chain(*(glob.glob(g) for g in [
        "./data/OZTreeBuild/AllLife/OpenTreeParts/OpenTree_all/*.phy",
        "./data/OZTreeBuild/AllLife/BespokeTree/include_OTT3.7/*.phy",
        "./data/OZTreeBuild/AllLife/BespokeTree/include_OTT3.7/*.PHY",
    ]))
    trees = {}
    #tracemalloc.start()
    start_time = time.time()
    for tree_path in phy_paths:
        try:
            # NB: format=1 in ete3, parser=1 in ete4
            trees[tree_path] = ete4.Tree(tree_path, parser=1)
            print("Tree %s: %d nodes" % (
                tree_path,
                len([n.name for n in trees[tree_path].traverse()]),
            ))
        except Exception as e:
            print("Tree %s: Error %s" % (
                tree_path,
                e,
            ))
    print("Elapsed time: %f" % (time.time() - start_time))
    #print("Memory: %f MB" % ((tracemalloc.get_traced_memory()[1] / (1024 * 1024))))


if __name__ == "__main__":
    main()

[hyanwong]

Great. It definitely looks like ete4 is the way forward. Thanks for researching this @lentinj

[jrosindell]

Thanks @lentinj I agree about ETE version 4 though I've asked Jonathan the question for confirmation. A few considerations to add to all this based on the thinking I've done since....

1. we'll need to decide at which stage of the pipeline we fix the positions of leaves and nodes that are imputed based on taxonomy - this is a step in Jonathan's code and can be regarded as a post process of the open tree topology. I believe this is best done before the open tree gets cut into chunks and stiched as per the process being discussed here. Rationale - it's going to be messy if we do the step that moves things around on a tree of mixed origins when the step was desigend as a cleaning step specific to open tree origin tree data. Connected with this step is also the flags attached to nodes and leaves that were imputed at random (as distinct from the separate and later polytomy resolution). This may make more sense after looking at Jonathan's code. Action for now is probably just to see if we agree the principe and be aware of how the full pipeline will be assembled, perhaps wiring up the ETE node metadata system to hold a binary flag for imputation.

2. thinking ahead is it worth supporting a more general set of curation rules that - given things are being re-engineered anyway - might not be any harder to do at this point but will make things more flexible. I'm not absolutely sure what that would look like but it might reduce the curation to three kinds of element, a set of tiny newick trees that were essentially hand written, a set of trees from various sources (mostly from open tree after cleaning) and list of paired identifiers that say which leaf or node of which tree gets stitched to which to which leaf or node of wich other tree as well as which node is the overall root. Rationale - we're also supposed to be providing a tree with extinct species and we know already that open tree cannot be trusted to place more than a tiny proportion of them. @davidebbo 's extinct species tree is thus necessary to incorporate and to be stitched with a range of extant species sub trees and that's going to require a rather longer set of curation rules. We may not worry about it right now but I suspect we'll be worried about it in the future and so it makes sense to future proof ourselves by preparing for more flexible curation tools. Action for now if agreed would be to re-consider how curation rules are recorded - probably the toughest action from this list.

3. continuing on with the extinct species tree considerations - how do we intend to do this in the end? By having two entirely independent sets of curation rules one for extant only and one for extant + extinct together (messy but easier) or by attempting to curate an extinct spcecies tree that will look like what we want for extant species once extinct nodes are all dropped. I guess I prefer the messy but easier option at this stage Rationale: we're expecting to resort to grey data sources for creating the extinct species tree and I think we want our extant species tree to be methodologically unpolluted by any grey data. Action: nothing I guess but just recording how it would all fit together later on.

4. (least important) for scientific purposes and possibly later on for our own downstream data products best practices are now to provide a set of many trees created by repeating the build process which has stochastic elements standing in for uncertainty. This wil be true both for the cleaned open tree data and for some of the curated trees themselves as supplied by third parties (e.g. the one bird tree we have was actually picked from a collection of 10,000 others that the authors generated at the time). I think it's worth being mindful of the potential future need to support this. In practice there's probably not much to it it means a single curated tree might be substituted for a folder of the same name containing many files with some idenifying number on the end. The code would just choose a random one of those files and we'd then need to run our entire pipeline multiple times if wanted to end up with such a distribution. Action: nothing for now I think except just to record this and to be mindful not to commit to something that might make this step prohibitively hard in future.

[lentinj]

we'll need to decide at which stage of the pipeline we fix the positions of leaves and nodes that are imputed based on taxonomy

Didn't we decide that we weren't doing this, and only worrying about interpolating dates? Apart from that agreed, working on individual subtrees seems much more sensible.

thinking ahead is it worth supporting a more general set of curation rules

From what I saw yesterday, the existing rules are pretty flexible and I couldn't imagine any obvious near-term needs (and presumably @hyanwong doesn't either, as they'd be implemented by now). It is tempting to:

• Move the syntax into an attribute, so some of the parsing is done for free by ete
• Move the mapping in token_to_oz_tree_file_mapping.py to node attributes, which seems like it'd be cleaner (OTOH, maybe this file is a useful point for switching out multiple potential data sources?)

...but neither of these are particularly important, and would cause a bunch of upheaval in the pipeline for not much gain.

downstream data products best practices are now to provide a set of many trees created by repeating the build process which has stochastic elements standing in for uncertainty

Ultimately we have to end up with one tree though, and storing all possible trees doesn't gain us much. Having a tree-of-the-week, or BushOfAllPossiblePermutationsZoom don't seem like they'd be very helpful. I'm presuming that any literature would make it a relatively informed choice, e.g. there'd be likelihood scores for the 000's of trees they provide?

What we could do to include this is encode the branch uncertainty into the tree (what proportion of trees also have a path between x & y), and map that to branch opacity (as already happens to a degree, although I'm not sure where that comes from now).

[jrosindell]

Didn't we decide that we weren't doing this, and only worrying about interpolating dates? Apart from that agreed, working on individual subtrees seems much more sensible.

I think we're at cross purposes - in original OZ tree build there was just one kind of step which was polytomy resolution. Now there are two kinds - polytomy resolution (of a real polytomy in source data) and fixing of leaves and nodes that are 'dumped' by open tree as a polytomy somewhere beacuse there is no phylogenetic data at all. Jonathan's code will fix the 'dumped' species by reference to the tree and taxonomy inserting them instead without a polytomy at least in a place where they could have been. So this second step which is specific to open tree sourced data only will need to be done before the full tree is stitched whilst the real polytomy resolution is done afterwards with no changes being needed to that part

From what I saw yesterday, the existing rules are pretty flexible and I couldn't imagine any obvious near-term needs

Fair enough just thought it was worth a flag

Ultimately we have to end up with one tree though

Yes, this would not be for the visualisaiton - it would be for if we want to calculate statistics on the tree with propagated error - more for science uses of the data set than for OneZoom itself. Again more of a mention rather than a feature needed at present.

[lentinj]

I've pushed a WIP build_oz_tree replacement here ab32b80 if it's interesting. As the comment says, there's 3 differences now:

• Rounding errors in branch_length outputs: We've decided it's not really relevant.

  >>> ete4.Tree("(a:123.456789);").write()
  '(a:123.457);'

• Strings can become quoted: They can, but it's removing quotes that weren't needed, not adding them. A non-issue.

  >>> ete4.Tree("(a 2:1);").write()
  "('a 2':1);"

• The root node name gets lost, even when we turn on internal node names: Turns out there's a format_root_node option

  >>> ete4.Tree("((moo,oink)sounds)baa;",parser=1).write(parser=1)
  '((moo,oink)sounds);'

[lentinj]

I started graphing the pipeline & additions, to get it straight in my head at least. I've not finished adding Jonathan's parts on the right hand side, but may be useful anyway:

flowchart TD
    classDef Green fill:#BDFFA4;
    OT_required/[OT_required/: orphan OT parts]
    BespokeTree/include_noAutoOTT[BespokeTree/include_noAutoOTT: Custom tree parts]
    BespokeTree/Include_OTTxxx[BespokeTree/Include_OTTxxx: Custom tree parts w/OTT]
    OpenTreeParts/OpenTree_all/[OpenTreeParts/OpenTree_all/: Subtrees]
    ordered_nodes[OneZoom ordered_nodes&age column dump]:::Green
    BespokeTree/Include_OTTxxxage:::Green

    add_existing_ages_to_trees( )
    build_oz_tree( )
    

    BespokeTree/include_noAutoOTT--add_ott_numbers_to_trees-->BespokeTree/Include_OTTxxx
    BespokeTree/Include_OTTxxx-->add_existing_ages_to_trees:::Green
    ordered_nodes-->add_existing_ages_to_trees
    add_existing_ages_to_trees--add_existing_ages_to_trees-->BespokeTree/Include_OTTxxxage
    OT_required/--cp-->OpenTreeParts/OpenTree_all/
    labelled_supertree.tre--get_open_trees_from_one_zoom-->OpenTreeParts/OpenTree_all/

    BespokeTree/Include_OTTxxxage-->build_oz_tree
    OpenTreeParts/OpenTree_all/-->build_oz_tree
    build_oz_tree--build_oz_tree-->AllLife_full_tree.phy

Loading

[lentinj]

The core of what we need to add is node_ages.json, a dump from Chronosynth (I think?), with entries like:

    "mrcaott100191ott148281": [
      {
        "age": 69.35051,
        "source_id": "ot_502@tree1",
        "source_node": "node972"
      },
      {
        "age": 107.590831,
        "source_id": "ot_502@tree2",
        "source_node": "node2579"
      }
    ],

Basically we need to select the median age from the list, and then apply it to any nodes mentioned in the file.

To be able to do this, bff17ee ditches the mrcaottXXXottYYY-removal until much later in the pipeline, after we've stopped caring about them. We have to keep doing the " " -> "_" though, since at very least the tree-build newick parser relies on them. I'm guessing all sorts of other bugs will come out the woodwork too.

[hyanwong]

Oh yes, I forgot that we need mrcaottXXXottYYY to match up dates. Let's keep those labels in until the last minute then

[lentinj]

Right, I've updated the branch with a version that can produce a dated tree: main...issue-120-tree-splicer

• I've preserved the original build_oz_tree, partially to act as an acceptance test, partially so things can keep working if we choose to merge this branch. Any preferences @hyanwong ? Should we just get on with it and replace build_oz_tree?
• I've also simplified the process so we know where OT_required is, and there's no manual copy step any more.
• We've 2 strategies for adding dates, apply_node_ages which uses node_ages.json to apply dates to any OTTs in that file, and ages_from_dist that uses branch length. Currently we apply the former to OT trees and base.phy (so we get an estimate for biota, which is required), the latter to any other bespoke trees. Feels like we should get rid of this special case, either with a combined function or try the latter first, if that doesn't work try the former. (EDIT: I'm fairly convinced after mulling it that having a single combined strategy---use branch_lengths, fall back to known OTT dates when they don't exist---would simplify matters and seems reasonable).
• What do we want to send further into the pipeline, dates or branch lengths?
• And somewhat pedantically, should the "date" node property actually be called "age"? It would be more consistent.

EDIT: also

• I've not documented where node_ages.json comes from, because I'm not sure. But I'm assuming it's an API call somewhere?

[lentinj]

Assuming this is in reasonable shape, the next steps would be:

• Remove the old build_oz_tree.py & merge this
• Document how to get node_ages.json

...and actually do something with the data :) Based on James' demo:

• Ensure we populate OneZoom's existing age column with our new data
• Pre-generate a graphiclength.bin, with per-node graphiclength. I'm assuming that ete4 can already generate WMBL anyway, so that part should be pretty quick
• Do we need files with WMBL in too? Or is the derived value enough?