EAGER: Cluster Detection in Graphs for Noisy, Incomplete Biological Data

基因注释和组学的整合（例如，基因组学、蛋白质组学、代谢组学）数据可以提供对噪声和不完整的生物数据的重要洞察。这样的数据通常也在一定规模上对许多传统算法提出了计算挑战。这个项目利用Foretell，一个本地搜索算法，最初创建用于加速大型约束满足问题的求解器。在这里，Foretell被用于在人类专家的指导下，检测特定于上下文的蛋白质-蛋白质相互作用（PPI）网络中基因之间的复杂关系。这是一种新颖的，潜在的变革性的方法，为基本生物过程的分子和细胞机制提供新的见解。这个灵活、创新的项目非常适合嘈杂、不完整的基因组数据。它使用经验生物学知识指导的重复局部搜索来探索人类指导下的大型加权图。它为用户提供了有意义的反馈，以重新制定他们在特定背景的PPI网络中寻找基因之间复杂关系的搜索，并设计新的权重方案来找到它们。预期的成果包括在酿酒酵母和用于检测它们的权重方案，一个更灵活的算法，检测和列表集群功能，并提供有意义的反馈给用户，和一个工具，其输出建议额外的生物实验中反复出现的集群的知识库。 这个项目在设计和执行方面都涉及生物网络的计算方法的发现和应用方面的重要问题，从这个项目中获得的知识将广泛适用，并通过出版物和网站广为传播。由此产生的知识库将支持其他研究人员？检测相互作用基因的组合并解释其结果。在推进发现和理解的同时，该项目将支持跨学科合作，广泛传播其成果，并促进学生在以女性为主的少数民族服务机构中进行研究。

The integration of gene annotations and omics (e.g., genomics, proteomics, metabolomics) data can provide important insights into noisy and incomplete biological data. Such data is often also on a scale presents computational challenges to many traditional algorithms. This project exploits Foretell, a local search algorithm originally created to accelerate solvers on large constraint satisfaction problems. Here Foretell is used to detect complex relationships among genes in context-specific protein-protein interaction (PPI) networks, with guidance from human experts. This is a novel, and potentially transformative, approach to provide new insights into the molecular and cellular mechanisms of fundamental biological processes. This flexible, innovative project is ideal for noisy, incomplete genomic data. It uses repeated local search guided by empirical biological knowledge to explore large weighted graphs under human direction. It provides users with meaningful feedback to reformulate their search for complex relationships among genes in context-specific PPI networks, and to devise new weight schemes to find them. Expected outcomes include a knowledge base of recurring clusters in Saccharomyces cerevisiae and the weight schemes used to detect them, a more flexible algorithm that detects and tabulates cluster features and provides meaningful feedback to the user, and a tool whose output suggests additional biological experiments. This project addresses, both in its design and its implementation, important questions in the discovery and application of computational approaches to biological networks.Knowledge derived from this project will be broadly applicable and well promulgated through publication and through a web site. The resultant knowledge base will support other researchers? detection of combinations of interacting genes and the interpretation of their results. While it advances discovery and understanding, this project will support interdisciplinary collaboration, disseminate its results broadly, and promote research by students in a predominantly female, minority-serving institution.