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 BDD-Based Approach to Finite-Time Control of Boolean Networks
Abra o Access
Uma abordagem baseada em BDD para controle em tempo finito de redes booleanas

Fuma MOTOYAMA, Koichi KOBAYASHI, Yuh YAMASHITA

  • Exibições de texto completo

    209

  • Cite isto
  • Free PDF (1.4MB)

Resumo:

O controle de redes complexas, como redes reguladoras de genes, é um dos problemas fundamentais da teoria do controle. Uma rede booleana (BN) é um dos modelos matemáticos em redes complexas e representa o comportamento dinâmico por funções booleanas. Neste artigo, um método de solução para o problema de controle em tempo finito de BNs é proposto usando um BDD (diagrama de decisão binário). Neste problema, encontramos todas as combinações do estado inicial e da sequência de entrada de controle tais que uma determinada especificação de controle seja satisfeita. O uso de BDDs nos permite resolver este problema para BNs de tal forma que o método convencional não pode ser aplicado. Primeiramente, depois de explicado o esboço dos BNs e BDDs, é apresentado o problema estudado neste artigo. A seguir, é proposto um método de solução utilizando BDDs. Finalmente, é apresentado um exemplo numérico em um BN de 67 nós.

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

1. Introdução

Uma rede booleana (BN) é bem conhecida como um dos modelos matemáticos em redes complexas, como redes reguladoras de genes. Em um BN, o estado e a entrada de controle assumem um valor binário, e a evolução temporal do estado é representada por um conjunto de funções booleanas. Há um ponto fraco de que um BN é muito simples, mas um BN é amplamente utilizado como o primeiro passo no desenvolvimento da teoria de controle de redes complexas. Muitos resultados fundamentais foram obtidos, como estabilidade [1], [2], estabilização [3], [4], controlabilidade [5]-[7], observabilidade [5], [8], [9], e controle ideal [10]-[12]. Para modelar um comportamento mais complexo, uma rede booleana probabilística (PBN) [13] e uma PBN sensível ao contexto [14] foram propostas como um modelo estendido de BNs. Também para estes modelos estendidos, resultados fundamentais [15]-[18] foram obtidos.

Na última década, o método do produto semitensor (STP) tem sido amplamente utilizado na análise e controle de BNs (ver, por exemplo, [5] e [19]). Usando o método STP, um determinado BN é transformado de forma equivalente em uma representação algébrica linear. Conseqüentemente, problemas de análise/controle podem ser resolvidos de forma algébrica. No entanto, o método STP tem um ponto fraco. Para um BN com \(n\) nós e \(m\) entradas de controle, matrizes do tamanho \(2^n \times 2^{n+m}\) deve ser manuseado. A partir deste fato, BNs tais que o método STP possa ser aplicado são limitados.

Um solucionador BDD (diagrama de decisão binário) e SAT (satisfatibilidade)/SMT (teorias do módulo de satisfatibilidade) são bem conhecidos como ferramentas eficientes para lidar com funções booleanas. Um BDD é uma estrutura de dados usada para representar funções booleanas [20]. Foi proposto um algoritmo eficiente para realizar operações lógicas (AND, OR, XOR e assim por diante) em BDDs. Um BDD trabalha com eficiência na análise de BNs, como detecção de atratores [21], [22]. Os solucionadores SAT/SMT determinam se uma determinada função booleana é satisfatória ou não. O solucionador Yices SMT (https://yices.csl.sri.com/), o provador de teorema Z3 (https://github.com/Z3Prover) e assim por diante foram desenvolvidos. Solucionadores SAT/SMT têm sido usados ​​para detecção de atratores [23] e projeto de BN baseado em atratores [24]. Até onde sabemos, os solucionadores BDDs e SAT/SMT não foram aplicados ao problema de controle de BNs.

Neste artigo, utilizando BDDs, propomos um método de solução para o problema de controle de tempo finito de BNs. O problema de controle em tempo finito é encontrar uma sequência de entrada de controle tal que o estado em um determinado tempo final seja igual ao valor alvo sob um determinado estado inicial. Este problema é um dos problemas de controle típicos em BNs [25]. Utilizando o método STP, este problema foi estudado assim como o problema de controlabilidade. No entanto, uma classe de BNs é limitada pelo motivo acima. Além disso, em [25], foi provado que o problema de controle em tempo finito para um BN geral é NP-difícil. Nesses casos, é importante utilizar ferramentas de computação eficientes, como BDDs e solucionadores SAT/SMT. Como as funções booleanas são simplificadas pelo uso de BDDs, é apropriado usar BDDs para este problema. Neste artigo, usando BDDs, consideramos encontrar todas as combinações do estado inicial e da sequência de entrada do controle tais que uma determinada especificação de controle seja satisfeita (isto é, o estado inicial não é fornecido antecipadamente). Portanto, o problema estudado neste artigo é um problema mais geral, incluindo o problema em [25] como um caso especial.

Este artigo está organizado da seguinte forma. Na seita. 2, BNs e BDDs são resumidos. Na seita. 3, o problema aqui estudado está formulado. Na seita. 4, é proposto um método de solução utilizando BDDs. Um exemplo simples também é apresentado para demonstrar o método proposto. Na seita. 5, o método proposto é aplicado a um BN de 67 nós. O método STP não pode ser aplicado a tais BNs. Comparamos o tempo de cálculo usando BDDs com aquele usando o Z3 Theorem Prover. Na seita. 6, concluímos este artigo e abordamos esforços futuros.

Notação: Deixei \(\{ 0,1 \}^{n}\) denotar o conjunto de \(n\)vetores -dimensionais, que consistem em elementos \(0\) e \(1\). Deixei \(0_n\) (\(1_n\)) denotam o \(n\)vetor -dimensional cujos elementos são todos \(0\) (\(1\)).

2. Preliminares

2.1 Redes Booleanas

Um BN consiste em um conjunto de \(n\) nós \(V=\{ x_1, x_2, \dots, x_n \}\) e um conjunto de \(n\) funções booleanas \(F_a=\{ f_1^a, f_2^a, \dots, f_n^a \}\). No caso de redes reguladoras de genes, \(V\) e \(F_a\) correspondem a um conjunto de genes e a um conjunto de regras reguladoras de genes, respectivamente. Para o \(i\)-ésimo nó, uma variável booleana \(x_i \in \{ 0,1 \}\) (por exemplo, nível de expressão do gene) e uma função booleana \(f_i^a\) estão associados. Cada função booleana é dada com base nas interações entre nós (ou seja, a estrutura da rede), onde operadores lógicos como AND lógico \(( \land )\), OU lógico \(( \lor )\), e lógico NÃO \(( \lnot )\) são usados. Então, podemos obter a seguinte expressão:

\[\begin{equation*} \left\{ \begin{array}{l} x_1(t+1) = f_1^a ( x(t) ), \\ x_2(t+1) = f_2^a ( x(t) ), \\ \vdots \\ x_n(t+1) = f_n^a ( x(t) ), \end{array} \right. \tag{1} \end{equation*}\]

onde \(x = [ x_1, x_2, \dots, x_n ] \in {\{ 0,1 \} }^n\) é o estado, e \(t = 0,1,2,\dots\)é o tempo discreto.

1 exemplo: Considere o seguinte modelo BN para uma rede de apoptose simplificada [26]:

\[\left\{ \begin{array}{l} x_1(t+1) = x_1(t), \\ x_2(t+1) = x_1(t) \wedge \neg x_3(t), \\ x_3(t+1) = \neg x_2(t) \wedge x_4(t), \\ x_4(t+1) = x_1(t) \vee x_3(t), \end{array} \right. \]

onde \(x_1\) é o nível de concentração (alto ou baixo) do fator de necrose tumoral (TNF, um estímulo), \(x_2\) é o nível de concentração do inibidor de proteínas de apoptose (IAP), \(x_3\) é o nível de concentração da caspase 3 ativa (C3a), e \(x_4\) é o nível de concentração da caspase 8 ativa (C8a). Se \(x(t) = [1,1,0,0]\), na próxima vez que o estado for \(x(t+1) = [1,1,0,1]\). Veja, por exemplo, [27] para modelos mais complicados de uma rede de apoptose. \(\tag*{◻}\)

2.2 Diagramas de Decisão Binária

Um BDD é uma estrutura de dados que representa eficientemente uma função booleana. Um BDD consiste em dois nós terminais rotulados com 0 e 1 e nós rotulados com nomes de variáveis. Cada nó, exceto os nós terminais, possui dois nós filhos, e um nó filho é escolhido de acordo com o valor do nó (pai). Quando o nó terminal é alcançado continuando a escolher os nós filhos de acordo com cada valor do nó, o valor do nó terminal é a saída da função. Sabe-se que um BDD é determinado exclusivamente a partir de uma função booleana quando a ordem das variáveis ​​no gráfico é fixa.

A operação Apply foi proposta como um algoritmo útil para lidar com equações lógicas em BDDs [20]. As operações Apply podem executar operadores lógicos (AND, OR, XOR, etc.) entre BDDs. O tempo de cálculo da operação Apply é aproximadamente proporcional à quantidade total de dados de entrada e saída. A Figura 1 mostra o procedimento para gerar a expressão lógica \(a \land b \lor \lnot c\) pela operação Aplicar.

FIG. 1  O procedimento para gerar a expressão lógica \(a \land b \lor \lnot c\) pela operação Aplicar.

3. Formulação do Problema

Considere o seguinte BN que é adicionado à entrada de controle do BN (1):

\[\begin{equation*} \left\{ \begin{array}{l} x_1(t+1) = f_1 ( x(t), u(t) ), \\ x_2(t+1) = f_2 ( x(t), u(t) ), \\ \vdots \\ x_n(t+1) = f_n ( x(t), u(t) ), \end{array} \right. \tag{2} \end{equation*}\]

onde \(u = [ u_1, u_2, \dots, u_m ] \in {\{ 0,1 \} }^m\) é a entrada de controle e \(f_i\) é uma determinada função booleana. Assumimos que para cada elemento da entrada de controle, qualquer valor binário pode ser definido a cada tempo discreto. Considere o seguinte problema de controle em tempo finito para o BN (2).

Problema 1: Suponha que para o BN (2), o estado alvo \(x^* \in \{0,1\}^n\) e a última vez \(T\) são dados.

  1. Encontre todos os estados iniciais tais que \(x(T) = x^* = [ x^*_1, x^*_2, \dots, x^*_n ]\) segura. Deixar \({\mathcal X}_0 \subseteq \{ 0,1 \}^n\) denota o conjunto de estado inicial obtido.
  2. Para cada \(x_0 \in {\mathcal X}_0\), encontre uma sequência de entrada de controle \(U = [u(0), u(1), \ldots, u(T-1)]\).

No caso em que o estado inicial é dado, este problema é um dos problemas de controle típicos para BNs, e foi estudado em [25].

4. Método de solução proposto

Nesta seção, propomos um método de solução para o Problema 1. Primeiro, são explicados detalhes do método de solução proposto. A seguir, o método de solução proposto é demonstrado através de um exemplo simples.

4.1 Método de solução usando BDDs

Considere resolver o Problema 1 usando BDDs.

Primeiro, definindo \(f := [f_1, f_2, \dots, f_n]\), o estado final \(x(T)\) pode ser representado por

\[\begin{aligned} x(T) &= f( f( \cdots f( f(x(0),u(0)), u(1)), \dots ), u(T-1) )\\ &=: f^{(T)}(x(0),U), \end{aligned}\]

onde a função booleana \(f^{(T)}: \{ 0,1 \}^n \times \{ 0,1 \}^{Tm}\) pode ser calculado a partir de \(f\). Além disso, \(f^{(T)}\) é representado como \(f^{(T)} = [ f^{(T)}_1, f^{(T)}_2, \dots, f^{(T)}_n ]\). Então, o Problema 1 pode ser reescrito como o seguinte problema.

Problema 2: Encontre todas as combinações do par do estado inicial \(x(0)\) e a sequência de entrada de controle \(U\) tal que a seguinte fórmula lógica \(F(x(0),U)\) é igual a \(1\) (verdadeiro):

\[\begin{align} F(x(0),U) := & \ (f^{(T)}_1(x(0),U) \leftrightarrow x^*_1)\nonumber\\ & \ \land (f^{(T)}_2(x(0),U) \leftrightarrow x^*_2)\nonumber\\ & \ \land \cdots \land (f^{(T)}_n(x(0),U) \leftrightarrow x^*_n), \tag{3} \end{align}\]

Onde "\(\leftrightarrow\)”representa o operador de equivalência lógica.

Para resolver esse problema, \(F(x(0),U)\) é representado por um único BDD. Então, uma solução para este problema pode ser facilmente derivada do BDD obtido.

Por fim, resumimos o procedimento proposto para resolução do Problema 2, que pode ser implementado em BDDs.

Procedimento de resolução do Problema 2:

- Derive um BDD representando a função booleana \(f_i^{(T)}(x(0),U)\), \(i=1,2,\dots,n\) substituindo recursivamente funções booleanas por outras.

- Derive um BDD representando \(F(x(0),U)\) de (3).

- Encontre todas as combinações de \(x(0)\) e \(U\) de tal modo que \(F(x(0),U) = 1\).

Como o Problema 2 é chamado de problema AllSAT (satisfatibilidade de todas as soluções), ele pode ser resolvido usando um solucionador SAT/SMT (Teorias do Módulo de Satisfiabilidade). Porém, utilizando BDD, podemos obter uma representação compacta, que será útil na análise e controle de BNs1.

4.2 Exemplo

Apresentamos um exemplo simples para explicar o procedimento proposto para resolução do Problema 2. Embora o procedimento proposto possa ser implementado em BDDs, explicamos aqui o procedimento utilizando fórmulas lógicas.

Considere o seguinte BN com três nós e uma única entrada de controle:

\[\begin{align} \left\{ \begin{array}{l} x_1(t+1) = (x_1(t) \land x_3(t) \land u_1(t)) \lor x_2(t), \\ x_2(t+1) = x_3(t) \lor u_1(t), \\ x_3(t+1) = \lnot x_1(t). \end{array} \right. \tag{4} \end{align}\]

Suponha que o estado alvo \(x^*\) e a última vez \(T\) são dados por \(x^* = [1,1,0]\) e \(T=2\), respectivamente. Considere encontrar todas as combinações dos estados iniciais e das sequências de controle tais que \(x(2) = [1,1,0]\) detém.

Na Etapa 1, a função booleana \(f^{(2)}_i\) pode ser derivado da seguinte forma. De \(x_1(2) = (x_1(1) \land x_3(1) \land u_1(1)) \lor x_2(1)\) e (4), podemos obter

\[f^{(2)}_1 =(\lnot x_1(0) \land x_2(0) \land u_1(1)) \lor x_3(0) \lor u_1(0).\]

De maneira semelhante, a partir \(x_2(2) = x_3(1) \lor u_1(1)\), \(x_3(2) = \lnot x_1(1)\)e (4), as funções booleanas \(f^{(2)}_2\) e \(f^{(2)}_3\) pode ser obtido como

\[\begin{aligned} f^{(2)}_2 =& \ \lnot x_1(0) \lor u_1(1), \\ f^{(2)}_3 =& \ \lnot (x_1(0) \land x_3(0) \land u_1(0)) \land \lnot x_2(0), \end{aligned}\]

respectivamente.

Na Etapa 2, a função booleana \(F(x(0),U)\) é obtido da seguinte forma:

\[\begin{aligned} F(x(0),U) =& \ ( f^{(2)}_1 \leftrightarrow x_1^* ) \land ( f^{(2)}_2 \leftrightarrow x_2^* ) \land ( f^{(2)}_3 \leftrightarrow x_3^* ) \\ =& \ \{ (\lnot x_1(0) \land x_2(0) \land u_1(1)) \lor x_3(0) \lor u_1(0) \} \\ & \ \land (\lnot x_1(0) \lor u_1(1)) \\ & \ \land \lnot \{ \lnot (x_1(0) \land x_3(0) \land u_1(0)) \land \lnot x_2(0) \} \\ =& \ (x_1(0) \land x_3(0) \land u_1(0) \land u_1(1)) \\ & \ \lor (\lnot x_1(0) \land x_2(0) \land x_3(0)) \\ & \ \lor (\lnot x_1(0) \land x_2(0) \land u_1(0)) \\ & \ \lor (\lnot x_1(0) \land x_2(0) \land u_1(1)) \\ & \ \lor (x_2(0) \land x_3(0) \land u_1(1)) \\ & \ \lor (x_2(0) \land u_1(0) \land u_1(1)). \end{aligned}\]

O BDD representando \(F(x(0),U)\) é mostrado na Figura 2.

FIG. 2  BDD de \(F(x(0),U)\) no exemplo da Seção. 4.2. Os nós x_1(0), x_2(0) e x_3(0) correspondem a \(x_1(0)\), \(x_2(0)\) e \(x_3(0)\), respectivamente. Os nós u_1(0) e u_1(1) correspondem a \(u_1(0)\) e \(u_1(1)\), Respectivamente.

Na Etapa 3, todas as combinações do estado inicial e da sequência de controle que satisfazem \(F(x(0),U) = 1\) são encontrados na Fig. 2. Neste gráfico, as combinações de nós que alcançam o nó terminal \(1\) satisfaz \(F(x(0),U) = 1\). A partir da observação deste gráfico, as combinações são obtidas como

\[\begin{aligned} & [x_1(0),x_2(0),x_3(0),u_1(0),u_1(1)] \\ &= [0,1,0,0,1],[0,1,0,1,*],[0,1,1,*,*],\\ &\hphantom{=\ } [1,0,1,1,1],[1,1,0,1,1],[1,1,1,*,1], \end{aligned}\]

Onde "\(*\)”Significa que o valor pode ser dado por qualquer valor binário. Por exemplo, \([0,1,1,*,*]\) significa que quando \(x_0 = [0,1,1]\), a sequência de entrada de controle pode assumir qualquer valor binário (ou seja, \([0,0],[0,1],[1,0],[1,1]\)). Portanto, vemos que existem 11 combinações. Assim, podemos derivar a solução do Problema 1.

5. Exemplo Numérico

Nesta seção, para demonstrar o método proposto, apresentamos um exemplo numérico de uma BN tal que o método STP não pode ser aplicado.

Considere um modelo BN de 67 nós e 5 entradas de uma rede apoptótica [29]. As interações entre os nós são mostradas na Figura 3, onde os nós de entrada correspondem a elementos da entrada de controle. Suponha que o estado alvo \(x^* \in \{0,1\}^{67}\) é dado como o seguinte vetor binário:

\[x^* = \left[ 0_{16}, 1, 0_{16}, 1, 0_{3}, 1_{10}, 0, 1, 0_{7}, 1_{3}, 0_{7}, 1 \right].\]

Consideramos os casos de \(T = 1,2,\dots,15\). Ressaltamos aqui que o método STP, frequentemente utilizado na análise e controle de BNs, não pode ser aplicado a tais BNs. Isso ocorre porque no método STP, matrizes com \(2^{67} \times 2^{67+5}\) geralmente devem ser manipulados, e o manuseio de tais matrizes é difícil em um computador convencional. Veja, por exemplo, [5] e [19] para detalhes do método STP. Neste exemplo numérico, comparamos o tempo de cálculo do procedimento proposto com o do solucionador SMT.

FIG. 3  Gráfico representando as interações entre nós, onde os nós de entrada correspondem a elementos da entrada de controle.

Apresentamos o resultado do cálculo. A Tabela 1 mostra o número de combinações de \(x(0)\) e \(U\), o tempo de cálculo do procedimento proposto, e o do solucionador SMT, onde usamos Python 3.9.7 no computador (CPU: Processador AMD Ryzen 5 5600X 6-Core 3.70 GHz, Memória: 32.0 GB, SO: Windows 11) . Também usamos o z3-solver 4.12.2.0 como solucionador SMT. Definimos o tempo limite para 10000 segundos. Na Tabela 1, vemos que o tempo de cálculo do procedimento proposto é mais rápido que o do solucionador SMT.

Mesa. 1  O resultado do cálculo e o tempo de cálculo para cada \(T\).

Apresentamos uma amostra de combinações no caso de \(T=10\). Como uma das combinações, podemos obter o seguinte estado inicial e sequência de entrada de controle:

\[\begin{align} x(0) =& \left[ 0_{5}, 1, 0_{10}, 1, 0_{3}, 1, 0_{12}, 1, 0_{3}, 1_{3}, 0, 1, 0_{2}, 1_{2}, \right. \nonumber \\ & \left. 0_{3}, 1_{3}, 0_{3}, 1_{5}, 0_{2}, 1, 0_{3}, 1 \right], \tag{5} \\ u(0) =& \left[ 1, 0, 0, 0, 1 \right], \nonumber \\ u(1) =& u(2) = \left[ 1, 0, 0, 0, 0 \right], \nonumber \\ u(3) =& \left[ 0, 0, 0, 0, 0 \right], \nonumber \\ u(4) =& \left[ 0, 0, 0, 0, 1 \right], \nonumber \\ u(5) =& \left[ 0, 0, 0, 0, 0 \right], \nonumber \\ u(6) =& \left[ 1, 0, 0, 0, 0 \right], \nonumber \\ u(7) =& \left[ 0, 0, 0, 0, 0 \right], \nonumber \\ u(8) =& \left[ 1, 0, 0, 0, 0 \right], \nonumber \\ u(9) =& \left[ 0, 0, 0, 0, 0 \right], \nonumber \end{align}\]

Em vez da resposta temporal do estado, apresentamos a distância de Hamming definida por \(\sum_{i=1}^{67} | x_i(k)-x^*_i(k) |\). A Figura 4 mostra a distância de Hamming em cada tempo. A partir desta figura, vemos que \(x(T)=x^*\) detém.

FIG. 4  Resposta temporal da distância de Hamming.

Finalmente, discutimos ainda o caso em que o estado inicial é dado por (5). Neste caso, existem outras sequências de entrada de controle tais que \(x(T)=x^*\) segura. Todas as sequências de entrada de controle tais que \(x(T)=x^*\) as posses podem ser caracterizadas da seguinte forma:

\[\begin{aligned} u(0) &= \left[ *, 0, 0, 0, 1 \right], \\ u(1) &= \left[ *, 0, 0, 0, * \right]. \\ u(2) &= \left[ 0, 0, 0, 0, 0 \right], \nonumber \\ u(3) &= \left[ *, 0, 0, 0, * \right], \nonumber \\ u(4) &= \left[ *, 0, 0, 0, 1 \right], \nonumber \\ u(5) &= u(6) = \left[ *, 0, 0, 0, 0 \right], \nonumber \\ u(7) &= \left[ *, 0, 0, 0, * \right], \nonumber \\ u(8) &= u(9) = \left[ *, 0, 0, 0, 0 \right]. \nonumber \end{aligned}\]

Portanto, existem muitos padrões da sequência de entrada de controle, tais que \(x(T)=x^*\) segura. Por exemplo, quando é desejável que a entrada de controle seja o melhor possível zero, podemos definir que \(u_5(0)\) e \(u_5(4)\) são iguais a \(1\), e outras entradas são zero. Assim, pelo método proposto, podemos obter informações úteis.

6. Conclusão

Neste artigo, baseado em BDDs, propusemos um método de solução para o problema de controle de tempo finito de BNs. Usando o método proposto, podemos obter todas as combinações do estado inicial e da sequência de entrada de controle, de modo que o estado no tempo final atinja o estado alvo. A eficácia do método proposto foi apresentada por um BN com 67 nós e 5 entradas.

Em trabalhos futuros, utilizando o BDD obtido pelo método proposto, consideraremos o desenvolvimento de um método para derivar tanto o estado inicial quanto a sequência de entrada de controle de modo que uma outra especificação de controle seja satisfeita. Além disso, como uma extensão do método proposto, também é significativo desenvolver um método de solução para o problema de controle ótimo utilizando BDDs.

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

Referências

[1] S. Azuma, T. Yoshida, and T. Sugie, “Structural monostability of activation-inhibition Boolean networks,” IEEE Trans. Control Netw. Syst., vol.4, no.2, pp.179-190, 2017.
CrossRef

[2] M. Meng, J. Lam, J.E. Feng, and K.C. Cheung, “Stability and stabilization of Boolean networks with stochastic delays,” IEEE Trans. Autom. Control, vol.64, no.2, pp.790-796, 2018.
CrossRef

[3] Y. Guo, P. Wang, W. Gui, and C. Yang, “Set stability and set stabilization of Boolean control networks based on invariant subsets,” Automatica, vol.61, pp.106-112, 2015.
CrossRef

[4] A. Yerudkar, C. Del Vecchio, and L. Glielmo, “Feedback stabilization control design for switched Boolean control networks,” Automatica, vol.116, p.108934, 2020.
CrossRef

[5] D. Cheng and H. Qi, “Controllability and observability of Boolean control networks,” Automatica, vol.45, no.7, pp.1659-1667, 2009.
CrossRef

[6] D. Laschov and M. Margaliot, “Controllability of Boolean control networks via the perron-frobenius theory,” Automatica, vol.48, no.6, pp.1218-1223, 2012.
CrossRef

[7] Q. Zhu, Y. Liu, J. Lu, and J. Cao, “Further results on the controllability of Boolean control networks,” IEEE Trans. Autom. Control, vol.64, no.1, pp.440-442, 2018.
CrossRef

[8] E. Fornasini and M.E. Valcher, “Observability, reconstructibility and state observers of Boolean control networks,” IEEE Trans. Autom. Control, vol.58, no.6, pp.1390-1401, 2013.
CrossRef

[9] Y. Yu, M. Meng, J.e. Feng, and G. Chen, “Observability criteria for Boolean networks,” IEEE Trans. Autom. Control, vol.67, no.11, pp.6248-6254, 2022.
CrossRef

[10] K. Kobayashi and K. Hiraishi, “Optimal control of gene regulatory networks with effectiveness of multiple drugs: A Boolean network approach,” BioMed research international, vol.2013, 2013.
CrossRef

[11] E. Fornasini and M.E. Valcher, “Optimal control of Boolean control networks,” IEEE Trans. Autom. Control, vol.59, no.5, pp.1258-1270, 2014.
CrossRef

[12] Y. Wu, X.M. Sun, X. Zhao, and T. Shen, “Optimal control of Boolean control networks with average cost: A policy iteration approach,” Automatica, vol.100, pp.378-387, 2019.
CrossRef

[13] 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

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

[15] F. Li and J. Sun, “Controllability of probabilistic Boolean control networks,” Automatica, vol.47, no.12, pp.2765-2771, 2011.
CrossRef

[16] 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

[17] M. Toyoda and Y. Wu, “Mayer-type optimal control of probabilistic Boolean control network with uncertain selection probabilities,” IEEE Trans. Cybern., vol.51, pp.3079-3092, 2021.
CrossRef

[18] A. Acernese, A. Yerudkar, L. Glielmo, and C. Del Vecchio, “Reinforcement learning approach to feedback stabilization problem of probabilistic Boolean control networks,” IEEE Control Syst. Lett., vol.5, no.1, pp.337-342, 2020.
CrossRef

[19] D. Cheng, H. Qi, and Z. Li, Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach, Springer, London, U.K., 2011.
CrossRef

[20] R.E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., vol.C-35, no.8, pp.677-691, 1986.
CrossRef

[21] G.V. Trinh, T. Akutsu, and K. Hiraishi, “An FVS-based approach to attractor detection in asynchronous random Boolean networks,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol.19, no.2, pp.806-818, 2022.
CrossRef

[22] Q. Yuan, H. Qu, J. Pang, and A. Mizera, “Improving BDD-based attractor detection for synchronous Boolean networks,” Sci. China Inf. Sci., vol.59, no.8, pp.1-16, 2016.
CrossRef

[23] T. Tamura and T. Akutsu, “Detecting a singleton attractor in a Boolean network utilizing SAT algorithms,” IEICE Trans Fundamentals, vol.E92-A, no.2, pp.493-501, Feb. 2009.
CrossRef

[24] K. Kobayashi and K. Hiraishi, “ILP/SMT-based method for design of Boolean networks based on singleton attractors,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol.11, no.6, pp.1253-1259, 2014.
CrossRef

[25] T. Akutsu, M. Hayashida, W.K. Ching, and M.K. Ng, “Control of Boolean networks: Hardness results and algorithms for tree structured networks,” Journal of Theoretical Biology, vol.244, no.4, pp.670-679, 2007.
CrossRef

[26] M. Chaves, “Methods for qualitative analysis of genetic networks,” 2009 European Control Conference, pp.671-676, 2009.
CrossRef

[27] 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

[28] M. Jonáš and J. Strejček, “Q3B: An efficient BDD-based SMT solver for quantified bit-vectors,” International Conference on Computer Aided Verification, pp.64-73, Springer, 2019.
CrossRef

[29] P. Dutta, L. Ma, Y. Ali, P. Sloot, and J. Zheng, “Boolean network modeling of β-cell apoptosis and insulin resistance in type 2 diabetes mellitus,” BMC Syst. Biol., vol.13, no.2, pp.1-12, 2019.
CrossRef

Notas de rodapé

1. Um solucionador SMT baseado em BDD foi desenvolvido (ver, por exemplo, [28]). Neste artigo, consideramos o uso apenas de técnicas de BDD.

autores

Fuma MOTOYAMA
  Hokkaido University

received the B.E. degree in 2020 and the M.I.S degree in 2022 from Hokkaido University. He is currently a doctor course student at the Graduate School of Information Science and Technology, Hokkaido University. His research interests include Boolean networks.

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.

Yuh YAMASHITA
  Hokkaido University

received his B.E., M.E., and Ph.D. degrees from Hokkaido University, Japan, in 1984, 1986, and 1993, respectively. In 1988, he joined the faculty of Hokkaido University. From 1996 to 2004, he was an Associate Professor at the Nara Institute of Science and Technology, Japan. Since 2004, he has been a Professor of the Graduate School of Information Science and Technology, at Hokkaido University. His research interests include nonlinear control and nonlinear dynamical systems. He is a member of SICE, ISCIE, IEICE, RSJ, and IEEE.

Palavra-chave