Finding biologically accurate clusterings in hierarchical tree decompositions using the variation of information

Abstract. Hierarchical clustering is a popular method for grouping to-gether similar elements based on a distance measure between them. In many cases, annotation information for some elements is known before-hand, which can aid the clustering process. We present a novel approach for decomposing a hierarchical clustering into the clusters that optimally match a set of known annotations, as measured by the variation of in-formation metric. Our approach is general and does not require the user to enter the number of clusters desired. We apply it to two biological domains: finding protein complexes within protein interaction networks and identifying species within metagenomic DNA samples. For these two applications, we test the quality of our clusters by using them to pre-dict complex and species membership, respectively. We find that our approach generally outperforms the commonly used heuristic methods