Uma rede booleana consiste em um conjunto discreto de variáveis booleanas, a cada uma das quais é atribuída uma função booleana (possivelmente diferente para cada variável) que recebe entradas de um subconjunto dessas variáveis e produz uma saída que determina o estado da variável à qual está atribuída. Esse conjunto de funções determina, na prática, uma topologia (conectividade) sobre o conjunto de variáveis, que passam a ser nós em uma rede. Geralmente, a dinâmica do sistema é tratada como uma série temporal discreta, onde o estado de toda a rede no tempo t+1 é determinado pela avaliação da função de cada variável no estado da rede no tempo t. Isso pode ser feito de forma síncrona ou assíncrona. As redes booleanas têm sido utilizadas na biologia para modelar redes regulatórias. Embora as redes booleanas sejam uma simplificação grosseira da realidade genética, na qual os genes não são interruptores binários simples, existem vários casos em que elas transmitem corretamente o padrão correto de genes expressos e suprimidos. O modelo (síncrono), aparentemente simples do ponto de vista matemático, só foi totalmente compreendido em meados dos anos 2000.
Modelo clássico Uma rede booleana é um tipo particular de sistema dinâmico sequencial, onde o tempo e os estados são discretos, ou seja, tanto o conjunto de variáveis quanto o conjunto de estados na série temporal possuem uma bijeção com uma série de números inteiros. Uma rede booleana aleatória (RBN, na sigla em inglês) é uma rede selecionada aleatoriamente a partir do conjunto de todas as redes booleanas possíveis de um tamanho específico, N. Pode-se então estudar estatisticamente como as propriedades esperadas de tais redes dependem de várias propriedades estatísticas do conjunto de todas as redes possíveis. Por exemplo, pode-se estudar como o comportamento da RBN muda conforme a conectividade média é alterada. As primeiras redes booleanas foram propostas por Stuart A. Kauffman em 1969, como modelos aleatórios de redes de regulação genética.
Atratores Como uma rede booleana possui apenas 2N estados possíveis, uma trajetória mais cedo ou mais tarde alcançará um estado visitado anteriormente e, portanto, como a dinâmica é determinística, a trajetória cairá em um estado estacionário ou ciclo chamado atrator (embora no campo mais amplo dos sistemas dinâmicos, um ciclo só seja um atrator se perturbações a partir dele levarem de volta a ele). Se o atrator possuir apenas um único estado, ele é chamado de atrator de ponto, e se o atrator consistir em mais de um estado, é chamado de atrator de ciclo. O conjunto de estados que levam a um atrator é chamado de bacia do atrator. Os estados que ocorrem apenas no início das trajetórias (nenhuma trajetória leva a eles) são chamados de estados do Jardim do Éden e a dinâmica da rede flui desses estados em direção aos atratores. O tempo necessário para alcançar um atrator é chamado de tempo transitório. Com o aumento da capacidade de processamento dos computadores e uma maior compreensão desse modelo aparentemente simples, diferentes autores forneceram estimativas distintas para o número médio e comprimento dos atratores. Abaixo apresenta-se um breve resumo das principais publicações.
Estabilidade Na teoria dos sistemas dinâmicos, a estrutura e o comprimento dos atratores de uma rede correspondem à fase dinâmica da rede. A estabilidade das redes booleanas depende das conexões de seus nós. Uma rede booleana pode exibir comportamento estável, crítico ou caótico. Esse fenômeno é governado por um valor crítico do número médio de conexões dos nós (
K
c
{\displaystyle K_{c}}
), e pode ser caracterizado pela Distância de Hamming como medida de distância. No regime instável, a distância entre dois estados inicialmente próximos cresce, em média, exponencialmente no tempo, enquanto no regime estável ela diminui exponencialmente. Por "estados inicialmente próximos", entende-se que a distância de Hamming é pequena em comparação com o número de nós (
N
{\displaystyle N}
) na rede. Para o modelo N-K, a rede é estável se
K <
K
c
{\displaystyle K<K_{c}}
, crítica se
K =
K
c
{\displaystyle K=K_{c}}
, e instável se
K >
K
c
{\displaystyle K>K_{c}}
. O estado de um determinado nó
n
i
{\displaystyle n_{i}}
é atualizado de acordo com sua tabela verdade, cujas saídas são preenchidas aleatoriamente.
p
i
{\displaystyle p_{i}}
denota a probabilidade de atribuir uma saída desativada (falsa) a uma determinada série de sinais de entrada. Se
p
i
= p = c o n s t .
{\displaystyle p_{i}=p=const.}
para cada nó, a transição entre a faixa estável e caótica depende de
p
{\displaystyle p}
. De acordo com Bernard Derrida e Yves Pomeau, o valor crítico do número médio de conexões é
K
c
= 1
/
[ 2 p ( 1 − p ) ]
{\displaystyle K_{c}=1/[2p(1-p)]}
. Se
K
{\displaystyle K}
não for constante e não houver correlação entre os graus de entrada (in-degrees) e os graus de saída (out-degrees), as condições de estabilidade são determinadas por
⟨
K
i n
⟩
{\displaystyle \langle K^{in}\rangle }
. A rede é estável se
⟨
K
i n
⟩ <
K
c
{\displaystyle \langle K^{in}\rangle <K_{c}}
, crítica se
⟨
K
i n
⟩ =
K
c
{\displaystyle \langle K^{in}\rangle =K_{c}}
, e instável se
⟨
K
i n
⟩ >
K
c
{\displaystyle \langle K^{in}\rangle >K_{c}}
. As condições de estabilidade são as mesmas no caso de redes com topologia livre de escala, onde a distribuição dos graus de entrada e saída segue uma distribuição de lei de potência:
P ( K ) ∝
K
− γ
{\displaystyle P(K)\propto K^{-\gamma }}
, e
⟨
K
i n
⟩ = ⟨
K
o u t
⟩
{\displaystyle \langle K^{in}\rangle =\langle K^{out}\rangle }
, uma vez que cada ligação de saída de um nó é uma ligação de entrada para outro. A sensibilidade mostra a probabilidade de que a saída da função booleana de um determinado nó mude se a sua entrada for alterada. Para redes booleanas aleatórias,
q
i
= 2
p
i
( 1 −
p
i
)
{\displaystyle q_{i}=2p_{i}(1-p_{i})}
. No caso geral, a estabilidade da rede é governada pelo maior autovalor
λ
Q
{\displaystyle \lambda _{Q}}
da matriz
Q
{\displaystyle Q}
, onde
Q
i j
=
q
i
A
i j
{\displaystyle Q_{ij}=q_{i}A_{ij}}
, e
A
{\displaystyle A}
é a matriz de adjacência da rede. A rede é estável se
λ
Q
< 1
{\displaystyle \lambda _{Q}<1}
, crítica se
λ
Q
= 1
{\displaystyle \lambda _{Q}=1}
, e instável se
λ
Q
> 1
{\displaystyle \lambda _{Q}>1}
.
Variações do modelo
Outras topologias Um dos temas de estudo consiste em analisar diferentes topologias de grafos subjacentes.
O caso homogêneo refere-se simplesmente a uma grade que se reduz ao famoso Modelo de Ising. Topologias livres de escala podem ser escolhidas para redes booleanas. Pode-se distinguir o caso em que apenas a distribuição do grau de entrada segue uma lei de potência, apenas a distribuição do grau de saída, ou ambas.
Outros esquemas de atualização As redes booleanas clássicas (às vezes chamadas de CRBN, ou seja, Classic Random Boolean Network) são atualizadas de forma síncrona. Motivados pelo fato de que os genes geralmente não mudam de estado simultaneamente, diferentes alternativas foram introduzidas. Uma classificação comum é a seguinte:
Redes booleanas de atualização assíncrona determinística (DRBNs) não são atualizadas de forma síncrona, mas ainda existe uma solução determinística. Um nó i será atualizado quando t ≡ Qi (mod Pi), onde t é o passo de tempo. O caso mais geral é a atualização estocástica completa (GARBN, general asynchronous random Boolean networks). Aqui, um (ou mais) nó(s) são selecionados a cada passo computacional para serem atualizados. O modelo de sinal do Sistema Dinâmico Booleano Parcialmente Observado (POBDS) difere de todos os modelos anteriores de redes booleanas determinísticas e estocásticas ao remover a suposição de observabilidade direta do vetor de estado booleano e permitir incerteza no processo de observação, abordando o cenário encontrado na prática. Redes booleanas autônomas (ABNs) são atualizadas em tempo contínuo (t é um número real, não um número inteiro), o que leva a condições de corrida e a comportamentos dinâmicos complexos, tais como o caos determinístico.
Aplicação de redes booleanas
Classificação A Classificação Bayesiana Ótima Escalonável desenvolveu uma classificação ótima de trajetórias considerando a incerteza potencial do modelo e também propôs uma classificação de trajetórias baseada em partículas que é altamente escalonável para grandes redes com complexidade muito menor do que a solução ótima.
Ver também Modelo NK
Referências
Dubrova, E., Teslenko, M., Martinelli, A., (2005). *Kauffman Networks: Analysis and Applications, in "Proceedings of International Conference on Computer-Aided Design", pages 479-484.
