Analysis of discrete automaton models of gene networks with irregular structure using symbolic algorithms

A. A. Evdokimov ; S. E. Kochemazov ; I. V. Otpushennikov ; A. A. Semenov

Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 25-40.

Résumé

We introduce and analyze discrete-automaton models of gene networks where weight functions of vertices take into account various forms of regulatory activity of agents. Within the model, we analyze a discrete mapping specified by a fragment of the gene network of E.coli. For this mapping, we found a number of fixed points using SAT-approach. Also we analyze mappings specified by random graphs generated according to Gilbert–Erdos–Renyi and Watts–Strogatz models. For these mappings, it was possible to find fixed points and cycles of length 2 and 3. This work can be considered as a review of our recent results regarding discrete models of gene networks and symbolic methods of analysis of their functioning. Ill. 6, tab. 2, bibliogr. 27.

Détail

Keywords: discrete function, discrete automaton model of gene networks, SAT.

Bibliographie

[1] Grigorenko E. D., Evdokimov A. A., Likhoshvai V. A., Lobareva I. A., “Nepodvizhnye tochki i tsikly avtomatnykh otobrazhenii, modeliruyuschikh funktsionirovanie gennykh setei”, Vestn. Tomsk. gos. un-ta. Pril., 2005, no. 14, 206–212

[2] Demidenko G. V., Fadeev S. I., Likhoshvai V. A., Matushkin Yu. G., Kolchanov N. A., “Mathematical simulation of regulatory circuits of gene networks”, Comput. Math. Math. Phys., 44:12 (2004), 2166–2183 | MR | Zbl

[3] Evdokimov A. A., “Diskretnye modeli gennykh setei: analiz i slozhnost funktsionirovaniya”, Vychisl. tekhnologii, 13:3 (2008), 31–37

[4] Evdokimov A. A., Kochemazov S. E., Otpuschennikov I. V., Semenov A. A., “Simvolnye algoritmy resheniya bulevykh uravnenii v primenenii k issledovaniyu diskretnykh modelei gennykh setei”, Mat. XVI Mezhdunar. konf. “Problemy teoreticheskoi kibernetiki” (Nizhnii Novgorod, 2011 g.), Izd-vo Nizhegorod. gos. un-ta, Nizhnii Novgorod, 2011, 151–154

[5] Evdokimov A. A., Kochemazov S. E., Semenov A. A., “Primenenie simvolnykh vychislenii k issledovaniyu diskretnykh modelei nekotorykh klassov gennykh setei”, Vychisl. tekhnologii, 16:1 (2011), 30–47 | Zbl

[6] Evdokimov A. A., Likhoshvai V. A., Komarov A. V., “O vosstanovlenii struktury diskretnykh modelei funktsionirovaniya gennykh setei”, Vestn. Tomsk. gos. un-ta. Pril., 2005, no. 14, 213–217

[7] Evdokimov A. A., Perezhogin A. L., “Discrete dynamical systems of a circulant type with linear functions at the vertices of a network”, J. Appl. Industr. Math., 6:2 (2012), 160–166 | MR | Zbl

[8] Kolchanov N. A., Latypov A. F., Likhoshvai V. A., Matushkin Yu. G., Nikulichev Yu. V., Ratushnyi A. V., “Optimal control problems in gene network dynamics and the methods for solving them”, J. Comput. Syst. Sci. Int., 43:6 (2004), 862–872 | MR | Zbl

[9] Kutumova E. O., “Tsikly funktsionirovaniya diskretnoi modeli regulyatornogo kontura gennoi seti s porogovymi funktsiyami”, Diskret. analiz i issled. operatsii, 18:3 (2011), 65–75 | MR | Zbl

[10] Otpuschennikov I. V., Semenov A. A., “Tekhnologiya translyatsii kombinatornykh problem v bulevy uravneniya”, Prikl. diskret. matematika, 2011, no. 1, 96–115

[11] Posypkin M. A., Zaikin O. S., Bespalov D. V., Semenov A. A., “Reshenie zadach kriptoanaliza potochnykh shifrov v raspredelënnykh vychislitelnykh sredakh”, Tr. ISA RAN, 46, 2009, 119–137

[12] Sistemnaya kompyuternaya biologiya, Izd-vo SO RAN, Novosibirsk, 2008, 768 pp.

[13] Tseitin G. S., “O slozhnosti vyvoda v ischislenii vyskazyvanii”, Zap. nauchn. seminarov LOMI AN SSSR, 8, 1968, 234–259 | MR | Zbl

[14] Biere A., Heule V., van Maaren H., Walsh T., Handbook of satisfiability, IOS Press, Amsterdam, 2009, 980 pp. | Zbl

[15] Cook S. A., “The complexity of theorem-proving procedures”, 3rd Ann. ACM Symp. Theory of Computing (Shaker Heights, Ohio, USA, 1971), ACM, New York, 1971, 151–159 | DOI

[16] Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F., “Critical phenomena in complex networks”, Rev. Mod. Physics, 80 (2008), 1275–1335 | DOI

[17] Dubrova E., Teslenko M., “A SAT-based algorithm for finding attractors in synchronous Boolean networks”, IEEE/ACM Trans. Comput. Biology Bioinform., 8:5 (2011), 1393–1399 | DOI

[18] Dubrova E., Teslenko M., Martinelli A., “Kauffman networks: analysis and applications”, Proc. ICCAD (San Jose, USA, 2005), IEEE Comput. Soc., Washington, DC, 2005, 479–484

[19] Erdos P., Renyi A., “On random graphs”, Publ. Math., 6 (1959), 290–297 | MR | Zbl

[20] Gilbert E. N., “Random graphs”, Ann. Math. Stat., 30:4 (1959), 1141–1144 | DOI | MR | Zbl

[21] Kauffman S. A., “Metabolic stability and epigenesis in randomly constructed genetic nets”, J. Theor. Biol., 22:3 (1969), 437–467 | DOI

[22] Mironov I., Zhang L., “Applications of SAT solvers to cryptanalysis of Hash functions”, Lect. Notes Comp. Sci., 4121, 2006, 102–115 | DOI | MR | Zbl

[23] Newman M. E. J., “The structure and function of complex networks”, SIAM Review, 45:2 (2003), 167–256 | DOI | MR | Zbl

[24] Semenov A., Zaikin O., Bespalov D., Posypkin M., “Parallel logical cryptanalysis of the generator A5/1 in BNB-grid system”, Lect. Notes Comp. Sci., 6873, 2011, 473–483 | DOI

[25] Solomonoff R., Rapoport A., “Connectivity of random nets”, Bull. Math. Biophys., 13 (1951), 440–442 | MR

[26] Soos M., Nohl K., Castelluccia C., “Extending SAT solvers to cryptographic problems”, Lect. Notes Comp. Sci., 5584, 2009, 244–257 | DOI

[27] Watts D. J., Strogatz S. H., “Collective dynamics of small-world networks”, Nature, 393 (1998), 440–442 | DOI