matsen/pplacer — Issue #216: `guppy trim` cuts out the fat
Author: matsen
Created: 2012-01-28 20:25:26+00:00
State: open
Labels: top

Connor and I have been having issues doing PCA on big trees because this requires doing eigenproblems on square matrices that are 10,000+ in each dimension.

I realize this morning (head slap) that we just need to trim down the reference tree down to what is represented in the collection of placeruns. This will make everything faster, and will make things like PCA trees easier to visualize.

We will select a subset of the leaves (see below) and then take the subtree induced by those leaves.

That is, if we were to take the induced subtree of

^
/ \
/\ \
ab /\
c d

with the leaf set (a,d), we would get the tree

^
/ \
/ \
a \
d

with the branch lengths induced by adding branch lengths along edges that are not bifurcating. This is just like for the prepsim, but it's crucial that we "heal" the cuts along the edges, so that we don't have things like (((a)),b).

Now, how do we select the leaf set given a mass distribution? As a first go, I propose we travel from the root to the leaves, totaling up mass as we go. If the total mass once we arrive at the leaves is less than a threshold, then the leaf gets thrown out.

I hope this can unfold in several steps.

First, implement the above as `guppy trim`, which takes placerun list (placefile list or split placefile) and a `--min-path-mass` flag for the above-described cutoff. The mass will be calculated as: unitize the mass for each placerun individually and then take the overall average of those collections of masses. Seems like some code from `guppy_mft` could be factored out for this. This `--min-path-mass` flag will take a float argument whose default is 0.001 (and displayed in command line help). A note: all of this averaging may be expensive, but we don't really care about the exact attachment locations, so if there is some way of just summarizing on an edge-by-edge basis that's fine.

Please push that so that @cmccoy and @metasoarous can try it out as a preprocessing step to edge PCA etc. We will be curious to see how much a `guppy trim` step changes the shape of the PCA plots, and if it improves things on the superedge side.

Second, figure out how we can incorporate this with reference packages. The trick will be that then we will have jplace files that will not be the same tree as the reference package. My proposal is to relax this assumption, and rather allow for trees that are induced subtrees of trees in reference package. This will require a bit of work to write an appropriate validator. It seems to me that we can use the taxonomy just fine-- we will just use a subset of the species names.