[BioRuby] gsoc: SDI - unrooted trees

[Christian M Zmasek]

Hi, Sara:

Something I forgot the mention.

As you know, most phylogeny inference methods produce trees which are 
unrooted (these trees might look rooted, but for most methods the root 
is placed randomly, and thus incorrectly).

In the the context of duplication inference, a reasonable way to root a 
tree is by placing the root in such a way that the the sum of inferred 
duplications is minimized.

The brute force approach to accomplish this is by sequentially placing 
the root on each branch and then running the SDI algorithm on each 
differently rooted tree and retaining the root position which results in 
the smallest sum of duplications.

A more time efficient approach is possible by realizing that the mapping 
function only changes for a few nodes if the root is moved from one 
branch to an neighboring one.
  	
This approach is implemented in org.forester.sdi.SDIR.

Besides extending the algorithm to work on non-binary trees, this is 
another useful extension which you might think about tackling.

Christian