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

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2008 Управление, вычислительная техника и информатика № 2

УДК 618.5:519.68

А.А. Евдокимов, Е.О. Лиховидова

ДИСКРЕТНАЯ МОДЕЛЬ ГЕННОЙ СЕТИ ЦИРКУЛЯНТНОГО ТИПА С ПОРОГОВЫМИ ФУНКЦИЯМИ

Рассматривается дискретная модель генных сетей, функционирование которых определяется заданием аддитивного автоматного отображения. Получено описание нового класса циклов и рабочих наборов моделей циклического типа, структура которых является циркулянтным ориентированным графом.

Ключевые слова: генные сети, ориентированный граф, аддитивный автомат, граф состояний отображения, циклы графа состояний, рабочие наборы графа состояний.

1. Введение, основные определения

Генные сети служат основой для моделирования процессов, протекающих в клетке: поддерживают в организме устойчивые состояния, характеризующиеся постоянством концентрации веществ (стационарные состояния); обеспечивают периодические незатухающие колебания концентраций определенных групп веществ (циклы); контролируют необратимые процессы развития и роста [1].

Контуры с положительными и отрицательными обратными связями обеспечивают управление генной сетью. Некоторые структурные особенности строения регуляторных контуров естественно формулируются в терминах ориентированных графов и дискретных моделей функционирования регуляторных контуров.

Ниже рассматривается одна из таких моделей. Регуляторный контур генной сети представляется в виде связного ориентированного графа G(V,D), где V е 1, п -множество вершин, отождествляемое с продуктами генетических элементов (РНК, белки), а Б - множество дуг, имеющих смысл регуляторных связей. В качестве графов мы рассматриваем ориентированные циркулянт-ные графы Оп,к, где (к - 1) - число входящих (и выходящих) дуг, к < п [2]. На рис. 1 изображен граф 06,3.

В вершинах графа в каждый момент времени подсчитываются значения некоторых функций /(\ >—>х1к) (возможно, одной функции), сопоставленных вершинам, а переменные х;, , у е 1, к, приписаны дугам, входящим в вершину V и

к = а+ (V). Значения функции / : Nк ^ N , где N е 1, р -1, содержательно соответствуют уровню концентрации, далее называемому весом вершины, конечного продукта, синтезируемого с генетического элемента, соответствующего заданной вершине.

Функционирование генной сети характеризуется изменением концентрации ее веществ, т.е. сменой п-наборов из Nк, соответствующих значениям функций /у в п вершинах сети в каждый момент времени. Таким образом, для каждого началь-

ного состояния (и-набора) динамика изменения состояний определяется отображением А : Ор ^ Ор, где Ор - множество наборов весов вершин графа 0„,к. Будем считать, что все функции /г в вершинах из V равны и определяются следующим образом. Для любой вершины V /(хі,..., хі+к) = х/, где

хі +1, если ^ х] = 0 и хі < р -1; хі -1, если ^ х .• > 0 и хі > 0;

]

хі, иначе,

Ц- = {(г - у )(шоё п)|/ е 1, к -1} - номера вершин, дуги из которых ведут в вершину V. (По условию цикличности полагаем х0 = хп.) Отображение А : Ор ^ Ор,

определяемое таким образом, назовем действием аддитивного (автономного) автомата А(/, р) на множестве Ор. Здесь и далее действие автомата А(/, р) задается

на графе Оп,к.

Последовательность наборов X1,...,Хг € 0.р называется циклом длины г аддитивного автомата А(/, р), если

ГА(х1) = X1+, I елГг;

[ хг+1 = х[.

При г = 1 имеем А(X1) = X1 и X1 называется неподвижной точкой отображения А: О р ^ О р.

Графом состояний отображения А : Ор ^ Ор называется ориентированный граф, вершинами которого являются элементы X & Ор , причем дуга из вершины X идет в вершину У е Ор тогда и только тогда, когда А(Х) = 7 .

Набор У е Ор называется рабочим для отображения А : Ор ^ Ор, если существует X & О , для которого А(Х) = 7 . В графе состояний это соответствует дуге {У, X).

Анализ поведения генной сети включает исследование динамики изменения ее состояний, которая полностью характеризуется видом графа состояний и включает исследование циклов, оценку числа рабочих наборов в зависимости от значений параметров п, к ир и т. д.

2. Циклы отображения графа состояний

В [2] было описано действие аддитивного автомата на наборы Xг = (О^О,р - 1,0и0), г е 1,1,

I-1 П—

где d = нод(п, к), в зависимости от значения к, а также циклы, возникающие в результате этого действия в случае d < к. При 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 > 2 .

В настоящей работе нами получено описание нового класса циклов для случая n = 2k. Пусть r > 1.

Цикл Xх,...,Xr автомата Af, p) называется p-собственным, если для всех р1 < p определяющая его последовательность Xх,...,Xr не является циклом автомата Af, р1). В противном случае будем называть его несобственным для p.

P-собственный цикл Xх,..., Xr автомата Af, p) называется наследственным, если для любого p2 > p определяющая его последовательность Xх,..., Xr является циклом автомата Af p2).

Набор (x1,...,xn) назовем <^,/>-набором, если он содержит поднабор 0k-1 d ,

вхождение которого начинается с /-й координаты, где l е 1, n .

Лемма 1. (Критерий ^-собственности.) Цикл являлся ^-собственным тогда и только тогда, когда существует l е 1, n , что цикл содержит <p - 2, / >-набор.

Следующая теорема сводит описание циклов для произвольного p > 4 к описанию 4-собственных циклов и наследственных циклов для p = 3 .

Теорема 1 (о сводимости). При p > 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 < k - 2 , где r el, k - 2, m e 0, k - 3 .

3. Рабочие наборы графа состояний

Пусть в начале p = 2.

Заметим, что если k = 2, то все n-наборы являются рабочими для нашего отображения A: Q2 ^ ^2.

Теорема 3. Если k > 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

Теорема 4. При фиксированном k > 3 для асимптотического поведения функции H (n, k ,2) справедливо

H (n, k) = ck R n,

где ck - константа, зависящая только от k, а R > 1 - наибольший по модулю действительный корень характеристического уравнения Xk - 2Xk-1 + Xk-2 -1 = 0 рекуррентного соотношения (1).

Пусть теперь p > 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 г.