In a broad range of organisms, Piwi-interacting RNAs (piRNAs) have emerged as core components of a surveillance system that protects the genome by silencing transposable and repetitive elements. A vast proportion of piRNAs is produced from discrete genomic loci, termed piRNA clusters, which are generally embedded in heterochromatic regions. The molecular mechanisms and the factors that govern their expression are largely unknown. Here, we show that Cutoff (Cuff), a Drosophila protein related to the yeast transcription termination factor Rai1, is essential for piRNA production in germline tissues. Cuff accumulates at centromeric/pericentromeric positions in germ-cell nuclei and strongly colocalizes with the major heterochromatic domains. Remarkably, we show that Cuff is enriched at the dual-strand piRNA cluster 1/42AB and is likely to be involved in regulation of transcript levels of similar loci dispersed in the genome. Consistent with this observation, Cuff physically interacts with the Heterochromatin Protein 1 (HP1) variant Rhino (Rhi). Our results unveil a link between Cuff activity, heterochromatin assembly and piRNA cluster expression, which is critical for stem-cell and germ-cell development in Drosophila.

MOTIVATION: Clustering algorithms play an important role in the analysis of biological networks, and can be used to uncover functional modules and obtain hints about cellular organization. While most available clustering algorithms work well on biological networks of moderate size, such as the yeast protein physical interaction network, they either fail or are too slow in practice for larger networks, such as functional networks for higher eukaryotes. Since an increasing number of larger biological networks are being determined, the limitations of current clustering approaches curtail the types of biological network analyses that can be performed. RESULTS: We present a fast local network clustering algorithm SPICi. SPICi runs in time O(V log V+E) and space O(E), where V and E are the number of vertices and edges in the network, respectively. We evaluate SPICi's performance on several existing protein interaction networks of varying size, and compare SPICi to nine previous approaches for clustering biological networks. We show that SPICi is typically several orders of magnitude faster than previous approaches and is the only one that can successfully cluster all test networks within very short time. We demonstrate that SPICi has state-of-the-art performance with respect to the quality of the clusters it uncovers, as judged by its ability to recapitulate protein complexes and functional modules. Finally, we demonstrate the power of our fast network clustering algorithm by applying SPICi across hundreds of large context-specific human networks, and identifying modules specific for single conditions. AVAILABILITY: Source code is available under the GNU Public License at http://compbio.cs.princeton.edu/spici.