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

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

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.