Many critical functions performed by organisms are governed by a complex network of interactions among various biochemical molecules. Understanding how different functions are served through these interactions is of utmost importance. Like many processes in the biological realm, interactions are probabilistic events. An interaction may or may not happen with some probability, depending on a variety of factors such as the size, abundance or proximity of the interacting molecules. The probabilistic nature of the interactions introduces significant computational challenges in studying biological networks.
Intellectual Merit: This project develops novel computational techniques that characterize and compare probabilistic networks. More specifically, this proposal addresses the following problems. - (Modeling) It will develop novel mathematical models that characterize topological properties of probabilistic networks precisely and efficiently. - (Comparative analysis) It will develop a framework that allows comparing biological networks when at least one of them is probabilistic.
Characterizing the implications of uncertainties in interactions of biological networks is a computationally interesting and challenging problem. The main difficulty is that probabilistic interactions yield an exponential number of alternative network topologies. At the heart of this project lies a novel mathematical technique based on probability generating functions. This technique reduces a broad set of questions on the network structure to operations on polynomials resulting in very efficient algorithms. This project will use this technique to address the problem of aligning probabilistic biological networks.
Broader Impact: Numerous applications follow an interaction pattern that resembles biological networks. Wireless networks, sensor networks, social networks and homeland security are just a few examples. A critical common property of these applications is that the interactions that define them are probabilistic events. This project will enable studying such networks and thus will help answering fundamental queries such as: What are the similar patterns between two social networks?, How fast do we expect a virus spread through a given wireless network? precisely and efficiently even when interactions are probabilistic.
This project will also have educational impact. The PIs will recruit and train a graduate student as a part of this project. Finally, the code developed in this project will serve as an excellent educational tool to analyze and query data for a broad spectrum of applications, where the database consists of a set of interacting entities.
