matsen/pplacer — Issue #235: --rep-edges for splitify subcommand
Author: matsen
Created: 2012-03-05 14:16:36+00:00
State: open
Labels: top-ish

It turns out that many edges have identical splitified columns, and this is one way of picking representatives from closely related sets.

This is a filter for after doing splitification that will only deliver a subset of the columns. In order to make this work, we need to figure out a way to adapt the splitify machinery to work with an array that only specifies results for a subset of the edges. It seems to me that adding in a map from the new array indices to the original edge numbers would work fine.

The `--rep_edges` takes a positive float argument, which I will call `max_edge_d`.

Define the distance between edges to be the Euclidean distance between their columns in the splitification matrix.

We are going to partition the edges of the tree into connected regions, such that all pairs of edges within a region have distance `max_edge_d` between them. We are then going to take the most distal representatives of these connected regions as follows.

The routine will be a depth-first recursion, that keeps an edge list `rep_edges` and an edge set `curr_edges`.

Base case at a leaf is that `rep_edges` is empty and `curr_edges` contains the pendant edge leading to that leaf.

At an internal node, say e is the edge directly above. Let the new `rep_edges` be the concatenation of the `rep_edge` list for the subtrees. Then let `possible_curr_edges` be the union of the `curr_edges` for the subtrees. Calculate the distance between each edge of that set and e. The new `curr_edges` is the set of edges that are less than `max_edge_d` away from e, and then add any edge that is greater than `max_edge_d` away from e to the `rep_edge` list. If `curr_edges` is empty, make it the single-edge set consisting of e. Recur.

@metasoarous could you please put together a little unit test jplace file for this?