On cycles in functional graphs of circulant type gene networks with threshold functions.pdf В работе рассматривается функционирование дискретных моделей генных сетей [1]. Как ив [2], рассматриваются пороговые функции в вершинах с произвольным пороговым значением T. Состоянием генной сети назовём кортеж (so, s1,... , sn-1), где si £ {0,1,... ,p - 1}. Функционированием такой системы будем называть последовательное изменение состояний S,A(S ),A2(S ),A3(S),..., где S - некоторое состояние; A - отображение, действующее на множестве всех состояний. Отображение A задается пороговой функцией с двумя параметрами k и T следующим образом: пусть S = (s0, s1,... , sn-1), тогда A(S) = (s0, s'b ... , s^-1), где k si + 1, если E sj+j < T и si 0, j=1 si иначе. Здесь и далее операции в индексах выполняются по модулю n. В работе рассматривается функционирование системы при p = 2. В этом случае k . 0, если Е si+j ^ T, si = \ j=1 1 иначе. Графом функционирования называют ориентированный граф G(V, D), где V - множество всех состояний; D = {(S1, S2) : S1, S2 G V; A(S1) = S2}. Задачей анализа функционирования называется задача описания качественных характеристик графа функционирования по заданным параметрам n, k, T. Одной из таких задач является изучение свойств состояний, входящих в циклы графа функционирования. Рассматривая полученные свойства, можно получать оценки на количество циклов (компонент связности) графа функционирования, а также перечислять некоторые из циклов. Выделим среди множества всех состояний два подмножества: состояния с длинными сериями и состояния с короткими сериями. 1. Состояния с длинными сериями Определение 1. Состояние S будем называть состоянием с длинными сериями, если длина каждой серии из нулей не меньше k - T +1, а длина каждой серии из единиц не меньше T. Теорема 1. Любое состояние с длинными сериями лежит в цикле графа функционирования. Все состояния этого цикла также являются состояниями с длинными сериями. В силу теоремы 1, подсчитав количество состояний с длинными сериями, можно получить, например, следующую оценку на количество циклов в графе функционирования. Теорема 2. Количество циклов в графе функционирования системы с параметрами n, k, T не менее Lk+1J - 1+ £ P(n - (k - 1)i, 2i), i=1 где P(a, b) -число циклических разбиений a на b слагаемых. 2. Состояния с короткими сериями Определение 2. Состояние S будем называть состоянием с короткими сериями, если длина каждой серии из нулей не больше k - T, а длина каждой серии из единиц не больше T - 1. Теорема 3. Если состояние лежит в цикле графа функционирования, то оно является либо состоянием с длинными сериями, либо состоянием с короткими сериями. Обозначим вес состояния (количество ненулевых компонент) как W(S). Состояния с короткими сериями в системах с большими параметрами можно строить из подходящих систем с меньшими параметрами, используя одну из следующих двух конструкций. Теорема 4. Пусть имеется q систем, Si - состояние с длинными сериями в системе с параметрами ni, ki, Ti и отображением Aj. Тогда если для некоторых k и T и любого 0 ^ j ^ q - 1 выполняются условия k = kj + Е ni - n, T = Tj + E W(Si) - W(Sj), W(S) = W(Aj(Sj)), i=0 i=0 то состояние S - So S1 ... Sq- 1 лежит в цикле графа функционирования системы с параметрами n = £ ni, k = ko + £ n - no, T = To + £ W(Si) - W(So) i=0 i=0 i=0 и является состоянием с короткими сериями. Теорема 5. Пусть состояние S' лежит в цикле графа функционирования системы с параметрами n', k', T' и отображением A' и выполнено условие W(S) = W(A'(S')). Тогда состояние ' ' ' ' S = S S . . . S S 4-V-' m лежит в цикле графа функционирования системы с параметрами n = mn', k = k' + Zn', T = T' + 1W(S') и является состоянием с короткими сериями для всех 0 < Z < m.

Скачать электронную версию публикации