CIF: EAGER: Modeling and Querying of Probabilistic Biological Networks

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

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.