Solving the influence maximization problem reveals regulatory organization of the yeast cell cycle

The Influence Maximization Problem (IMP) aims to discover the set of nodes with the greatest influence on network dynamics. The problem has previously been applied in epidemiology and social network analysis. Here, we demonstrate the application to cell cycle regulatory network analysis for Saccharomyces cerevisiae. Fundamentally, gene regulation is linked to the flow of information. Therefore, our implementation of the IMP was framed as an information theoretic problem using network diffusion. Utilizing more than 26,000 regulatory edges from YeastMine, gene expression dynamics were encoded as edge weights using time lagged transfer entropy, a method for quantifying information transfer between variables. By picking a set of source nodes, a diffusion process covers a portion of the network. The size of the network cover relates to the influence of the source nodes. The set of nodes that maximizes influence is the solution to the IMP. By solving the IMP over different numbers of source nodes, an influence ranking on genes was produced. The influence ranking was compared to other metrics of network centrality. Although the top genes from each centrality ranking contained well-known cell cycle regulators, there was little agreement and no clear winner. However, it was found that influential genes tend to directly regulate or sit upstream of genes ranked by other centrality measures. The influential nodes act as critical sources of information flow, potentially having a large impact on the state of the network. Biological events that affect influential nodes and thereby affect information flow could have a strong effect on network dynamics, potentially leading to disease. Code and data can be found at: https://github.com/gibbsdavidl/miergolf.

影响力最大化问题（Influence Maximization Problem，IMP）旨在找出对网络动态影响最大的节点集合。该问题此前已被应用于流行病学与社会网络分析领域。本研究将其应用于酿酒酵母（Saccharomyces cerevisiae）的细胞周期调控网络分析。从本质而言，基因调控与信息流动紧密关联，因此我们将IMP的实现框架设定为基于网络扩散的信息论问题。我们利用YeastMine中的26000余条调控边，采用时滞传递熵——一种量化变量间信息传递的方法——将基因表达动态编码为边权重。通过选取一组源节点，扩散过程可覆盖网络的部分区域，而网络覆盖范围的大小与源节点的影响力直接相关，能够最大化影响力的节点集合即为IMP的解。通过针对不同数量的源节点求解IMP，我们得到了基因的影响力排序，并将该排序与其他网络中心性指标进行了对比。尽管各中心性排序的顶级基因均包含已知的细胞周期调控因子，但各排序间一致性极低，未出现明确的最优指标。不过研究发现，高影响力基因往往直接调控其他中心性指标排序靠前的基因，或位于其上游调控位置。高影响力节点作为信息流的关键源头，可对网络状态产生显著影响，若生物事件影响了这些高影响力节点并进而改变信息流，则可能对网络动态产生强烈作用，甚至引发疾病。相关代码与数据集可通过以下链接获取：https://github.com/gibbsdavidl/miergolf。