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

Cuny Hunter College, New York NY

Investigators

Abstract

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.