A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
A Feedback Vertex Set-Based Approach to Simplifying Probabilistic Boolean Networks
Abra o Access
Uma abordagem baseada em conjunto de vértices de feedback para simplificar redes booleanas probabilísticas

Koichi KOBAYASHI

  • Exibições de texto completo

    231

  • Cite isto
  • Free PDF (736.4KB)

Resumo:

Um PBN é bem conhecido como um modelo matemático de sistemas de redes complexos, como redes reguladoras de genes. Nas redes booleanas, as interações entre nós (por exemplo, genes) são modeladas por funções booleanas. Nos PBNs, as funções booleanas são trocadas probabilisticamente. Neste artigo, para um PBN, é proposta uma representação simplificada que seja eficaz na análise e controle. Primeiro, após uma breve explicação de uma representação polinomial de um PBN, uma representação simplificada é derivada. Aqui, o valor de estado estacionário do valor esperado do estado é focado e é caracterizado por um conjunto de vértices de feedback mínimo de um gráfico de interação que expressa interações entre nós. A seguir, usando esta representação, são discutidas a seleção e estabilização de entradas. Finalmente, o método proposto é demonstrado por um exemplo biológico.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.5 pp.779-785
Data de publicação
2024/05/01
Publicitada
2023/09/26
ISSN online
1745-1337
DOI
10.1587/transfun.2023MAP0004
Tipo de Manuscrito
Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
Categoria

1. Introdução

O controle de sistemas de redes complexos, como redes reguladoras de genes, é um dos problemas centrais da teoria de controle. Para simplificar tais sistemas, a aproximação por modelos discretos é frequentemente eficaz. Na análise e controle de redes reguladoras de genes, uma rede booleana (BN) é bem conhecida como um dos modelos discretos [1]. Em uma BN, a expressão de um gene (nó) é dada por um valor binário (ON/OFF), e as interações entre genes são modeladas por funções booleanas. Além disso, uma BN é estendida a uma rede booleana probabilística (PBN). Em um PBN, os candidatos das funções booleanas são dados antecipadamente, e um é escolhido probabilisticamente entre os candidatos [2].

Na última década, vários métodos de controle para PBNs foram desenvolvidos (ver, por exemplo, [3]-[11]). Esses métodos têm desvantagens. Por exemplo, tanto no método baseado em cadeia de Markov [7]-[9] quanto no método do produto semitensor [5], [6], [11], \(2^n \times 2^n\) matrizes devem ser manipuladas, onde \(n\) é o número de nós. Nos métodos de [3], [4], um problema de programação inteira ou um problema de otimização polinomial deve ser resolvido. É importante desenvolver um método simples e útil para análise e controle de um PBN.

Neste artigo, estudamos uma nova abordagem para simplificar um PBN com foco nas interações entre nós.

Primeiramente, propomos uma representação simplificada, que pode ser derivada da representação polinomial proposta em [4]. A representação polinomial representa o valor esperado do estado de um determinado PBN. Porém, em [4], o problema de controle ótimo foi focado principalmente, e a simplificação da representação polinomial não foi estudada. Para analisar o comportamento de um PBN é importante considerar uma representação simplificada de que algumas propriedades são preservadas. A representação simplificada aqui proposta preserva as propriedades do estado estacionário. Para derivá-lo, usamos um conjunto mínimo de vértices de feedback de um gráfico de interação que expressa interações entre nós, onde cada vértice de um gráfico de interação corresponde a cada nó (veja a Seção 2 para mais detalhes). Usando a representação proposta, o valor de estado estacionário do valor esperado do estado pode ser caracterizado apenas por vértices em um conjunto de vértices de feedback mínimo. Em geral, o número de vértices em um conjunto mínimo de vértices de feedback é muito menor que o número de vértices em um gráfico de interação. Assim, a dinâmica de um determinado PBN pode ser simplificada. Para uma BN, tal método foi proposto em, por exemplo, [12], [13]. Além disso, a importância dos conjuntos de vértices de feedback na análise de BNs foi apontada em [14]. Em [12]-[14], apenas um BN foi focado e um PBN não foi considerado. O método proposto pode ser considerado como uma extensão destes métodos para um PBN.

A seguir, a representação simplificada pode ser aplicada ao problema de seleção de insumos. Em muitos casos, as redes reguladoras genéticas não têm entradas de controlo (externas). Como primeiro passo no estudo do controle de tais sistemas, é importante escolher nós de controle dentre os nós. No nó de controle, assumimos que o valor binário inicial pode ser definido arbitrariamente (isto é, consideramos a entrada de controle constante). No método proposto, os vértices em um conjunto de vértices de realimentação mínimo são considerados como nós de controle (ver também [15], [16]). Através de uma representação simplificada, a estabilidade pode ser facilmente analisada e as entradas de controle constantes podem ser derivadas.

Finalmente, demonstramos um método de derivação de entradas de controle constantes por meio de um exemplo de via de sinalização de neurotransmissor [17].

Este artigo está organizado da seguinte forma. Primeiro, o esboço dos PBNs é explicado e os gráficos de interação e conjuntos mínimos de vértices de feedback são definidos. A seguir, após resumir uma representação polinomial de PBNs, uma representação simplificada é proposta. O problema de seleção de entrada também é explicado. Finalmente, um exemplo biológico é apresentado.

Notação: Deixei \(\{ 0,1 \}^{n}\) denotar o conjunto de \(n\)vetores -dimensionais, que consistem em elementos \(0\) e \(1\). Para o \(n\)vetor tridimensional \(x = [ x_1~~x_2~~\cdots\) \(x_n ]^{\top}\) e o conjunto de índices \({\mathcal I} = \{ i_1, i_2, \dots, i_m \} \subseteq \{ 1,2,\dots,n\}\), definir \([x_i]_{i \in {\mathcal I}} := [ x_{i_1}~~x_{i_2}~~\cdots~~x_{i_m} ]^{\top}\).

2. Redes Booleanas Probabilísticas

Nesta seção, primeiro, um PBN é brevemente explicado.

Em um PBN representando uma rede complexa com \(n\) nós, cada nó tem um valor binário \(x_i \in \{ 0,1 \}\), \(i \in \{ 1,2,\dots,n \}\). A dinâmica para \(x_i\) são dados por

\[\begin{align} x_i(k+1) &= f^{(i)}([x_j(k)]_{j \in {\mathcal N}^{(i)}}) \nonumber \\ &= \begin{cases} f^{(i)}_1([x_j(k)]_{j \in {\mathcal N}^{(i)}_1}), \mbox{Prob. $c^{(i)}_1$,} \\ f^{(i)}_2([x_j(k)]_{j \in {\mathcal N}^{(i)}_2}), \mbox{Prob. $c^{(i)}_2$,} \\ \vdots \\ f^{(i)}_{q(i)}([x_j(k)]_{j \in {\mathcal N}^{(i)}_{q(i)}}), \mbox{Prob. $c^{(i)}_{q(i)}$,} \end{cases} \tag{1} \end{align}\]

onde \(k = 0,1,2,\dots\) é o tempo discreto, o conjunto \({\mathcal N}^{(i)}_l \subseteq \{ 1,2,\dots,n \}\), \(l=1,2,\dots,q(i)\) é um determinado conjunto de índices, e o conjunto \({\mathcal N}^{(i)}\), \(i=1,2,\dots,n\) é definido por

\[{\mathcal N}^{(i)} := \bigcup_{l=1}^{q(i)} {\mathcal N}^{(i)}_{l}.\]

A função \(f^{(i)}_l : \{ 0,1 \}^{|{\mathcal N}^{(i)}_l|} \rightarrow \{ 0,1 \}^1\) é uma determinada função booleana que consiste em operadores lógicos como AND (\(\wedge\)), OU (\(\vee\)), e não (\(\neg\)). Se \({\mathcal N}^{(i)}_l = \emptyset\) é válido, então o valor (\(0\) or \(1\)) da função booleana \(f^{(i)}_l\) é unicamente determinado como \(0\) or \(1\). A probabilidade \(c^{(i)}_l\), \(l=1,2,\dots,q(i)\) é formalmente definido por

\[c^{(i)}_l := {\rm Prob} \left( f^{(i)}=f^{(i)}_l \right).\]

Para \(c^{(i)}_l\), a seguinte relação:

\[\begin{equation*} \sum_{l=1}^{q(i)} c^{(i)}_l = 1 \tag{2} \end{equation*}\]

deve estar satisfeito. Nós definimos o estado \(x(k) := [ x_1(k) x_2(k) \cdots\) \(x_n(k) ]^{\top} \in \{ 0,1 \}^n\).

Apresentamos um exemplo simples.

1 exemplo: Considere o PBN no qual funções e probabilidades booleanas são dadas por

\[\begin{aligned} f^{(1)} &= \begin{cases} f^{(1)}_1 = x_3(k), c^{(1)}_1 = 0.8, \\ f^{(1)}_2 = \neg x_3(k), c^{(1)}_2 = 0.2, \end{cases} \\ f^{(2)} &= f^{(2)}_1 = x_1(k) \wedge \neg x_3(k), c^{(2)}_1 = 1.0, \\ f^{(3)} &= \begin{cases} f^{(3)}_1 = x_1(k) \wedge \neg x_2(k), c^{(3)}_1 = 0.7, \\ f^{(3)}_2 = x_2(k), c^{(3)}_2 = 0.3, \end{cases} \end{aligned}\]

onde \(q(1) = 2\), \(q(2) = 1\) e \(q(3) = 2\) aguarde, \({\mathcal N}^{(1)} = \{ 3 \}\), \({\mathcal N}^{(2)} = \{ 1,3 \}\) e \({\mathcal N}^{(3)} = \{ 1,2 \}\) segure, e vemos que a relação (2) é satisfeita. A seguir, considere a trajetória do estado. Então para \(x(0) = [ 0~~ 0~~ 0 ]^{\top}\), nós obtemos

\[\begin{aligned} {\rm Prob} \left( x(1) = [ 0 ~~ 0 ~~ 0 ]^{\top} | x(0) = [ 0 ~~ 0 ~~ 0 ]^{\top} \right) &= 0.8, \\ {\rm Prob} \left( x(1) = [ 1 ~~ 0 ~~ 0 ]^{\top} | x(0) = [ 0 ~~ 0 ~~ 0 ]^{\top} \right) &= 0.2. \end{aligned}\]

Neste exemplo, a cardinalidade do conjunto de estados finitos \(\{ 0,1 \}^3\) É dado por \(2^3 = 8\), e obtemos o diagrama de transição de estado da Fig. 1 calculando a transição de cada estado. Na Fig. 1, o número atribuído a cada nó denota \(x_1\), \(x_2\), \(x_3\), e o número atribuído a cada arco denota a probabilidade de transição de um estado para outro estado. Observe aqui que, para simplificar, a transição de estado de apenas \(x(k) = [ 0 ~~ 0 ~~ 0 ]^{\top}, \ [ 0 ~~ 0 ~~ 1 ]^{\top}, \ [ 0 ~~ 1 ~~ 0 ]^{\top}, \ [ 1 ~~ 1 ~~ 0 ]^{\top}\) está ilustrado na Figura 1. \(\tag*{◻}\)

FIG. 1  Diagrama de transição de estado do PBN no Exemplo 1. Para simplificar, a transição de estado de apenas \(x(k) = [ 0 ~~ 0 ~~ 0 ]^{\top}, \ [ 0 ~~ 0 ~~ 1 ]^{\top}, \ [ 0 ~~ 1 ~~ 0 ]^{\top}, \ [ 1 ~~ 1 ~~ 0 ]^{\top}\) é ilustrado.

A seguir, definimos um gráfico de interação para um determinado PBN como segue.

Definição 1: Um gráfico de interação de um determinado PBN é definido por um gráfico direcionado \(G = ({\mathcal V}, {\mathcal E})\), Onde \({\mathcal V} = \{ 1,2,\dots,n \}\) é o conjunto de vértices correspondentes a \(x_i\), \(i \in \{ 1,2,\dots,n \}\) e \({\mathcal E} = \{ (j,i) \in \{ 1,2,\dots,n \} \times \{ 1,2,\dots,n \} | j \in {\mathcal N}^{(i)} \}\) é o conjunto de arcos.

Para um determinado gráfico de interação, um conjunto de vértices de feedback é definido como segue (ver, por exemplo, [18], [19]).

Definição 2: Um conjunto de vértices de um grafo de interação é chamado de conjunto de vértices de feedback se a remoção de vértices resultar em um gráfico acíclico. Em particular, um conjunto de vértices de feedback é chamado de conjunto de vértices de feedback mínimo se o número de seus elementos for mínimo.

A complexidade computacional para encontrar um conjunto mínimo de vértices de feedback é NP-completa [19], mas um algoritmo aproximado para encontrá-lo foi desenvolvido (ver, por exemplo, [18]).

Apresentamos dois exemplos.

2 exemplo: Considere novamente o PBN do Exemplo 1. De \({\mathcal N}^{(1)} = \{ 3 \}\), \({\mathcal N}^{(2)} = \{ 1,3 \}\) e \({\mathcal N}^{(3)} = \{ 1,2 \}\), seu gráfico de interação é dado pela Fig. 2. Além disso, o conjunto mínimo de vértices de feedback é dado por \(\{ 3 \}\). \(\tag*{◻}\)

FIG. 2  Gráfico de interação do PBN no Exemplo 1.

3 exemplo: Considere o gráfico de interação de uma rede de apoptose dado pela Fig. 3. Veja [20] para detalhes. Na Figura 3, vemos que um dos conjuntos mínimos de vértices de feedback é dado por {NF\(\kappa\)B\(_{\rm nuc}\), C3a, TNF}. \(\tag*{◻}\)

FIG. 3  Gráfico de interação de uma rede de apoptose [20] no Exemplo 3.

3. Representação Polinomial de Redes Booleanas Probabilísticas

Nesta seção, explicamos uma representação polinomial de um determinado PBN [4]. Usando-o, o valor esperado do estado (\(E[x_i(k)|\ast]\)) pode ser representado por um sistema polinomial.

Como preparação, o seguinte lema [21] é introduzido.

Lema 1: Considere duas variáveis ​​binárias \(\delta_1\) e \(\delta_2\). Então as seguintes relações são válidas.

(I) \(\neg \delta_1\) é equivalente a \(1 - \delta_1\).

(Ii) \(\delta_1 \wedge \delta_2\) é equivalente a \(\delta_1 \delta_2\).

(iii) \(\delta_1 \vee \delta_2\) é equivalente a \(\delta_1 + \delta_2 - \delta_1 \delta_2\).

Pelo Lema 1, uma determinada função booleana pode ser transformada em um polinômio no corpo de números reais. Por exemplo, a fórmula lógica \(\delta_1 \vee \neg \delta_2\) é equivalentemente transformado no polinômio \(\delta_1 + (1-\delta_2) - \delta_1 (1-\delta_2) = 1 - \delta_2 + \delta_1 \delta_2\).

A seguir, assumimos que a função booleana \(f^{(i)}_j\) é expresso como um polinômio com variáveis ​​binárias. Para simplificar a notação, a condição em \(E[x_i(k)|\ast]\) é omitido. Então, o seguinte resultado foi obtido em [4].

Teorema 1: Suponha que para o PBN (1), o estado inicial \(x(0)=x_0\) é dado arbitrariamente. Então, o valor esperado do estado, \(E[x_i(k)] \in [0,1]\) é expresso como o seguinte sistema polinomial:

\[\begin{align} E[x_i(k+1)] &= \tilde{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal N}^{(i)}}]), \tag{3} \\ \tilde{f}^{(i)} &= \sum_{l=1}^{q(i)} c^{(i)}_l f^{(i)}_l(E[[x_j(k)]_{j \in {\mathcal N}_j^{(i)}}]). \nonumber \end{align}\]

Apresentamos um exemplo simples.

4 exemplo: Considere novamente o PBN do Exemplo 1. Então, o sistema polinomial para \(x_1\) é derivado como

\[\begin{aligned} E[x_1(k+1)] &= 0.8 E[x_3(k)] + 0.2 (1-E[x_3(k)]) \\ &= 0.2 + 0.6 E[x_3(k)]. \end{aligned}\]

De maneira semelhante, o sistema polinomial para \(x_2\) é derivado como

\[\begin{aligned} E[x_2(k+1)] &= E[x_1(k)] - E[x_1(k)] E[x_3(k)]. \end{aligned}\]

Finalmente, o sistema polinomial para \(x_3\) é derivado como

\[\begin{aligned} E[x_3(k+1)] =& \ 0.7 ( E[x_1(k)] - E[x_1(k)] E[x_2(k)] ) \\ & + 0.3 E[x_2(k)] \\ =& \ 0.7 E[x_1(k)] + 0.3 E[x_2(k)] \\ & - 0.7 E[x_1(k)] E[x_2(k)]. \end{aligned}\]

\(\tag*{◻}\)

Observamos aqui que o sistema polinomial (3) é uma classe de sistemas positivos sob um estado inicial binário.

4. Representação Simplificada de Redes Booleanas Probabilísticas

Nesta seção, consideramos a simplificação da representação polinomial (3) para um determinado PBN. Aqui, nos concentramos no estado estacionário do sistema (3).

Como preparação, deixe \({\mathcal W}\) denota um conjunto mínimo de vértices de feedback do gráfico de interação \(G\). Deixei \(G_I = ({\mathcal V}, {\mathcal E}_I)\), \({\mathcal E}_I := \{ (i,j) | (j,i) \in {\mathcal E} \}\) denotam o gráfico direcionado obtido invertendo os nós inicial e final do arco do gráfico de interação \(G\). Para \(G_I\), deixei \(d_i\) denota o comprimento do caminho/ciclo mais longo do nó \(i\) para um vértice de \({\mathcal W}\). Por exemplo, no caso do gráfico de interação da Fig. 2, uma vez que \({\mathcal W}\) É dado por \({\mathcal W} = \{ 3 \}\), \(d_1 = 1\) segura. Para o nó \(2\), existem dois caminhos (\(2 \rightarrow 1 \rightarrow 3\) e \(2 \rightarrow 3\)), E \(d_2 = 2\) segura. Para o nó \(3\), existem três caminhos (\(3 \rightarrow 1 \rightarrow 3\), \(3 \rightarrow 2 \rightarrow 3\) e \(3 \rightarrow 2 \rightarrow 1 \rightarrow 3\)), E \(d_3 = 3\) segura. Observamos que mesmo que o nó \(i\) está incluído no \({\mathcal W}\), devemos encontrar caminhos.

Além disso, deixe \({\mathcal W}_{i,l}\), \(l=0,1,\dots,d_i-1\) denota um subconjunto de \({\mathcal W}\) tal que exista um caminho do seu elemento até o nó \(i\) com o comprimento \(l+1\) sobre o gráfico \(G\). Por exemplo, no caso do gráfico de interação na Fig. 2 (\({\mathcal W} = \{ 3 \}\)), podemos obter \({\mathcal W}_{1,0} = \{ 3 \}\), \({\mathcal W}_{2,0} = {\mathcal W}_{2,1} = \{ 3 \}\), \({\mathcal W}_{3,0} = \emptyset\) e \({\mathcal W}_{3,1} = {\mathcal W}_{3,2} = \{ 3 \}\).

O procedimento proposto é dado a seguir.

Procedimento para derivar uma representação simplificada:

- Para um determinado gráfico de interação, encontre um conjunto mínimo de vértices de feedback \({\mathcal W}\).

- utilização \(E[x_i(k-l+1)] = \tilde{f}^{(i)}(E[[x_j(k-l)]_{j \in {\mathcal N}^{(i)}}])\), \(l = 1,2,\dots,d_i-1\), reescreva o polinômio \(\tilde{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal N}^{(i)}}])\) como o seguinte polinômio equivalente:

\[\begin{eqnarray*} \tilde{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal W}_{i,0}}], E[[x_j(k-1)]_{j \in {\mathcal W}_{i,1}}],\nonumber\\ \dots,E[[x_j(k-d_i+1)]_{j \in {\mathcal W}_{i,d_i-1}}]). \tag{4} \end{eqnarray*}\]

- Para o polinômio obtido, substitua \(E[[x_j(k-l)]_{j \in {\mathcal W}_{i,l}}]\), \(l = 1,2,\dots,d_i-1\) fazendo o melhor dos nossos \(E[[x_j(k)]_{j \in {\mathcal W}_{i,l}}]\). Deixei \(\hat{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal W}_i}])\) denota o polinômio obtido, onde \({\mathcal W}_i = \cup_{l} {\mathcal W}_{i,l}\).

- Obtenha a representação simplificada como

\[\begin{equation*} E[\hat{x}_i(k+1)] = \hat{f}^{(i)}(E[[\hat{x}_j(k)]_{j \in {\mathcal W}_i}]), \tag{5} \end{equation*}\]

onde \(\hat{x}_i\) é recentemente definido como uma variável binária.

Na Etapa 2, \(\tilde{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal N}^{(i)}}])\) e (4) são equivalentes. Porque os sistemas polinomiais nos quais o tempo é deslocado são substituídos em \(\tilde{f}^{(i)}(E[[x_j(k)]_{j \in {\mathcal N}^{(i)}}])\). A partir da definição de conjuntos mínimos de vértices de realimentação, o Passo 2 pode ser necessariamente executado. Na representação simplificada proposta, a dinâmica é expressa apenas por \(E[[\hat{x}_j(k)]_{j \in {\mathcal W}_i}]\). Como foi explicado na Seção. 2, a complexidade computacional para encontrar um conjunto mínimo de vértices de feedback é NP-completa. Conseqüentemente, a complexidade computacional da Etapa 1 também é NP-completa. Na Etapa 2, para cada \(i\), são realizadas substituições de polinômios por certos termos de outros polinômios \(d_i-1\) vezes. Na Etapa 3, \(k-1, k-2, \dots, k-d_i+1\) são substituídos por \(k\). Na Etapa 4, a variável binária na representação simplificada é definida novamente para distinguir entre o PBN original e o PBN simplificado. Se um conjunto mínimo de vértices de feedback for fornecido, as etapas 2 a 4 podem ser implementadas por um software adequado, como MATLAB e Mathematica.

Apresentamos um exemplo simples.

5 exemplo: Considere o sistema polinomial obtido no Exemplo 4. No Exemplo 2, o conjunto mínimo de vértices de realimentação é dado por \(\{ 3 \}\). Da Figura 2, \(d_1=1\), \(d_2=2\) e \(d_3=3\) segura. Primeiro, considere o sistema polinomial para \(x_1\). Neste sistema, apenas \(E[x_3(k)]\) é incluído como uma variável de estado (isso pode ser confirmado também \({\mathcal W}_{1,0} = \{ 3 \}\)). Então, de \(d_1=1\), não podemos simplificá-lo e podemos obter a seguinte representação simplificada:

\[\begin{align} E[\hat{x}_1(k+1)] &= \hat{f}^{(1)}(E[\hat{x}_3(k)]) \nonumber \\ &= 0.2 + 0.6 E[\hat{x}_3(k)]. \tag{6} \end{align}\]

A seguir, considere o sistema polinomial para \(x_2\). De \(d_2=2\), a dinâmica em \(k+1\), \(k\) e \(k-1\) pode ser derivado como

\[\begin{aligned} E[x_2(k+1)] =& \ E[x_1(k)] - E[x_1(k)] E[x_3(k)]. \\ =& \ (0.2 + 0.6 E[x_3(k-1)]) \\ & \ \times (1- E[x_3(k)]). \end{aligned}\]

De \({\mathcal W}_{2,0} = {\mathcal W}_{2,1} = \{ 3 \}\), vemos que a função \(\tilde{f}^{(2)}\) pode ser representado por \(E[x_3(k-1)]\) e \(E[x_3(k)]\). Ao substituir \(E[x_3(k-1)]\) fazendo o melhor dos nossos \(E[x_3(k)]\), o seguinte polinômio simplificado pode ser derivado:

\[\begin{align} E[\hat{x}_2(k+1)] =& \ \hat{f}^{(2)}(E[\hat{x}_3(k)]) \nonumber \\ =& \ 0.2 + 0.4 E[\hat{x}_3(k)] \nonumber \\ & \ - 0.6 E[\hat{x}_3(k)]^2. \tag{7} \end{align}\]

Finalmente, considere o sistema polinomial para \(x_3\). De \(d_3=3\), a dinâmica em \(k+1\), \(k\), \(k-1\) e \(k-2\) pode ser derivado como

\[\begin{aligned} E[x_3(k+1)] =& \ 0.7 ( 0.2 + 0.6 E[x_3(k-1)] ) \\ & \ + 0.3 ( 0.2 + 0.6 E[x_3(k-2)] ) \\ & \ ~~~~~~~~~\times ( 1 - E[x_3(k-1)] ) \\ & \ - 0.7 ( 0.2 + 0.6 E[x_3(k-1)] ) \\ & \ ~~~~~~~~~\times ( 0.2 + 0.6 E[x_3(k-2)] ) \\ & \ ~~~~~~~~~\times ( 1 - E[x_3(k-1)] ). \end{aligned}\]

De \({\mathcal W}_{3,0} = \emptyset\) e \({\mathcal W}_{3,1} = {\mathcal W}_{3,2} = \{ 3 \}\), vemos que a função \(\tilde{f}^{(3)}\) pode ser representado por \(E[x_3(k-2)]\) e \(E[x_3(k-1)]\). Então, o seguinte polinômio simplificado pode ser derivado:

\[\begin{align} E[\hat{x}_3(k+1)] =& \ \hat{f}^{(3)}(E[\hat{x}_3(k)]) \nonumber \\ =& \ 0.172 + 0.4 E[\hat{x}_3(k)] \nonumber \\ & \ - 0.264 E[\hat{x}_3(k)]^2+ 0.252 E[\hat{x}_3(k)]^3. \tag{8} \end{align}\]

De (6), (7) e (8), vemos que \(E[\hat{x}_i(k+1)]\), \(i=1,2,3\) pode ser expresso por um polinômio em relação apenas a \(E[\hat{x}_3(k)]\). \(\tag*{◻}\)

A seguir, consideramos a análise da representação simplificada obtida. A noção de pontos fixos é definida como segue.

Definição 3: Para o sistema (3), \(x_F := [ x_1^F x_2^F \cdots x_n^F ]^{\top}\) é chamado de ponto fixo se \(x_i^F = E[x_i(k+1)] = E[x_i(k)]\), \(i \in \{ 1, 2, \dots, n \}\) segurar. De forma semelhante, para o sistema (5), \(\hat{x}_F := [ \hat{x}_1^F ~ \hat{x}_2^F ~ \cdots ~ \hat{x}_n^F ]^{\top}\) é chamado de ponto fixo se \(\hat{x}_i^F = E[\hat{x}_i(k+1)] = E[\hat{x}_i(k)]\), \(i \in \{ 1, 2, \dots, n \}\) aguarde.

Observamos que \(x_F\) e \(\hat{x}^F\) não são determinados exclusivamente em geral. Então, temos o seguinte teorema.

Teorema 2: O ponto fixo \(x^F\) pois o sistema (3) está em correspondência biunívoca com o ponto fixo \(\hat{x}^F\) para o sistema (5).

Prova: Quando \(x^F\) é calculado, o polinômio (4) pode ser usado. O ponto fixo \(x^F\) pode ser derivado de (4) e \(x_i^F = E[x_i(k+1)] = E[x_i(k)] = E[x_i(k-1)] = \cdots = E[x_i(k-d_i+1)]\), \(i \in \{ 1, 2, \dots, n \}\). Na derivação da representação simplificada (5), o polinômio (4) é simplificado com base em \(E[x_i(k)] = E[x_i(k-1)] = \cdots = E[x_i(k-d_i+1)]\), \(i \in \{ 1, 2, \dots, n \}\). Portanto, há uma correspondência biunívoca entre \(x^F\) e \(\hat{x}^F\). \(\tag*{◻}\)

A partir deste teorema, vemos que a representação simplificada 5 pode ser utilizada para análise e controle de PBNs com foco no ponto fixo (isto é, o comportamento de longo prazo).

5. Discussão sobre Seleção e Estabilização de Insumos

Nesta seção, discutimos a seleção e estabilização de insumos como um dos métodos para utilização da representação simplificada (5). Em [15], [16], um método de controle utilizando um conjunto mínimo de vértices de realimentação foi proposto para o sistema representado por equações diferenciais ordinárias. Neste método, foi demonstrado que a estabilização ou desestabilização pode ser alcançada controlando nós em um conjunto mínimo de vértices de feedback. Motivado por este método, neste artigo, a seguinte suposição, na qual apenas o valor inicial é focado por simplicidade, é imposta para (5).

Suposição 1: O sistema polinomial \(E[\hat{x}_i(k+1)] = \hat{f}^{(i)}(\cdot)\), \(i \in {\mathcal W}\) em (5) pode ser substituído por

\[\hat{x}_i(k+1) = \hat{x}_i(k) = \hat{x}_i^0, i \in {\mathcal W},\]

onde o valor inicial \(\hat{x}_i^0 \in \{ 0,1 \}^{| {\mathcal W} |}\) pode ser dado arbitrariamente.

Neste artigo, um vértice incluído em \({\mathcal W}\) é chamado de nó de controle. Esta suposição implica que os valores binários nos nós de controle são considerados entradas de controle constantes. Em outras palavras, encontrar um conjunto mínimo de vértices de feedback de um grafo de interação implica selecionar entradas de controle constantes. Utilizando a representação simplificada (5), o valor das entradas de controle constantes pode ser facilmente determinado.

Apresentamos um exemplo simples.

6 exemplo: Considere novamente o PBN do Exemplo 1. Na Suposição 1, sua representação simplificada é dada por (6), (7) e \(\hat{x}_3(k+1) = \hat{x}_3(k) = \hat{x}_3^0 \in \{ 0,1 \}\). No caso de \(\hat{x}_3^0=0\), podemos obter \(E[\hat{x}_1(k+1)]=E[\hat{x}_2(k+1)]=0.2\). No caso de \(\hat{x}_3^0=1\), podemos obter \(E[\hat{x}_1(k+1)]=0.8\) e \(E[\hat{x}_2(k+1)]=0\). As Figuras 4 e 5 mostram os resultados da simulação utilizando o PBN do Exemplo 1, onde o estado inicial é dado por \(x_1(0)=x_2(0)=1\), e a simulação foi repetida 10000 vezes. A partir dessas figuras, vemos que a representação simplificada expressa o comportamento ao longo do tempo. Além disso, no caso de \(\hat{x}_3^0=1\), garantimos que \(x_2(k)=0\), \(k \geq 1\) mantém com a probabilidade \(1\). Podemos confirmar este fato tanto pela representação simplificada quanto pelo resultado da simulação. \(\tag*{◻}\)

FIG. 4  Resposta temporal da média de 10000 amostras para o PBN no Exemplo 1, onde \(x_3(k)=0\). Linha sólida: \(x_1\). Linha quebrada: \(x_2\).

FIG. 5  Resposta temporal da média de 10000 amostras para o PBN no Exemplo 1, onde \(x_3(k)=1\). Linha sólida: \(x_1\). Linha quebrada: \(x_2\).

Na análise de estabilidade e estabilização de PBNs, um método de produto semitensor (STP) é bem conhecido como um dos métodos típicos (ver, por exemplo, [5]). No método STP, um PBN com \(n\) nós e \(m\) nós de controle é representado por uma matriz com o tamanho de \(2^n \times 2^{n+m}\). Conseqüentemente, os cálculos sobre análise de estabilidade e estabilização podem ser difíceis para PBNs de grande escala.

A representação simplificada proposta pode expressar o comportamento utilizando menos variáveis, podendo ser utilizada em análises de estabilidade e estabilização de PBNs. Um PBN é complexo e pode acontecer que a entrada de controle não seja fornecida explicitamente. Nesses casos, a representação simplificada nos fornece informações úteis sobre a seleção de insumos. Se a estabilização não puder ser realizada sob a Suposição 1, então os nós que não convergem para a origem deverão ser controlados diretamente.

O valor que \(\hat{x}_i^0\) de entradas de controle constantes, tais que um determinado PBN satisfaça uma determinada especificação, pode ser facilmente calculado usando, por exemplo, MATLAB e Mathematica.

6. Exemplo Biológico

Nesta seção, apresentamos um exemplo biológico. Considere o modelo BN de uma via de sinalização de neurotransmissores [17]. Este modelo expressa uma via de interação entre os receptores glutamatérgicos e dopaminérgicos. O modelo BN deste sistema é dado por

\[\begin{aligned} x_1(k+1) &= x_1(k), \\ x_2(k+1) &= x_1(k) \wedge \neg x_3(k), \\ x_3(k+1) &= x_2(k), \\ x_4(k+1) &= x_2(k), \\ x_5(k+1) &= x_2(k), \\ x_6(k+1) &= x_4(k) \wedge \neg x_5(k), \\ x_7(k+1) &= x_6(k), \\ x_8(k+1) &= x_5(k), \\ x_9(k+1) &= x_8(k) \vee x_{14}(k), \\ x_{10}(k+1) &= x_9(k), \\ x_{11}(k+1) &= x_7(k) \wedge \neg x_{10}(k), \\ x_{12}(k+1) &= \neg x_{11}(k), \\ x_{13}(k+1) &= x_{13}(k), \\ x_{14}(k+1) &= x_7(k) \wedge \neg x_{12}(k) \wedge x_{13}(k), \\ x_{15}(k+1) &= x_{14}(k), \\ x_{16}(k+1) &= x_{15}(k). \end{aligned}\]

O gráfico de interação é dado pela Fig. 6. Aqui, para adicionar comportamento probabilístico, a dinâmica de \(x_6\) é artificialmente alterado para

\[x_6(k+1) = \begin{cases} x_4(k) \wedge \neg x_5(k), \mbox{Prob. 0.7,} \\ x_4(k), \mbox{Prob. 0.3.} \end{cases}\]

FIG. 6  Gráfico de interação do modelo de rede booleana de uma via de sinalização de neurotransmissor [17].

Considere derivar a representação simplificada. Um dos conjuntos mínimos de vértices de feedback é dado por \({\mathcal W} = \{ 1,2,10,13 \}\). Então, sob a Suposição 1, podemos obter a seguinte representação simplificada:

\[\begin{aligned} \hat{x}_1(k+1) &= \hat{x}_1(k), \\ \hat{x}_2(k+1) &= \hat{x}_2(k), \\ \hat{x}_3(k+1) &= \hat{x}_2(k), \\ \hat{x}_4(k+1) &= \hat{x}_2(k), \\ \hat{x}_5(k+1) &= \hat{x}_2(k), \\ E[\hat{x}_6(k+1)] &= 0.3 \hat{x}_2(k), \\ E[\hat{x}_7(k+1)] &= 0.3 \hat{x}_2(k), \\ \hat{x}_8(k+1) &= \hat{x}_2(k), \\ \hat{x}_9(k+1) &= \hat{x}_2(k), \\ \hat{x}_{10}(k+1) &= \hat{x}_{10}(k), \\ E[\hat{x}_{11}(k+1)] &= 0.3 \hat{x}_2(k) - 0.3 \hat{x}_2(k) \hat{x}_{10}(k), \\ E[\hat{x}_{12}(k+1)] &= 1 - 0.3 \hat{x}_2(k) + 0.3 \hat{x}_2(k) \hat{x}_{10}(k), \\ \hat{x}_{13}(k+1) &= \hat{x}_{13}(k), \\ E[\hat{x}_{14}(k+1)] &= 0.09 \hat{x}_2(k) \hat{x}_{13}(k), \\ & \ \ \ \ - 0.09 \hat{x}_2(k) \hat{x}_{10}(k) \hat{x}_{13}(k), \\ \hat{x}_{15}(k+1) &= \hat{x}_2(k), \\ \hat{x}_{16}(k+1) &= \hat{x}_2(k). \end{aligned}\]

Observamos que a dinâmica de alguns nós, exceto os nós em \({\mathcal W}\) são determinísticos. A partir desta representação, podem ser obtidos os dois fatos a seguir para o sistema original.

  1. Pela configuração \(x_1(0)=x_2(0)=x_{10}(0)=x_{13}(0)=0\), \(x_i\), \(i \neq 12\) convergir para \(0\), se apenas \(x_{12}\) converge para \(1\).
  2. Se é desejável que \(x_{12}\) converge para um valor menor, então devemos definir \(x_2(0)=1\) e \(x_{10}(0)=0\).

Validamos esses fatos por meio de uma simulação numérica. Consideramos os dois casos a seguir.

  • Caso 1:  \(x_i(0)=0\), \(i \in \{ 1,2,10,13 \}\) e \(x_j(0)=1\), \(j \neq i\).
  • Caso 2:  \(x_{10}(0)=0\) e \(x_j(0)=1\), \(j \neq 10\).

A Figura 7 mostra o resultado da simulação no Caso 1. A partir desta figura, vemos que \(x_{i}\), \(i \neq 12\) convergir para \(0\) e \(x_{12}\) converge para \(1\). Ou seja, para estabilizar este sistema na origem, \(x_{12}\) também deve ser controlado diretamente. De cada amostra, vemos também que todos \(x_i\) convergem para qualquer um \(0\) or \(1\) com a probabilidade \(1\). A Figura 8 mostra o resultado da simulação no Caso 2. A partir desta figura, vemos que a média de \(x_{12}\) converge para \(0.7\). Este fato também pode ser obtido a partir da representação simplificada. Assim, utilizando a representação simplificada, podemos obter informações úteis para controlar o comportamento de longo prazo de um determinado PBN.

FIG. 7  Resposta temporal da média de 10000 amostras para o PBN na Seção. 6 (Caso 1). Linha verde: \(x_{12}\).

FIG. 8  Resposta temporal da média de 10000 amostras para o PBN na Seção. 6 (Caso 2). Linha verde: \(x_{12}\).

7. Conclusão

Neste artigo, propusemos uma representação simplificada baseada no valor estacionário do valor esperado do estado. Na representação simplificada proposta, o comportamento de um determinado PBN é caracterizado por alguns nós determinados por um conjunto mínimo de vértices de realimentação de um grafo de interação. Em simulações numéricas, utilizamos o modelo BN de uma via de sinalização de neurotransmissores. Através de simulações numéricas, esclarecemos que a representação simplificada com quatro nós pode ser obtida a partir do PBN com dezesseis nós. Além disso, a representação obtida foi aplicada ao problema de seleção de insumos. Pelo método proposto, o comportamento de sistemas de redes complexos pode ser representado por um modelo matemático com menor número de nós. Portanto, espera-se que possamos considerar os problemas de análise/controle para sistemas de grande escala, cujo manejo tem sido difícil.

A seleção de entrada foi discutida com base no uso apenas de uma entrada de controle constante. Em sistemas de rede complexos, tais como redes reguladoras de genes, tal entrada é frequentemente eficaz, porque há casos em que a comutação frequente de um valor binário da entrada de controlo é difícil. Por outro lado, para melhorar o comportamento, há um caso em que é importante mudar um valor binário da entrada de controle dependendo do estado. Um dos esforços futuros é desenvolver um método de derivação de controladores de feedback de estado baseado no método proposto.

Agradecimentos

Este trabalho foi parcialmente apoiado pelos números de concessão JSPS KAKENHI JP21H04558, JP22K04163, JP23H01430.

Referências

[1] S.A. Kauffman, “Metabolic stability and epigenesis in randomly constructed genetic nets,” Journal of Theoretical Biology, vol.22, pp.437-467, 1969.
CrossRef

[2] I. Shmulevich, E.R. Dougherty, S. Kim, and W. Zhang, “Probabilistic Boolean networks: A rule-based uncertainty model for gene regulatory networks,” Bioinformatics, vol.18, no.2, pp.261-274, 2002.
CrossRef

[3] K. Kobayashi and K. Hiraishi, “An integer programming approach to optimal control problems in context-sensitive probabilistic Boolean networks,” Automatica, vol.47, no.6, pp.1260-1264, 2011.
CrossRef

[4] K. Kobayashi and K. Hiraishi, “Optimal control of probabilistic Boolean networks using polynomial optimization,” IEICE Trans. Fundamentals, vol.E95-A, no.9, pp.1512-1517, Sept. 2012.
CrossRef

[5] R. Li, M. Yang, and T. Chu, “State feedback stabilization for probabilistic Boolean networks,” Automatica, vol.50, no.4, pp.1272-1278, 2014.
CrossRef

[6] H. Li, Y. Wang, and P. Guo, “State feedback based output tracking control of probabilistic Boolean networks,” Information Sciences, vols.349-380, pp.1-11, 2016.
CrossRef

[7] R. Pal, A. Datta, M.L. Bittner, and E.R. Dougherty, “Intervention in context-sensitive probabilistic Boolean networks,” Bioinformatics, vol.21, pp.1211-1218, 2005.
CrossRef

[8] R. Pal, A. Datta, M.L. Bittner, and E.R. Dougherty, “Optimal infinite-horizon control for probabilistic Boolean networks,” IEEE Trans. Signal Process., vol.54, no.6, pp.2375-2387, 2006.
CrossRef

[9] I. Shmulevich and E.R. Dougherty, Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks, Society for Industrial and Applied Mathematics, 2010.
CrossRef

[10] P. Trairatphisan, A. Mizera, J. Pang, A.A. Tantar, J. Schneider, and T. Sauter, “Recent development and biomedical applications of probabilistic Boolean networks,” Cell Commun. Signal., vol.11, no.46, 25 pages, 2013.
CrossRef

[11] S. Zhu, J. Lu, Y. Liu, T. Huang, and J. Kurths, “Output tracking of probabilistic Boolean networks by output feedback control,” Information Sciences, vol.483, pp.96-105, 2019.
CrossRef

[12] A. Veliz-Cuba, “Reduction of Boolean network models,” Journal of Theoretical Biology, vol.289, pp.167-172, 2011.
CrossRef

[13] K. Kobayashi, “Design of fixed points in Boolean networks using feedback vertex sets and model reduction,” Complexity, vol.2019, article ID 9261793, 9 pages, 2019.
CrossRef

[14] T. Akutsu, S. Kuhara, O. Maruyama, and S. Miyano, “A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions,” Genome Informatics, vol.9, pp.151-160, 1998.
CrossRef

[15] B. Fiedler, A. Mochizuki, G. Kurosawa, and D. Saito, “Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks,” J. Dyn. Diff. Equat., vol.25, no.3, pp.563-604, 2013.
CrossRef

[16] A. Mochizuki, B. Fiedler, G. Kurosawa, and D. Saito, “Dynamics and control at feedback vertex sets. II: A faithful monitor to determine the diversity of molecular activities in regulatory networks,” Journal of Theoretical Biology, vol.335, pp.130-146, 2013.
CrossRef

[17] S. Gupta, S.S. Bisht, R. Kukreti, S. Jain, and S.K. Brahmachari, “Boolean network analysis of a neurotransmitter signaling pathway,” Journal of Theoretical Biology, vol.244, pp.469-469, 2007.
CrossRef

[18] G. Even, J. Naor, B. Schieber, and M. Suden, “Approximating minimum feedback sets and multicuts in directed graphs,” Algorithmica, vol.20, no.2, pp.151-174, 1998.
CrossRef

[19] R.M. Karp, “Reducibility among combinatorial problems,” Proc Symp. on Complexity of Computer Computations, pp.85-103, 1972.
CrossRef

[20] L. Tournier and M. Chaves, “Uncovering operational interactions in genetic networks using asynchronous Boolean dynamics,” Journal of Theoretical Biology, vol.260, no.2, pp.196-209, 2009.
CrossRef

[21] H.P. Williams, Model Building in Mathematical Programming, 5th ed., Wiley, 2013.

autores

Koichi KOBAYASHI
  Hokkaido University

received the B.E. degree in 1998 and the M.E. degree in 2000 from Hosei University, and the D.E. degree in 2007 from Tokyo Institute of Technology. From 2000 to 2004, he worked at Nippon Steel Corporation. From 2007 to 2015, he was an Assistant Professor at Japan Advanced Institute of Science and Technology. From 2015 to 2022, he was an Associate Professor at Hokkaido University. Since 2023, he has been a Professor at the Faculty of Information Science and Technology, Hokkaido University. His research interests include discrete event and hybrid systems. He is a member of IEEE, IEEJ, IEICE, ISCIE, and SICE.

Palavra-chave