A novel procedure for identification of chief master regulatory genes in weighted gene regulatory networks

Articles in Press

Document Type : Original paper

Authors

1 Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran

2 Department of Biology, Azarbaijan Shahid Madani University, Tabriz, Iran

Abstract

Identifying master regulatory genes is crucial for analyzing gene regulatory networks. Various optimization-based approaches have been developed to identify potential sets of master regulatory genes. In a weighted gene regulatory network, each interaction between gene pairs is assigned a weight. In such networks, not only  direct interactions between genes significant, but indirect influences also play an important role.
 In this study, an indirect relationship between two genes is considered to exist when, in addition to a potential direct link, there is at least one additional pathway through which they influence each other. An influence value between two genes is calculated using an algorithm inspired by the K-shortest path approach. Furthermore, each gene is assigned an impact factor based on its overall influence within the weighted network. These tools allow us to introduce a new method based on a modified version of the well-known uncapacitated facility location problem. This method can identify the most significant genes among those detected by other approaches and also determine a master regulatory gene that controls a specific target gene. The proposed approach has been applied to several gene regulatory networks, and the results are reported and compared against two existing models.

Keywords

Main Subjects

References

[1] S. Bakhteh, A. Ghaffari-Hadigheh, and N. Chaparzadeh, Identification of minimum set of master regulatory genes in gene regulatory networks, IEEE/ACM Trans. Comput. Biol. Bioinform. 17 (2018), no. 3, 999–1009. https://doi.org/10.1109/TCBB.2018.2875692
[2] A.L. Barabási, N. Gulbahce, and J. Loscalzo, Network medicine: a network-based approach to human disease, Nat. Rev. Genet. 12 (2011), no. 1, 56–68.  https://doi.org/10.1038/nrg2918
[3] A. Barrat, M. Barthelemy, and A. Vespignani, The architecture of complex weighted networks: Measurements and models, Large scale structure and dynamics of complex networks: from information technology to finance and natural
science, World Scientific, 2007, pp. 67–92.
[4] J. Berclaz, F. Fleuret, E. Turetken, and P. Fua, Multiple object tracking using k-shortest paths optimization, IEEE Trans. Pattern Anal. Mach. Intell. 33 (2011), no. 9, 1806–1819.  https://doi.org/10.1109/TPAMI.2011.21
[5] K. Bernhard and J. Vygen, Combinatorial Optimization: Theory and Algorithms,  2008.
[6] Jørgen B.J. and G. Gregory, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000.
[7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, vol. 290, Citeseer, 1976.
[8] S.P. Borgatti, Centrality and AIDS, Connections 18 (1995), no. 1, 111–113.
[9] R. Cordone and G. Lulli, An integer optimization approach for reverse engineering of gene regulatory networks, Discrete Appl. Math. 161 (2013), no. 4-5,  580–592. https://doi.org/10.1016/j.dam.2012.02.010
[10] E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 269–271.
[11] H. Eiselt and V. Marianov, Foundations of Location Analysis, vol. 155, Springer science & business media, 2011.
[12] F. Emmert-Streib, M. Dehmer, and B. Haibe-Kains, Gene regulatory networks and their applications: understanding biological and medical problems in terms of networks, Front. Cell Dev. Biol. 2 (2014), Article ID: 38 https://doi.org/10.3389/fcell.2014.00038
[13] B.L. Fox, κth shortest paths and applications to the probabilistic networks, ORSA/TIMS Joint National Mtg. 23 (1975), Artice ID: B263.
[14] C. Frank and K. Römer, Distributed facility location algorithms for flexible configuration of wireless sensor networks, Distributed Computing in Sensor Systems (Berlin, Heidelberg) (J. Aspnes, C. Scheideler, A. Arora, and S. Madden, eds.),
Springer Berlin Heidelberg, 2007, pp. 124–141.
[15] S.L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res. 12 (1964), no. 3, 450–459.  https://doi.org/10.1287/opre.12.3.450
[16] M. Hamed, C. Spaniol, A. Zapp, and V. Helms, Integrative network-based approach identifies key genetic elements in breast invasive carcinoma, BMC Genomics 16 (2015), no. 5, 1–14. https://doi.org/10.1186/1471-2164-16-S5-S2
[17] B.H. Junker and F. Schreiber Falk, Analysis of Biological Networks, John wiley & sons, 2011.
[18] H. Kitano, A robustness-based approach to systems-oriented drug design, Nat. Rev. Drug Discov. 6 (2007), no. 3, 202–210. https://doi.org/10.1038/nrd2195
[19] A. Klose and A. Drexl, Facility location models for distribution system design, Eur. J. Oper. Res. 162 (2005), no. 1, 4–29.
https://doi.org/10.1016/j.ejor.2003.10.031
[20] I. A. Kovács and A. L. Barabási, Network science: Destruction perfected, Nature 524 (2015), 38–39.
[21] N. Lazic, I. Givoni, B. Frey, and P. Aarabi, Floss: Facility location for subspace segmentation, 2009 ieee 12th international conference on computer vision, IEEE, 2009, pp. 825–832.
[22] H. Li, Two-view motion segmentation from linear programming relaxation, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007, pp. 1–8.
[23] Y. Lim and H. Kim, A shortest path algorithm for real road network based on path overlap, J. East Asia Soc. Transp. Stud. 6 (2005), 1426–1438.  https://doi.org/10.11175/easts.6.1426
[24] Y.Y. Liu, J.J. Slotine, and A.L. Barabási, Controllability of complex networks, Nature 473 (2011), no. 7346, 167–173.
https://doi.org/10.1038/nature10011
[25] G. Lulli and M. Romauch, A mathematical program to refine gene regulatory networks, Discrete Appl. Math. 157 (2009), no. 10, 2469–2482. https://doi.org/10.1016/j.dam.2008.06.044
[26] K. Mehlhorn and P. Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer Science & Business Media, 2008.
[27] T. Milenković, V. Memišević, A. Bonato, and N. Pržulj, Dominating biological networks, PloS one 6 (2011), no. 8, Artice ID: e23016. https://doi.org/10.1371/journal.pone.0023016
[28] F. Morone and H.A. Makse, Influence maximization in complex networks through optimal percolation, Nature 524 (2015), no. 7563, 65–68.  https://doi.org/10.1038/nature14604
[29] J.C. Nacher and T. Akutsu, Dominating scale-free networks with variable scaling exponent: heterogeneous networks are not difficult to control, New J. Phys. 14 (2012), no. 7, Article ID: 073005. https://doi.org/10.1088/1367–2630/14/7/073005
[30] J.C. Nacher and T. Akutsu, Structural controllability of unidirectional bipartite networks, Sci. Rep. 3 (2013), no. 1, Article ID: 1647. https://doi.org/10.1038/srep01647
[31] M. Nazarieh, A. Wiese, T. Will, M. Hamed, and V. Helms, Identification of key player genes in gene regulatory networks, BMC Syst. Biol. 10 (2016), no. 1, Article ID: 88. https://doi.org/10.1186/s12918-016-0329-5
[32] S. Ohno, Major Sex-Determining Genes, Springer-Verlag, Berlin, Germany, 1979.
[33] T. Opsahl, F. Agneessens, and J. Skvoretz, Node centrality in weighted networks: Generalizing degree and shortest paths, Soc. Netw. 32 (2010), no. 3, 245–251.
[34] R.Y. Pinter, O. Rokhlenko, E. Yeger-Lotem, and M. Ziv-Ukelson, Alignment of metabolic pathways, Bioinformatics 21 (2005), no. 16, 3401–3408. https://doi.org/10.1093/bioinformatics/bti554
[35] D. Warde-Farley, S.L. Donaldson, O. Comes, K. Zuberi, R. Badrawi, P. Chao, M. Franz, C. Grouios, F. Kazi, and Christian T. Lopes, The genemania prediction server: biological network integration for gene prioritization and predicting gene
function, Nucleic Acids Res. 38 (2010), no. suppl 2, W214–W220. https://doi.org/10.1093/nar/gkq537
[36] S. Wuchty, Controllability in protein interaction networks, Proc. Natl. Acad. Sci. 111 (2014), no. 19, 7156–7160. https://doi.org/10.1073/pnas.1311231111
[37] J.Y. Yen, Finding the k shortest loopless paths in a network, Mgmt. Sci. 17 (1971), no. 11, 712–716.
[38] X.F. Zhang, L. Ou-Yang, D.Q. Dai, M.Y. Wu, Y. Zhu, and H. Yan, Comparative analysis of housekeeping and tissue-specific driver nodes in human protein interaction networks, BMC Bioinform. 17 (2016), no. 1, Article ID: 358. https://doi.org/10.1186/s12859-016-1233-0
[39] X.F. Zhang, L. Ou-Yang, Y. Zhu, M.Yu. Wu, and D.Q. Dai, Determining minimum set of driver nodes in protein-protein interaction networks, BMC Bioinform. 16 (2015), no. 1, Article ID: 146. https://doi.org/10.1186/s12859-015-0591-3
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 09 July 2025

Files

Share

How to cite

Statistics