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.
