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.
