Алгоритмы восстановления дискретных динамических систем с пороговыми функциями
Ключевые слова:
дискретная динамическая система, генная сеть, пороговая функция, тестирование, задача восстановленияАннотация
Задача восстановления динамической системы по ее функционированию является актуальной в теории управляющих систем. Ранее были получены псевдополиномиальные алгоритмы восстановления дискретных динамических систем с аддитивными и мультипликативными функциями. Такие системы моделируют поведение регуляторного контура генной сети, а соответствующие функции отвечают за увеличение или уменьшения концентрации веществ. В настоящей статье рассматривается обобщение на случай произвольных пороговых функций. Приведены алгоритмы восстановления существенных переменных и алгоритм упорядочивания весов пороговых функций, имеющие псевдополиномиальную сложность тестирования. Эти алгоритмы позволяют либо полностью восстановить систему, либо уменьшить размерность пороговых функций.Литература
1. Wang R.-S., Saadatpour A., Albert R. Boolean modeling in systems biology: an overview of methodology and applications // Physical Biology. 2012. vol. 9. no. 5.
2. Евдокимов А.А., Комаров А.В. О восстановлении структуры дискретных моделей функционирования генных сетей. // Вестник ТГУ. 2005. № 14. С. 213–217.
3. Евдокимов А.А., Комаров А.В. О восстановимости дискретных моделей генных сетей // Вестник ТГУ. 2006. № 3. С. 437–467.
4. Akutsu T., Kuhara S., Maruyama O., Miyano S. Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model // Theoretical Computer Science. 2003. vol. 298. pp. 235–251.
5. Евдокимов А.А., Пережогин А.Л. Дискретные динамические системы циркулянтного типа с линейными функциями в вершинах сети // Дискретн. анализ и исслед. опер. 2011. № 18(3). С. 39–48.
6. Корниенко А.С. Структура функциональных графов для циркулянтов с линейными булевыми функциями в вершинах // Прикладная дискретная ма-тематика. 2014. №1. С. 84–95.
7. Демиденко Г.В. и др. Математическое моделирование регулярных контуров генных сетей // Журн. вычисл. математики и мат. физики. 2004. Т. 44. № 12. C. 2276–2295.
8. Григоренко Е.Д., Евдокимов А.А., Лихошвай В.А., Лобарева И.А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестник ТГУ. Приложение. 2005. № 14. С. 206–212.
9. Kutumova E.O., Evdokimov A.A. Reversible states of functioning the regulatory circuits discrete models the gene nets // Вестник ТГУ. Управление, вычислительная техника и информатика. 2011. № 14(1). С. 85–94.
10. Нажмиденова А.М., Пережогин А.Л. Дискретная динамическая система на двойном циркулянте // Дискретн. анализ и исслед. опер. 2014. № 21(4). С. 80–88.
11. Евдокимов А.А., Кочемазов С.Е. Отпущенников И.В., Семенов А.А. Исследование динамических свойств некоторых дискретно-автоматных отображений, заданных случайными графами // Прикладная дискретная математика. Приложение. 2013. № 6. С. 75–76.
12. Евдокимов А.А., Кочемазов С.Е. Отпущенников И.В., Семенов А.А. Исследование дискретно-автоматных моделей генных сетей нерегулярой структуры методами символьных вычислений // Дискретн. анализ и исслед. опер. 2014. № 21(3). С. 25–40.
13. Батуева Ц.Ч.-Д. Свойства генных сетей циркулянтного типа с пороговыми функциями // Прикладная дискретная математика. Приложение. 2013. № 6. С. 72–73.
14. Батуева Ц.Ч.-Д. Дискретные динамические системы циркулянтного типа с пороговыми функциями в вершинах // Дискретн. анализ и исслед. опер. 2014. № 21(4). С. 25–32.
15. Быков И.С. Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах // Прикладная дискретная математика. 2014. №4. С. 84–95.
16. Золотых Н.Ю., Шевченко В.Н. Расшифровка пороговых функций k-значной логики // Дискретн.анализ и исслед. опер. 1995. Т. 2. № 3. С. 18–23.
2. Евдокимов А.А., Комаров А.В. О восстановлении структуры дискретных моделей функционирования генных сетей. // Вестник ТГУ. 2005. № 14. С. 213–217.
3. Евдокимов А.А., Комаров А.В. О восстановимости дискретных моделей генных сетей // Вестник ТГУ. 2006. № 3. С. 437–467.
4. Akutsu T., Kuhara S., Maruyama O., Miyano S. Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model // Theoretical Computer Science. 2003. vol. 298. pp. 235–251.
5. Евдокимов А.А., Пережогин А.Л. Дискретные динамические системы циркулянтного типа с линейными функциями в вершинах сети // Дискретн. анализ и исслед. опер. 2011. № 18(3). С. 39–48.
6. Корниенко А.С. Структура функциональных графов для циркулянтов с линейными булевыми функциями в вершинах // Прикладная дискретная ма-тематика. 2014. №1. С. 84–95.
7. Демиденко Г.В. и др. Математическое моделирование регулярных контуров генных сетей // Журн. вычисл. математики и мат. физики. 2004. Т. 44. № 12. C. 2276–2295.
8. Григоренко Е.Д., Евдокимов А.А., Лихошвай В.А., Лобарева И.А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестник ТГУ. Приложение. 2005. № 14. С. 206–212.
9. Kutumova E.O., Evdokimov A.A. Reversible states of functioning the regulatory circuits discrete models the gene nets // Вестник ТГУ. Управление, вычислительная техника и информатика. 2011. № 14(1). С. 85–94.
10. Нажмиденова А.М., Пережогин А.Л. Дискретная динамическая система на двойном циркулянте // Дискретн. анализ и исслед. опер. 2014. № 21(4). С. 80–88.
11. Евдокимов А.А., Кочемазов С.Е. Отпущенников И.В., Семенов А.А. Исследование динамических свойств некоторых дискретно-автоматных отображений, заданных случайными графами // Прикладная дискретная математика. Приложение. 2013. № 6. С. 75–76.
12. Евдокимов А.А., Кочемазов С.Е. Отпущенников И.В., Семенов А.А. Исследование дискретно-автоматных моделей генных сетей нерегулярой структуры методами символьных вычислений // Дискретн. анализ и исслед. опер. 2014. № 21(3). С. 25–40.
13. Батуева Ц.Ч.-Д. Свойства генных сетей циркулянтного типа с пороговыми функциями // Прикладная дискретная математика. Приложение. 2013. № 6. С. 72–73.
14. Батуева Ц.Ч.-Д. Дискретные динамические системы циркулянтного типа с пороговыми функциями в вершинах // Дискретн. анализ и исслед. опер. 2014. № 21(4). С. 25–32.
15. Быков И.С. Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах // Прикладная дискретная математика. 2014. №4. С. 84–95.
16. Золотых Н.Ю., Шевченко В.Н. Расшифровка пороговых функций k-значной логики // Дискретн.анализ и исслед. опер. 1995. Т. 2. № 3. С. 18–23.
Recovery Algorithms for Discrete Dynamic System with Threshold Functions
Abstract
Recovery of a dynamic system from its functioning is a problem of current interest in the theory of control systems. As a behavior model of gene network regulatory circuit, a discrete dynamic system has been proposed, where coordinates correspond to the concentration of substances, while special functions, which depend on the system value in the previous moment, account for their increase or decrease. Pseudo-polynomial discrete dynamic system recovery algorithms with additive and multiplicative functions have been obtained earlier. The generalized case of arbitrary threshold functions is considered in this article. Algorithms for significant variables recovery and threshold functions weight regulation, having pseudo-polynomial testing complexity, are given. These algorithms allow one either to recover the system completely, or to lower the threshold function dimension.
Опубликован
2016-12-15
Как цитировать
Прытков, Н. В., & Пережогин, А. Л. (2016). Алгоритмы восстановления дискретных динамических систем с пороговыми функциями. Труды СПИИРАН, 6(49), 66-79. https://doi.org/10.15622/sp.49.4
Раздел
Теоретическая и прикладная математика
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
