Том 21, номер 3, 2014 г., Стр. 25-40
УДК 519.7
А. А. Евдокимов, С. Е. Кочемазов, И. В. Отпущенников, А. А. Семёнов
Исследование дискретно-автоматных моделей генных сетей нерегулярной структуры методами символьных вычислений
Аннотация:
Вводятся и изучаются дискретно-автоматные модели генных сетей с весовыми функциями вершин, учитывающими различные формы регуляторного взаимодействия агентов. Исследовано дискретное отображение, описывающее функционирование фрагмента генной сети бактерии E.coli. Для этого отображения с помощью SAT-подхода находятся его неподвижные точки (стационарные состояния). Также исследованы отображения, задаваемые случайными графами сети, которые генерировались в соответствии с известными моделями Гилберта – Эрдеша – Реньи и Уоттса – Строгатца. Для этих отображений найдены неподвижные точки и циклы длины 2 и 3. Настоящую работу можно рассматривать как обзор полученных нами результатов по дискретным моделям генных сетей и численным методам анализа их функционирования.
Ил. 6, табл. 2, библиогр. 27.
Ключевые слова: дискретная функция, дискретно-автоматная модель генных сетей, SAT.
Евдокимов Александр Андреевич 1
Кочемазов Степан Евгеньевич 2
Отпущенников Илья Владимирович 2
Семенов Александр Анатольевич 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
е-mail: evdok@math.nsc.ru, veinamond@gmail.com, otilya@yandex.ru, biclop.rambler@yandex.ru
Статья поступила 2 сентября 2013 г.
Литература
[1] Григоренко Е. Д., Евдокимов А. А., Лихошвай В. А., ЛобареваИ. А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестн. Томск. гос. ун-та. Прил. - 2005. - №14. - C. 206–212.
[2] Демиденко Г. В., Колчанов Н. А., Лихошвай В. А., Матушкин Ю. Г., Фадеев С. И. Математическое моделирование регуляторных контуров генных сетей // Журн. вычисл. математики и мат. физики. - 2004. - Т. 44, №12. - С. 2276–2295.
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. - 2004. - Vol. 44, N12. - P. 2166–2183.
[3] Евдокимов А. А. Дискретные модели генных сетей: анализ и сложность функционирования // Вычисл. технологии. - 2008. - Т. 13, №3. - С. 31–37.
[4] Евдокимов А. А., Кочемазов С. Е., Отпущенников И. В., Семенов А. А. Символьные алгоритмы решения булевых уравнений в применении к исследованию дискретных моделей генных сетей // Мат. XVI Междунар. конф. «Проблемы теоретической кибернетики» (Нижний Новгород, 2011 г.). - Нижний Новгород: Изд-во Нижегород. гос. ун-та, 2011. - С. 151–154.
[5] Евдокимов А. А., Кочемазов С. Е., Семенов А. А. Применение символьных вычислений к исследованию дискретных моделей некоторых классов генных сетей // Вычисл. технологии. - 2011. - Т. 16, №1. - С. 30–47.
[6] Евдокимов А. А., Лихошвай В. А., Комаров А. В. О восстановлении структуры дискретных моделей функционирования генных сетей // Вестн. Томск. гос. ун-та. Прил. - 2005. - №14. - C. 213–217.
[7] Евдокимов А. А., Пережогин А. Л. Дискретные динамические системы циркулянтного типа с линейными функциями в вершинах сети // Дискрет. анализ и исслед. операций. - 2011. - T. 18, №3. - C. 39–8.
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. - 2012. - Vol. 6, N2. - P. 160–166.
[8] Колчанов Н. А., Латыпов А. Ф., Лихошвай В. А., Матушкин Ю. Г., Никуличев Ю. В., Ратушный А. В. Задачи оптимального управления в динамике генных сетей и методы их решений // Изв. РАН.
Теория и системы управления. - 2004. - №5. - С. 36–45.
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. - 2004. - Vol. 43, N 6. - P. 862–872.
[9] Кутумова Е. О. Циклы функционирования дискретной модели регуляторного контура генной сети с пороговыми функциями // Дискрет. анализ и исслед. операций. - 2011. - T. 18, №3. - C. 65–75.
[10] Отпущенников И. В., Семенов А. А. Технология трансляции комбинаторных проблем в булевы уравнения // Прикл. дискрет. математика. - 2011. - №1. - С. 96–115.
[11] Посыпкин М. А., Заикин О. С., Беспалов Д. В., Семенов А. А. Решение задач криптоанализа поточных шифров в распределЁенных вычислительных средах // Тр. ИСА РАН. - 2009. - №46. - С. 119–137.
[12] Системная компьютерная биология. - Новосибирск: Изд-во СО РАН, 2008. - 768 c.
[13] Цейтин Г. С. О сложности вывода в исчислении высказываний // Зап. научн. семинаров ЛОМИ АН СССР. - 1968. - T. 8. - C. 234–259.
[14] Biere A., Heule V., van Maaren H., Walsh T. Handbook of satisfiability. - Amsterdam: IOS Press, 2009. - 980 p.
[15] Cook S. A. The complexity of theorem-proving procedures // 3rd Ann. ACM Symp. Theory of Computing (Shaker Heights, Ohio, USA, 1971). - New York: ACM, 1971. - P. 151–159.
[16] Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F. Critical phenomena in complex networks // Rev. Mod. Physics. - 2008. - Vol. 80. - P. 1275–1335.
[17] Dubrova E., Teslenko M. A SAT-based algorithm for finding attractors in synchronous Boolean networks // IEEE/ACM Trans. Comput. Biology Bioinform. - 2011. - Vol. 8, N5. - P. 1393–1399.
[18] Dubrova E., Teslenko M.,Martinelli A. Kauffman networks: analysis and applications // Proc. ICCAD (San Jose, USA, 2005). - Washington, DC: IEEE Comput. Soc., 2005. - P. 479–484.
[19] Erdos P., Renyi A. On random graphs // Publ. Math. - 1959. - Vol. 6. - P. 290–297.
[20] Gilbert E. N. Random graphs // Ann. Math. Stat. - 1959. - Vol. 30, N 4. - P. 1141–1144.
[21] Kauffman S. A. Metabolic stability and epigenesis in randomly constructed genetic nets // J. Theor. Biol. - 1969. - Vol. 22, N3. - P. 437–467.
[22] Mironov I., Zhang L. Applications of SAT solvers to cryptanalysis of Hash functions // Lect. Notes Comp. Sci. - 2006. - Vol. 4121. - P. 102–115.
[23] Newman M. E. J. The structure and function of complex networks // SIAM Review. - 2003. - Vol. 45, N2. - P. 167–256.
[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. - 2011. - Vol. 6873. - P. 473–483.
[25] Solomonoff R., Rapoport A. Connectivity of random nets // Bull. Math. Biophys. - 1951. - Vol. 13. - P. 440–442.
[26] Soos M., Nohl K., Castelluccia C. Extending SAT solvers to cryptographic problems // Lect. Notes Comp. Sci. - 2009. - Vol. 5584. - P. 244–257.
[27] Watts D. J., Strogatz S. H. Collective dynamics of small-world networks // Nature. - 1998. - Vol. 393. - P. 440–442.
