ABI Innovation: Querying Massive Dynamic Biological Network Databases

通过生物网络中的相互作用，了解不同生物实体（如基因、蛋白质和代谢物）所服务的功能一直是生物学研究的主要目标。实现这一目标的一个有希望的方法是在生物网络之间进行比较分析。近年来，人们在收集和构建生物网络方面开展了大量工作。因此，大量的网络数据已经可用。当今的生物数据库规模非常大，而且是动态的。该项目旨在开发可扩展的算法和工具，以便对非常大的动态生物网络数据库进行比较分析。更具体地说，它解决了以下问题。i)开发可扩展和准确的算法，允许快速比较成对的生物网络，同时确保结果的最优性在数学上可证明的置信范围。ii)开发有效的挖掘方法，以便在大量可选择的生物网络拓扑中找到小组有代表性的子网。iii)开发能够适应数据库变化（即插入新网络、相互作用或分子以及删除现有网络或分子）和查询网络结构的大型生物数据库集合中搜索子网络的动态索引方法。该项目将具有实践和理论两方面的影响。所开发的方法将使功能相似的不同网络的子网映射成为可能。这将提高我们对生物体如何通过相互作用运作的理解。这个项目的主要影响将是涉及生物网络的应用。它还将影响其他领域的研究，如社交网络、分布式计算和国土安全，这些领域的一系列操作通过复杂的网络相互依赖。PI将组织讲习班和研讨会，在整个研究界传播这个项目。最后，作为该项目的一部分开发的代码将作为分析和查询生物网络的优秀教育工具。

Understanding the functions served by different biological entities, such as genes, proteins and metabolites, through interactions in biological networks has been a prime goal in biological studies. One promising way to reach this goal is to perform comparative analysis among biological networks. Recently, there has been significant work in collecting and constructing biological networks. As a result, enormous amount of network data is already available. Biological databases today are very large in size and dynamic in nature. This project aims to develop scalable algorithms and tools that enable comparative analysis of very large and dynamic biological network databases. More specifically, it addresses the following problems. i) Develop scalable and accurate algorithms that allow comparing pairs of biological networks quickly while ensuring mathematically provable confidence bounds on the optimality of the results. ii) Develop efficient mining methods tailored to find small sets of representative subnetworks in massive sets of alternative biological network topologies. iii) Develop dynamic indexing methods for searching subnetworks in large collections of biological databases that can adapt to changes in the database (i.e., insertion of new networks, interactions or molecules as well as removal of existing ones) and the query network structure.This project will have both practical and theoretical impact. The developed methods will enable mapping subnetworks of different networks with similar functions. This will improve our understanding of how organisms operate through interactions. The primary impact of this project will be on applications that involve biological networks. It will also impact the studies on other fields such as social networks, distributed computing and homeland security, where a set of operations depend on each other through a complex network. The PI will organize workshops and seminars to disseminate this project throughout the research community. Finally, the code developed as a part of this project will serve as an excellent educational tool to analyze and query biological networks.