CIF: Small: Novel biologically inspired methods for analyzing multilayer networks

复杂系统通常被组织成多个相互作用的网络，其中不同的特征，如相互作用机制或外部扰动控制着每个网络的拓扑结构。民用基础设施、社交网络、生产者/消费者/零售商网络只是这些系统的几个例子。这样一个系统中的每个网络都显示了实体在一定的前提和条件下如何相互作用，而不同网络之间的相互作用显示了不同的条件如何影响整个系统。研究者称这种复杂的系统为多层网络。要理解这些系统是如何工作的，最重要的是要从整体上考虑整个网络系统，而不是独立地考虑不同层的每个网络，因为它们共同描述了底层系统的功能。该项目的主要目标是开发研究多层网络所需的基本工具，这需要创建用于基序识别和此类网络的比较分析的新颖计算技术。生物网络，如细胞网络，自然地组织成多层，其中每层描述一组分子在一组独特的限制下的相互作用拓扑结构，如外部或内部应力条件、细胞类型、发育阶段和相互作用类型。因此，使用生物系统作为网络模型提供了描述和研究复杂网络系统的机会。对组成生物网络的不同分子之间的相互作用进行计算分析是一个计算上有趣而困难的问题。通过多层网络研究这种网络的集合带来了进一步的挑战，因为(i)相互作用的拓扑结构以及分子之间的相互作用类型可能在不同的层上有所不同，（ii）多层网络的不同层上的网络可能会相互作用，因为它们可能共享一些分子，或者不同层上的分子可能相互影响。根据这些观察，PI正在处理以下两个目标，以实现主要目标。(1)识别多层网络中的构建块。(2)开发多层网络比较分析工具。经典单层网络的基序识别和比较网络分析问题已经在文献中讨论了十多年。然而，针对复杂多层系统的这些挑战的研究非常有限。本项目开发的方法结合并扩展了基本图论、计算生物学、生物信息学和机器学习的理论和算法，以实现这些目标。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Complex systems are often organized as multiple networks of interactions, where different characteristics such as interaction mechanisms or external perturbations govern the topology of each network. Civil infrastructures, social networks, producer/consumer/retailer networks are just a few examples to these systems. Each network in such a system shows how entities interact with each other under certain premises and conditions, while the interactions across different networks show how different conditions affect the entire system. The investigator calls such complex systems multilayer networks. To understand how these systems work, it is of utmost importance to consider the entire system of networks holistically, rather than each network at different layers independently as they collectively describe the functionality of the underlying system. The main objective of this project is to develop the fundamental tools needed to study multilayer networks, which requires creation of novel computational techniques for motif identification and comparative analysis of such networks. Biological networks, such as cellular networks, are naturally organized in multiple layers, where each layer describes the interaction topology among a set of molecules under a unique set of restrictions, such as external or internal stress condition, cell type, developmental stage, and interaction type. Thus, using biological systems as a network model provides opportunities to describe and study complex network systems.Computational analysis of interactions among different molecules organized as a biological network is a computationally interesting and difficult problem. Studying collections of such networks through multilayer networks introduces further challenges as (i) the interaction topologies as well as the interaction types among molecules may vary across different layers, and (ii) networks at different layers of a multilayer network may interact as they may share some molecules or the molecules at different layers may affect each other. Following from these observations, the PI is tackling the below two goals to achieve the main objective. (1) Identify building blocks in multilayer networks. (2) Develop tools for comparative analysis of multilayer networks. Both motif identification and comparative network analysis problems for classical single layer networks have been considered in the literature for over a decade. There are however very limited studies which address these challenges for complex multilayer systems. The methods developed in this project are combining and extending the theory and the algorithms for fundamental graph theory, computational biology, bioinformatics, and machine learning to achieve these objectives.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.