ITR Collaborative Research: Combinatorial Algorithms for Biological Data Clustering

人类基因组计划打开了生物数据的闸门，导致产生了大量的序列，结构，表达和相互作用数据，其速度远远超过我们目前的分析和解释能力。迫切需要新的想法和方法来大大提高生物数据分析的能力。数据聚类是挖掘大量生物数据的基础。该项目的目标是：（a）开发一个高效的通用生物数据聚类框架，该框架适用于一大类生物数据分析问题;（B）通过应用于四个具有挑战性的生物数据分析问题，证明该框架作为通用聚类工具的有效性;（c）以类似于LINPACK/LAPACK的方式，将此聚类框架作为一组库函数来实现，其他研究人员可以更有效地建立自己的聚类能力;（d）通过聚类分析提供对几个生物学问题的洞察力;及（e）培训学生/博士后如何建立生物数据分析工具，使用我们的聚类框架作为培训基地。我们的框架的基础是一个最小生成树（MST）表示的数据集及其与聚类的关系。我们的初步研究表明，（i）MST和聚类概念之间存在天然联系，这有助于将多维数据聚类问题简化为树划分问题;（ii）具有一般目标函数的聚类问题，定义在（最小生成）树，可以最优有效地求解;以及（iii）MST提供了用于解决更一般类别的聚类问题的自然框架，即，从噪声背景中提取数据簇。额外的初步研究还表明，MST具有与聚类相关的丰富特性，进一步的研究可能会导致更有效的聚类和分析生物数据的方法。我们的研究将在五个任务中组织和进行。o MSTs与集群的基本属性的调查：我们将调查MSTs和集群之间的基本关系。关于它们之间关系的新见解和发现将被用来为开发更有效的聚类方法奠定基础。o基于MST的聚类算法和统计分析方法的研究和开发：我们将研究和开发一大类基于MST的算法，用于解决几个聚类相关问题。此外，我们将研究和开发有效的统计分析工具，用于评估聚类结果的统计显著性和鲁棒性。o针对四个选定的应用问题开发改进的分析能力：我们将把我们的聚类框架应用于四个生物数据分析问题：（1）基因表达数据分析，（2）调控结合位点鉴定，（3）双杂交数据分析，及（4）系统发生树聚类分析。o将我们的基于MST的聚类框架实现为库函数：我们将实现我们的基于MST的聚类相关算法作为API（应用程序编程接口），这可以很容易地被其他研究人员在他们自己的数据分析软件中使用。此外，我们还将把我们的集群工具作为社区服务的Web服务器。o培训和教育：由于MST提供了与聚类相关的一组丰富的有吸引力的属性，我们将使用基于MST的集群框架作为培训平台，向学生/博士后如何开发生物数据分析工具。我们提出的研究和开发直接解决ITR计划的研究挑战，如下所示提供新的计算，模拟和数据分析方法和工具来模拟物理，生物，社会，行为和数学现象，并提高我们理解，建模和控制复杂系统行为的能力。

Project SummaryThe Human Genome Project has opened the flood-gate of biological data, which has resulted in the generation of enormous amount of sequence, structure, expression, and interaction data at rates that far exceed our current capability of analyzing and interpreting them. New ideas and approaches are urgently needed to establish greatly improved capabilities for biological data analysis. Data clustering is fundamental to mining a large quantity of biological data. The goals of this project are (a) to develop a highly effective and general framework for biological data clustering, which is applicable to a large class of biological data analysis problems; (b) to demonstrate the effectiveness of this framework as a general-purpose clustering tool, through application to four challenging biological data analysis problems; (c) to implement this clustering framework as a set of library functions, in a similar fashion to LINPACK/LAPACK, with which other researchers can build their own clustering capabilities more efficiently; (d) to provide insight on several biological problems through clustering analysis; and (e) to train students/postdocs how to build biological data analysis tools, using our clustering framework as a training ground. The foundation of our framework is a minimum spanning tree (MST) representation of a data set and its relationships with clustering. Our preliminary studies have revealed that (i) there is a natural connection between MSTs and the concept of clustering, which can help to reduce a multi-dimensional data clustering problem to a tree-partitioning problem; (ii) clustering problems with general objective functions, defined on (minimum spanning) trees, can be solved optimally and efficiently; and (iii) MSTs provide a natural framework for solving a more general class of clustering problems, i.e., extracting data clusters from a noisy background. Additional preliminary studies have also revealed that MSTs have such rich properties related to clustering that further investigation could lead to significantly more effective ways of clustering and analyzing biological data. Our research will be organized and carried out in five tasks.o Investigation of fundamental properties of MSTs versus clustering: We will investigate fundamental relationships between MSTs and clustering. New insights and discoveries about their relationships will be used to lay the foundation for development of more effective ways of clustering.o Investigation and development of MST-based clustering algorithms and statistical analysis methods: We will investigate and develop a large class of MST-based algorithms for several clustering related problems. In addition, we will investigate and develop effective statistical analysis tools for assessing statistical significance and robustness of clustering results.o Development of improved analysis capabilities for four selected application problems: We will apply our clustering framework to four biological data analysis problems: (1) gene expression data analysis, (2) regulatory binding site identification, (3) two-hybrid data analysis, and (4) phylogenetic tree clustering analysis.o Implementation of our MST-based clustering framework as library functions: We will implement our MST-based clustering-related algorithms as APIs (Application Programming Interface), which can be used easily by other researchers in their own data analysis software. In addition, we will implement our clustering tools as a Web server for community service.o Training and education: As MST provides such a rich set of attractive properties relevant to clustering, we will use our MST-based clustering framework as a training platform to teach students/postdocs how to develop biological data analysis tools.Our proposed study and development directly address the research challenges of the ITR program in the following areas:o providing new computational, simulation and data-analysis methods and tools to model physical, biological,social, behavioral and mathematical phenomena, ando improving our ability to understand, model and control the behavior of complex systems.