ITR Collaborative Research: Combinatorial Algorithms for Biological Data Clustering

人类基因组计划打开了生物数据的闸门，产生了大量的序列、结构、表达和相互作用数据，其速度远远超过了我们目前分析和解释这些数据的能力。迫切需要新的想法和方法来建立大大提高的生物数据分析能力。数据聚类是挖掘大量生物数据的基础。该项目的目标是(a)为生物数据聚类开发一个高效和通用的框架，该框架适用于大量的生物数据分析问题；(b)通过应用于四个具有挑战性的生物数据分析问题，证明该框架作为通用聚类工具的有效性；(c)以类似于LINPACK/LAPACK的方式，将这个聚类框架作为一组库函数来实现，其他研究人员可以利用它更有效地构建自己的聚类能力；(d)通过聚类分析提供对几个生物学问题的见解；(e)培训学生/博士后如何构建生物数据分析工具，使用我们的聚类框架作为训练场。我们框架的基础是数据集及其与聚类关系的最小生成树（MST）表示。我们的初步研究表明：(i) MSTs与聚类概念之间存在天然联系，这有助于将多维数据聚类问题简化为树分割问题；（ii）具有一般目标函数的聚类问题，定义在（最小生成）树上，可以最优有效地解决；（iii） MSTs为解决更一般的聚类问题提供了一个自然的框架，即从嘈杂的背景中提取数据簇。其他的初步研究也表明，MSTs具有丰富的聚类特性，进一步的研究可以找到更有效的聚类和分析生物数据的方法。我们的研究将分为五个任务进行组织和开展。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.