CIF: EAGER: Modeling and Querying of Probabilistic Biological Networks

生物体所执行的许多关键功能是由各种生物化学分子之间复杂的相互作用网络控制的。了解不同的功能是如何通过这些相互作用是至关重要的。就像生物领域的许多过程一样，相互作用是概率事件。相互作用可能会或可能不会以一定的概率发生，这取决于各种因素，如相互作用分子的大小，丰度或接近程度。相互作用的概率性质在研究生物networks.Intellectual优点：这个项目开发新的计算技术，表征和比较概率网络引入了重大的计算挑战。更具体地说，这一建议解决了以下问题。- 它将开发新的数学模型，精确有效地表征概率网络的拓扑特性。（比较分析）当至少一个生物网络是概率性的时，它将开发一个允许比较生物网络的框架。描述生物网络相互作用中的不确定性的含义是一个计算上有趣和具有挑战性的问题。主要的困难是，概率的相互作用产生指数数量的替代网络拓扑结构。该项目的核心是一种基于概率生成函数的新型数学技术。这种技术将网络结构上的一系列问题减少到多项式上的操作，从而产生非常有效的算法。该项目将使用这种技术来解决对齐概率生物网络的问题。更广泛的影响：许多应用程序遵循类似于生物网络的交互模式。无线网络、传感器网络、社交网络和国土安全只是几个例子。这些应用程序的一个关键共同属性是定义它们的交互是概率事件。该项目将使研究这样的网络，从而将有助于回答基本的问题，如：什么是两个社交网络之间的相似模式？病毒通过给定的无线网络传播的速度有多快？即使在互动是概率性的情况下，也能准确有效地进行。该项目也将产生教育影响。作为该项目的一部分，PI将招募和培训一名研究生。最后，在这个项目中开发的代码将作为一个优秀的教育工具，分析和查询数据的广泛的应用程序，其中数据库由一组相互作用的实体。

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.