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

David L Gibbs and Ilya Shmulevich

PLOS Computational Biology, 2017, vol. 13, issue 6, 1-19

Abstract: 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.Author summary: The Influence Maximization Problem (IMP) has been applied in fields such as epidemiology and social network analysis. Here, we apply the method to biological networks, aiming to discover the set of regulatory genes with the greatest influence on network dynamics. Fundamentally, since gene regulation is linked to the flow of information, we framed the IMP as an information theoretic problem. Dynamics were encoded as edge weights using time lagged transfer entropy, a quantity that attempts to quantify information transfer across variables. The influential nodes act as critical sources of information flow, potentially affecting the global network state. Biological events that impact the influential nodes and thereby affecting normal information flow could have a strong effect on the network, potentially leading to disease.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1005591 (text/html)
https://journals.plos.org/ploscompbiol/article/fil ... 05591&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pcbi00:1005591

DOI: 10.1371/journal.pcbi.1005591

Access Statistics for this article

More articles in PLOS Computational Biology from Public Library of Science
Bibliographic data for series maintained by ploscompbiol ().