matsen/pplacer — Issue #162: more sophisticated way of doing initial ranking
Author: matsen
Created: 2011-10-16 14:38:03+00:00
State: open
Labels: top

When running pplacer with the GreenGenes tree, an important component of the time is the initial ranking (except for tree likelihood, which is currently dominated by re-calculating the categories, and is a fixed cost):

timing data:
ML calculation: 7.7365s
ranking: 175.7310s
tree likelihood: 486.3744s

This is in /home/matsengrp/working/matsen/FastTree/greengenes. It's not quite fair, because of the selection of query sequences, but we definitely should speed up the ranking component.

The current implementation just checks every insertion individually, using

List.sort
~cmp:(comparing snd |> flip)
(List.map
(fun loc ->
(loc,
Glv.bounded_logdot utilv_nsites full_query_evolv
(Glv_arr.get snodes loc) first_informative last_informative))
locs)

We would like to replace this with something smarter.

Design goals:
* make it faster in a way that doesn't sacrifice accuracy
* have as much as possible factored out into another module (?)
* have the option of easily comparing the "smart evaluation" results with the more intelligent results via a command line flag

The general idea is as follows: we will partition the node list into *chunks*. Each chunk will have one or more *representatives*. In order to do an evaluation of a given pquery, we first evaluate the bounded_logdot on each of the representatives, and thus rate the chunks. This is the "first stage".

The "second stage" is an algorithm that progresses down the list of chunks. Each chunk gets all of its snodes evaluated and sorted as in the code block above, and then we proceed down the resulting list playing baseball. If we are haven't struck out by the end of the chunk, we proceed onto the next chunk and continue. A more sophisticated algorithm might wander about the tree in an intelligent way, but I think this is fine for now.

How to partition the node list into appropriate chunks? One way would be to fix a chunking distance and recursively descend the tree, splitting subtrees into distinct chunks if they have minimal leaf-to-leaf distance between the subtrees greater than the chunking distance.