Дискретная модель генной сети циркулянтного типа с пороговыми функциями

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2008 Управление, вычислительная техника и информатика № 2(3)
УДК 618. 5:519. 68
А. А. Евдокимов, Е.О. Лиховидова
ДИСКРЕТНАЯ МОДЕЛЬ ГЕННОЙ СЕТИ ЦИРКУЛЯНТНОГО ТИПА С ПОРОГОВЫМИ ФУНКЦИЯМИ
Рассматривается дискретная модель генных сетей, функционирование которых определяется заданием аддитивного автоматного отображения. Получено описание нового класса циклов и рабочих наборов моделей циклического типа, структура которых является циркулянтным ориентированным графом.
Ключевые слова: генные сети, ориентированный граф, аддитивный автомат, граф состояний отображения, циклы графа состояний, рабочие наборы графа состояний.
1. Введение, основные определения
Генные сети служат основой для моделирования процессов, протекающих в клетке: поддерживают в организме устойчивые состояния, характеризующиеся постоянством концентрации веществ (стационарные состояния) — обеспечивают периодические незатухающие колебания концентраций определенных групп веществ (циклы) — контролируют необратимые процессы развития и роста [1].
Контуры с положительными и отрицательными обратными связями обеспечивают управление генной сетью. Некоторые структурные особенности строения регуляторных контуров естественно формулируются в терминах ориентированных графов и дискретных моделей функционирования регуляторных контуров.
Ниже рассматривается одна из таких моделей. Регуляторный контур генной сети представляется в виде связного ориентированного графа G (V, D), где V е 1, п -множество вершин, отождествляемое с продуктами генетических элементов (РНК, белки), а Б — множество дуг, имеющих смысл регуляторных связей. В качестве графов мы рассматриваем ориентированные циркулянт-ные графы Оп, к, где (к — 1) — число входящих (и выходящих) дуг, к & lt- п [2]. На рис. 1 изображен граф 06,3.
В вершинах графа в каждый момент времени подсчитываются значения некоторых функций /(& gt-->-х1к) (возможно, одной функции), сопоставленных вершинам, а переменные х-,, у е 1, к, приписаны дугам, входящим в вершину V и
к = а+ (V). Значения функции /: Nк ^ N, где N е 1, р -1, содержательно соответствуют уровню концентрации, далее называемому весом вершины, конечного продукта, синтезируемого с генетического элемента, соответствующего заданной вершине.
Функционирование генной сети характеризуется изменением концентрации ее веществ, т. е. сменой п-наборов из Nк, соответствующих значениям функций /у в п вершинах сети в каждый момент времени. Таким образом, для каждого началь-
ного состояния (и-набора) динамика изменения состояний определяется отображением А: Ор ^ Ор, где Ор — множество наборов весов вершин графа 0″, к. Будем считать, что все функции /г в вершинах из V равны и определяются следующим образом. Для любой вершины V /(хі,…, хі+к) = х/, где
хі +1, если ^ х] = 0 и хі & lt- р -1- хі -1, если ^ х .• & gt- 0 и хі & gt- 0-
]
хі, иначе,
Ц- = {(г — у)(шоё п)|/ е 1, к -1} - номера вершин, дуги из которых ведут в вершину V. (По условию цикличности полагаем х0 = хп.) Отображение А: Ор ^ Ор,
определяемое таким образом, назовем действием аддитивного (автономного) автомата А (/, р) на множестве Ор. Здесь и далее действие автомата А (/, р) задается
на графе Оп, к.
Последовательность наборов X1,…, Хг € 0. р называется циклом длины г аддитивного автомата А (/, р), если
ГА (х1) = X1+, I елГг-
[ хг+1 = х[.
При г = 1 имеем А (X1) = X1 и X1 называется неподвижной точкой отображения А: О р ^ О р.
Графом состояний отображения А: Ор ^ Ор называется ориентированный граф, вершинами которого являются элементы X & amp- Ор, причем дуга из вершины X идет в вершину У е Ор тогда и только тогда, когда А (Х) = 7.
Набор У е Ор называется рабочим для отображения А: Ор ^ Ор, если существует X & amp- О, для которого А (Х) = 7. В графе состояний это соответствует дуге {У, X).
Анализ поведения генной сети включает исследование динамики изменения ее состояний, которая полностью характеризуется видом графа состояний и включает исследование циклов, оценку числа рабочих наборов в зависимости от значений параметров п, к ир и т. д.
2. Циклы отображения графа состояний
В [2] было описано действие аддитивного автомата на наборы Xг = (О^О, р — 1,0и0), г е 1,1,
I-1 П-
где d = нод (п, к), в зависимости от значения к, а также циклы, возникающие в результате этого действия в случае d & lt- к. При d = к для всех г е 1,1 появляются
20
А. А. Евдокимов, Е.О. Лиховидова
неподвижные точки
(0UO, р — louo, р -1,о^. 1о,…, о,. -_1о, р -1Д. -1о).
i-1 k-1 k-1 k-1 k-i
Было отмечено, что цикл (0,…, 0) О длины 2 является циклом адди-
тивного автомата для любых k е 2, n и p & gt- 2.
В настоящей работе нами получено описание нового класса циклов для случая n = 2k. Пусть r & gt- 1.
Цикл Xх,…, Xr автомата Af, p) называется p-собственным, если для всех р1 & lt- p определяющая его последовательность Xх,…, Xr не является циклом автомата Af, р1). В противном случае будем называть его несобственным для p.
P-собственный цикл Xх,…, Xr автомата Af, p) называется наследственным, если для любого p2 & gt- p определяющая его последовательность Xх,…, Xr является циклом автомата Af p2).
Набор (x1,…, xn) назовем & lt-^,/>--набором, если он содержит поднабор 0k-1 d ,
вхождение которого начинается с /-й координаты, где l е 1, n.
Лемма 1. (Критерий ^-собственности.) Цикл являлся-собственным тогда и только тогда, когда существует l е 1, n, что цикл содержит & lt-p — 2, / & gt--набор.
Следующая теорема сводит описание циклов для произвольного p & gt- 4 к описанию 4-собственных циклов и наследственных циклов для p = 3.
Теорема 1 (о сводимости). При p & gt- 4 все циклы являются несобственными для p. Для p = 4 все собственные циклы являются наследственными.
Следующая теорема дает описание 4-собственных циклов для случая n=2k.
Теорема 2. Цикл является 4-собственным тогда и только тогда, когда он содержит набор, только две координаты которого равны 2, а все остальные — нулевые.
Наследственные циклы для случая p = 3 описываются как циклы, содержащие наборы вида (0,., 0, 2,0,., 0,1), где на параметры m и r накладывается ус-
k+m-r+1 k-m-2 r-1
ловие: r + m & lt- k — 2, где r el, k — 2, m e 0, k — 3.
3. Рабочие наборы графа состояний
Пусть в начале p = 2.
Заметим, что если k = 2, то все n-наборы являются рабочими для нашего отображения A: Q2 ^2.
Теорема 3. Если k & gt- 3, то набор X = (ххxn) является рабочим для отображения A: Q2 ^ Q2 тогда и только тогда, когда этот набор не содержит вхождений поднаборов 1,0,…, 0,1 для любого r el, k-2.
r
Лемма 2. Число H (n, k, 2) рабочих n-наборов отображения A: Q2 ^ Q2 равно H (n, k, 2) = k ¦ G (n +1) — (k — 2) • G (n),
где G (n) удовлетворяет следующему рекуррентному соотношению:
G (n) = 2 G (n -1) — G (n — 2) + G (n — k). (1)
Теорема 4. При фиксированном k & gt- 3 для асимптотического поведения функции H (n, k, 2) справедливо
H (n, k) = ck R n,
где ck — константа, зависящая только от k, а R & gt- 1 — наибольший по модулю действительный корень характеристического уравнения Xk — 2Xk-1 + Xk-2 -1 = 0 рекуррентного соотношения (1).
Пусть теперь p & gt- 3.
Теорема 5. Набор X = (xlxn) является рабочим для отображения A: Q ^ Q тогда и только тогда, когда этот набор не содержит вхождений следующих поднаборов:
1. a, 0,…, 0,(p-1), где a е 1, p -1 и r el, k — 2.
r
2. a,(p -1), где a e 2, p -1.
3. b, 0,…, 0,1,…, 1,(p-1), где b е 1, p-1, r el, k-2 и s el, n-k.
4. b, 1,…, 1,(p -1), где b e 2,^-1, s el, n-k.
s
5. W,^-1).
n-k+1
Найден и явный вид функции H (n, k, p) числа рабочих n-наборов нашего отображения для любых n, к и р. В теореме 6 приводится вид этой функции для к = n — 1.
Теорема 6. Для числа рабочих n-наборов отображения A: Qp p при
k = n — 1 справедлива формула
H (n, к, p) = (p -1)" + pn.
ЛИТЕРАТУРА
1. Лихошвай В. А., Матушкин Ю. Г., Фадеев С. И. Задачи теории функционирования генных сетей // Сиб. журн. индустр. математики. 2003. Т. 6. № 2(14). С. 64 — 80.
2. Григоренко Е. Д., Евдокимов А. А., Лихошвай В. А., Лобарева И. А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестник ТГУ. Приложение. 2005. № 14. C. 206 — 212.
Статья представлена кафедрой информационных технологий в исследовании дискретных структур радиофизического факультета Томского государственного университета и оргкомитетом 7 Российской конференции с международным участием «Новые информационные технологии в исследовании сложных структур», поступила в научную редакцию 10 мая 2008 г.

ПоказатьСвернуть
Заполнить форму текущей работой