Свойства генных сетей циркулянтного типа с пороговыми функциями | ПДМ. 2013. № 6 (Приложение).

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

Описан алгоритм нахождения всех неподвижных точек графа состояний генной сети циркулянтного типа с произвольной булевой функцией. Описаны все истоки графа состояний генной сети с пороговой функцией от k переменных, такой, что существует единственный набор v, для которого f (v) = 1. Для таких функций от трёх переменных описаны все циклы графа состояний и вычислены длины максимальных цепочек до цикла.

Properties of gene networks with threshold functions.pdf Пусть n ^ к — натуральные числа. Циклическим словом называется периодическое бесконечное в две стороны слово с периодом n; обозначается а1 a2 ... an. Множество всех циклических слов длины n будем обозначать через Qn. Рассмотрим ориентированный граф Gn,k+1 = (V, E), где множество вершин V равно {v1,... ,vn} (последовательность вершин соответствует циклическому слову), а множество рёбер E такое, что каждая вершина vi имеет входящие рёбра из к предыдущих вершин и выходящие в k следующих вершин. Пороговой функцией называется булева функция, которая представима в виде " k 1 Y, ai Xi > T i=1 ai,T e R. Рассмотрим пороговую функцию f, зависящую от k переменных. Построим отображение Af : Qn ^ Qn, которое каждому слову a1a2 ... an ставит в соответствие слово b1b2 .. .bn, если bi = f (ai-k, ai-k+1, . . . , ai-1) для всех i e {1,...,n}. Неподвижной точкой отображения Af называется слово а, такое, что а = Af (а). Циклическое слово а называется истоком для отображения Af : Qn ^ Qn, если не существует слова в, такого, что Af (в) = а. Графом состояний отображения Af : Пга Т Пга называется ориентированный граф, в котором Пга — множество вершин, а дуги соединяют слова а и в, если в = Af (а). Данная работа посвящена описанию свойств графа состояний отображения Af, а именно описанию истоков, неподвижных точек и циклических состояний, нахождению длин максимальных цепочек. Пусть f — булева функция от к переменных. Построим ориентированный граф Pf, вершинами которого являются все возможные слова длины к, а рёбра соединяют слова x1 ... xk и x2 ... xkb, если f (xi,... , xk) = b. Следующая теорема содержит способ нахождения всех неподвижных точек графов состояния отображения Af для произвольной булевой функции от к переменных. Теорема 1. Пусть f — булева функция от к переменных и n кратно l. Граф Pf содержит простой цикл (v1,...,vl), где v = Xj . ..xk+i-1 для i G {1,...,l}, тогда и только тогда, когда (x1... Xi)n/l является неподвижной точкой графа состояний отображения Af. В следующей теореме описаны все истоки графа состояний отображения. Теорема 2. Пусть f — булева функция от к переменных и существует единственный набор значений переменных v, такой, что f (v) = 1. Тогда циклическое слово а длины n является истоком графа состояний отображения Af тогда и только тогда, когда оно удовлетворяет одному из условий: 1) а содержит подслово 10s-11, где 1 ^ s ^ к — 1 и s = s'; 2) а содержит подслово 10k-11, где к = is' и t ^ 2. Здесь s' — минимальный период слова v. Получено описание всех циклов и длин максимальных цепочек для графа состояний отображения Af, где f — булева функция от трёх переменных, удовлетворяющая условию предыдущей теоремы. Если f(0, 0, 0) = 1, то циклы этого графа представляют циклический сдвиг на 1, 2 или 3 позиции состояния, избегающего определённые слова.

Ключевые слова

генная сеть, ориентированный граф, пороговая функция, граф состояний отображения, цикл, неподвижная точка, исток графа состояний, gene network, directed graph, threshold functions, state graph of mapping, fixed point, source of state graph

Авторы

ФИООрганизацияДополнительноE-mail
Батуева Цындыма Чимит-ДоржиевнаИнститут математики им. С. Л. Соболева Сибирского отделения Российской академии наук (г. Новосибирск)кандидат физико-математических наук, научный сотрудникbatueva@math.nsc.ru
Всего: 1

Ссылки

 Свойства генных сетей циркулянтного типа с пороговыми функциями | ПДМ. 2013. № 6 (Приложение).

Свойства генных сетей циркулянтного типа с пороговыми функциями | ПДМ. 2013. № 6 (Приложение).

Полнотекстовая версия