CLUSTERING BIOLOGICAL DATA USING MESSAGE PASSING

这个子项目是许多研究子项目中利用 资源由NIH/NCRR资助的中心拨款提供。子项目和 调查员(PI)可能从NIH的另一个来源获得了主要资金， 并因此可以在其他清晰的条目中表示。列出的机构是 该中心不一定是调查人员的机构。 聚类算法在生物信息学中被广泛用于数据分类，如在基因表达分析和系统发育树的构建中。生物数据常常描述平行的和自发的过程。为了捕捉这些特征，我们提出了一种新的利用消息传递概念的聚类算法。消息传递集群(MPC)允许数据对象相互通信并并行生成集群，从而使集群过程成为内在的。我们已经证明，MPC与层次聚类(HC)有相似之处，但由于它同时考虑了局部和全局结构，因此性能显著提高。我们已经分析了35组模拟的动态基因表达数据，获得了95%的命中率，在总共674个基因中有639个基因被正确聚类。我们还将MPC应用于一个真实的数据集，以从已比对的分枝杆菌序列中构建系统发育树。结果表明，与HC等传统的聚类方法相比，该方法具有更高的分类精度。

This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. Clustering algorithms are widely used in bioinformatics to classify data, as in the analysis of gene expression and in the building of phylogenetic trees. Biological data often describe parallel and spontaneous processes. To capture these features, we propose a new clustering algorithm that employs the concept of message passing. Message Passing Clustering (MPC) allows data objects to communicate with each other and produces clusters in parallel, thereby making the clustering process intrinsic. We have proved that MPC shares similarity with Hierarchical Clustering (HC) but offers significantly improved performance because it takes into account both local and global structure. We have analyzed 35 sets of simulated dynamic gene expression data, achieving a 95% hit rate in which 639 genes out of a total 674 genes were correctly clustered. We have also applied MPC to a real data set to build a phylogenic tree from aligned mycobacterium sequences. The results show higher classification accuracies as compared to traditional clustering methods such as HC.