[BioRuby] gsoc: SDI - unrooted trees
Christian M Zmasek
czmasek at burnham.org
Fri Jun 25 02:18:41 UTC 2010
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
More information about the BioRuby
mailing list