| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 25, 2016 |
| Latest Amendment Date: | May 2, 2017 |
| Award Number: | 1617678 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Mitra Basu
mbasu@nsf.gov (703)292-8649 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | August 15, 2016 |
| End Date: | July 31, 2021 (Estimated) |
| Total Intended Award Amount: | $287,993.00 |
| Total Awarded Amount to Date: | $303,993.00 |
| Funds Obligated to Date: |
FY 2017 = $16,000.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
300 TURNER ST NW BLACKSBURG VA US 24060-3359 (540)231-5281 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
VA US 24061-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01001617DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Proteins in the living cell interact with each other in complex ways. Graphs have emerged as a natural way to represent these interactions. In a conventional graph representation, a node represents a protein and an edge represents an interaction between two proteins. Although such graphs have been in widespread use for many years, they do not accurately capture important features of protein interactions, such as proteins that operate in groups called complexes, reactions involving such complexes that may have more than two reactants and products, as well as the influence of other proteins whose presence can regulate reactions. This project will develop a new representation called signaling hypergraphs that naturally describes the relationships between multiple groups of proteins as complexes, reactants, products, and regulators. Furthermore, the project will develop novel algorithms for fundamental computational challenges in the analysis of signaling hypergraphs, and apply this new representation and these algorithms to widely-used databases of cellular reactions.
The project will actively involve undergraduate students in research by recruiting them through the Virginia Tech Initiative to Maximize Student Diversity, and the Virginia Tech Undergraduate Research in Computer Science program. Students will engage in multiple semesters of research with the goal of ultimately leading their own individual projects, and obtaining co-authorship in publications. In this way the project will expose students to how computational thinking plays a major role in modern molecular biology, thereby meeting an important goal of STEM education.
This project focuses on developing algorithms for the analysis of cell signaling hypergraphs. Aim 1 focuses on methods for generating products efficiently by finding short paths through signaling hypergraphs, while accounting for feedback loops and reaction regulators. Aim 2 develops algorithms for discovering missing proteins, complexes, and reactions in a signaling pathway. Finally, Aim 3 will release open-source software implementing the algorithms for signaling hypergraphs developed in this project.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Intellectual merit. This project explored new directions in the representation and analysis of networks of interacting molecules in the cell. A common method is to represent these interactions as a graph, where each node represent a molecule and an edge connects exactly two nodes. This project dealt with such networks as well as with hypergraphs, where an edge connects more than nodes, e.g., to represent multi-way reactions.
The project made significant intellectual contributions along the following lines:
- Single-cell gene expression data measure the expression level of each gene in individual cells. Many computational techniques have been developed recently to use these data to infer gene regulatory networks, in which each edge connects a transcription factor to a gene it regulates. We developed the BEELINE framework for evaluating the accuracy of these algorithms for inferring gene regulatory networks. A surprising result was that most of these methods showed poor accuracy and oftentimes not better than that of a random predictor. The BEELINE software is available for use under an open-source licence.
- It is common to represent every node in a gene regulatory network as a Boolean variable, i.e., its state is either ON or OFF. Each node in this representation has a rule that specifies how its state is a Boolean combination of the states of the nodes it regulates. Concominant to BEELINE, we developed BoolODE, a novel method to convert a Boolean model of a gene regulatory network into a set of stochastic differential equations. BoolODE simulated these equations to generate synthetic single-cell gene expression data, which we used in BEELINE's evaluations.
- Mathematical models of biological processes can make very large number of predictions. Manually planning the experiments needed to verify these predictions is very painstaking and error-prone. We developed CrossPlan to automatically synthesize complex experimental plans based on "genetic crosses". CrossPlan creates these plans by finding short paths in an appropriately defined hypergraph. In this hypergraph, each edge represents a genetic cross experiment that takes two types of mutants as input and produces a new mutant as output.
- RegLinker is a state?of?the?art approach for reconstructing the interactions within signaling pathways. It extends an earlier method called PathLinker developed by us a few years ago.
Broader Impacts. The project supported one Ph.D. and two M.S. students. All students have graduated. The Ph.D. student received the "Ph.D. Student of the Year" award from the Department of Computer Science at Virginia Tech. The project also trained six undergraduate students (two female) in network biology.
Last Modified: 11/28/2021
Modified by: T M Murali
Please report errors in award information by writing to: awardsearch@nsf.gov.
