CLUSTERING BIOLOGICAL DATA USING MESSAGE PASSING

该子项目是利用NIH/NCRR资助的中心赠款提供的资源的许多研究子项目之一。子项目和研究者（PI）可能从另一个NIH来源获得主要资金，因此可以在其他CRISP条目中表示。所列机构为中心，不一定是研究者所在机构。聚类算法在生物信息学中被广泛用于对数据进行分类，如在基因表达的分析和系统发育树的构建中。生物学数据通常描述平行和自发的过程。为了捕捉这些功能，我们提出了一个新的聚类算法，采用消息传递的概念。消息传递聚类（MPC）允许数据对象相互通信并并行产生聚类，从而使聚类过程成为内在的。我们已经证明，MPC股相似的层次聚类（HC），但提供了显着改善的性能，因为它考虑到本地和全球的结构。我们已经分析了35组模拟的动态基因表达数据，达到了95%的命中率，其中639个基因，共674个基因被正确聚类。我们还将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.