Department of Biomedical Engineering, Johns Hopkins University, Baltimore, MD 21218, USA.
BMC Bioinformatics. 2011 Feb 15;12 Suppl 1(Suppl 1):S44. doi: 10.1186/1471-2105-12-S1-S44.
Graphs provide a natural framework for visualizing and analyzing networks of many types, including biological networks. Network clustering is a valuable approach for summarizing the structure in large networks, for predicting unobserved interactions, and for predicting functional annotations. Many current clustering algorithms suffer from a common set of limitations: poor resolution of top-level clusters; over-splitting of bottom-level clusters; requirements to pre-define the number of clusters prior to analysis; and an inability to jointly cluster over multiple interaction types.
A new algorithm, Hierarchical Agglomerative Clustering (HAC), is developed for fast clustering of heterogeneous interaction networks. This algorithm uses maximum likelihood to drive the inference of a hierarchical stochastic block model for network structure. Bayesian model selection provides a principled method for collapsing the fine-structure within the smallest groups, and for identifying the top-level groups within a network. Model scores are additive over independent interaction types, providing a direct route for simultaneous analysis of multiple interaction types. In addition to inferring network structure, this algorithm generates link predictions that with cross-validation provide a quantitative assessment of performance for real-world examples.
When applied to genome-scale data sets representing several organisms and interaction types, HAC provides the overall best performance in link prediction when compared with other clustering methods and with model-free graph diffusion kernels. Investigation of performance on genome-scale yeast protein interactions reveals roughly 100 top-level clusters, with a long-tailed distribution of cluster sizes. These are in turn partitioned into 1000 fine-level clusters containing 5 proteins on average, again with a long-tailed size distribution. Top-level clusters correspond to broad biological processes, whereas fine-level clusters correspond to discrete complexes. Surprisingly, link prediction based on joint clustering of physical and genetic interactions performs worse than predictions based on individual data sets, suggesting a lack of synergy in current high-throughput data.
图为可视化和分析多种类型的网络提供了一个自然的框架，包括生物网络。网络聚类是一种总结大型网络结构、预测未观察到的相互作用以及预测功能注释的有价值的方法。许多当前的聚类算法都存在一些共同的局限性：高层聚类分辨率差；底层聚类过度分割；在分析之前需要预先定义聚类的数量；以及无法联合聚类多种相互作用类型。
开发了一种新的算法，层次凝聚聚类（HAC），用于快速聚类异构交互网络。该算法使用最大似然法驱动网络结构的层次随机块模型的推断。贝叶斯模型选择为在最小组内合并精细结构以及在网络内识别顶级组提供了一种原则方法。模型得分在独立的相互作用类型上是可加的，为同时分析多种相互作用类型提供了直接途径。除了推断网络结构外，该算法还生成链接预测，通过交叉验证为真实示例提供性能的定量评估。
当应用于代表几种生物体和相互作用类型的基因组规模数据集时，HAC 在链接预测方面的性能优于其他聚类方法和无模型图扩散核。对酵母蛋白质相互作用的基因组规模数据的性能进行调查表明，大约有 100 个顶级聚类，聚类大小呈长尾分布。这些聚类反过来又被分成 1000 个包含平均 5 个蛋白质的精细级聚类，其大小分布也呈长尾分布。顶级聚类对应于广泛的生物学过程，而精细级聚类对应于离散的复合物。令人惊讶的是，基于物理和遗传相互作用的联合聚类进行的链接预测比基于单个数据集的预测效果更差，这表明当前高通量数据缺乏协同作用。
