Expand description
Boolean Networks
A (parametrised) BooleanNetwork
is an extension of a RegulatoryGraph
that can specify
for each variable a Boolean update function. This update function can be used to generate
a state-transition graph of the network. There are different techniques for generating
such state-transition graphs. Later, you will learn about an asynchronous state-transition
graph used in this library, but other variants (such as synchronous) are also possible.
Typically, a BooleanNetwork
has a fixed update function for each variable. For example,
let’s consider this simple graph:
graph LR
a(A)
b(B)
c(C)
a-- + -->b
b-- + -->a
c-- + -->a
c-. - .->b
a-- - -->a
We can extend this graph to a BooleanNetwork
by assigning each variable an update function
(we use the $
symbol to denote a function declaration):
$A: C | (!A & B)
$B: A
$C: true
Notice that C has no regulators, hence its update function has to be constant. Also, C -> B
is not observable, hence C
does not have to appear in the function of A
. Finally, A
appears
with a negation in $A
because it regulates itself negatively. However, the choice of logical
connectives (|
and &
) is arbitrary.
We can of course write all of this in Rust:
use biodivine_lib_param_bn::{RegulatoryGraph, BooleanNetwork, FnUpdate};
use std::convert::TryFrom;
// First, we build the regulatory graph of the network.
let rg = RegulatoryGraph::try_from(r"
A -> B
B -> A
C -> A
C -|? B
A -| A
").unwrap();
let id_a = rg.find_variable("A").unwrap();
let id_b = rg.find_variable("B").unwrap();
let id_c = rg.find_variable("C").unwrap();
// Now create a Boolean network and add update functions for each variable.
let mut bn = BooleanNetwork::new(rg);
assert!(bn.get_update_function(id_a).is_none());
// We can use standard Boolean operators `&`, `|`, `=>`, `<=>`, `^` and `!`.
// Names are alphanumeric strings (starting with a letter), possibly containing `_`.
bn.add_string_update_function("A", "C | (!A & B)")?;
bn.add_string_update_function("B", "A")?;
bn.add_string_update_function("C", "true")?;
// We can also test that the functions are properly set.
assert_eq!(&Some(FnUpdate::Const(true)), bn.get_update_function(id_c));
assert_eq!(&Some(FnUpdate::Var(id_a)), bn.get_update_function(id_b));
Normally, this would be the end of intro to Boolean networks, however, there is one more important aspect that we need to discuss that is usually not available in other BN packages.
Parametrised Boolean Networks
As you might have noticed above, a BooleanNetwork
is also valid if it does not have any
update functions set. If a Boolean network is missing some update functions, we say that
such network is parametrised. Intuitively, this means that there is some uncertainty
in how the update functions of the network behave. In fact, we will later show how to
introduce uncertainty even only into parts of an update function. But for now, let us only
focus on cases where the entire update function is unknown.
To each parametrised BooleanNetwork
corresponds a collection of fully specified Boolean
networks. We call these fully specified networks parametrisations, or colors. More
formally, a parametrisation assigns values to the rows of each update function table, thus
making the network fully specified, and color is just a more abstract concept from graph
theory which we can apply also outside of the domain of Boolean networks.
Note that the structure of the RegulatoryGraph
significantly limits the space of all possible
parametrisations. Only update functions that would be valid with respect to the specified graph
are considered (i.e. functions must depend only on the declared regulators and must follow
the declared monotonicity and observability rules).
In our example, update function of C
can thus be only true
or false
. Update function
of B
can in fact be A
, A & !C
, and A | !C
(since C
is not declared as necessarily
observable, we actually also consider both cases where C
can have impact, but also the one
where it does not). For the update function of A
, there are 9 possible valid
update functions.
When the update function for a variable X
is completely unknown as in this case, we say
that X
is implicitly parametrised.
Uninterpreted Boolean Functions as Parameters
If only part of the update function is unknown, we can use explicit parameters, or uninterpreted Boolean functions, to describe such behaviour. Formally, every uninterpreted Boolean function has a fixed name and arity, but its behaviour is otherwise unspecified.
For example, for variable A
from above, we can write:
$A: C | f(A, B)
Here, f
is an uninterpreted function of artiy 2
(we can also use uninterpreted constants,
which are simply functions of arity 0
). This way, we have just exactly specified the
dependence of A
on C
, while leaving the dependence on A
and B
unknown. Note that f
can only take values which follow the properties of the regulatory graph, just as we had for
the implicitly parametrised case above (so in this case, there are two possible
instantiations of f
).
When the update function of a variable X
contains such uninterpreted functions, we say X
is explicitly parametrised and the uninterpreted functions are its explicit parameters.
Note that such explicit parameter can be shared accross variables. By using a parameter with
the same name in two different update functions, you declare that this part of the two
functions is identical.
At the moment, arguments of each explicit parameter must be variables (complex Boolean expressions are not allowed). However, this restriction may be lifted in the future.
In Rust, we can capture this in the following way:
// Use the same graph as above...
let mut bn = BooleanNetwork::new(rg);
assert!(bn.get_update_function(id_a).is_none());
// Every explicit parameter must be declared before you use it in a function.
let id_f: ParameterId = bn.add_parameter("f", 2)?;
// `ParameterId` indexes `BooleanNetwork` just as `VariableId` would.
assert_eq!("f", bn[id_f].get_name());
assert_eq!(2, bn[id_f].get_arity());
bn.add_string_update_function("A", "C | f(A, B)")?;
let params: Vec<ParameterId> = bn.get_update_function(id_a).as_ref().unwrap().collect_parameters();
assert_eq!(vec![id_f], params);
Overall, this mechanism provides a very powerful framework for capturing uncertainty in Boolean networks.
String serialisation and other features
To store and share the BooleanNetwork
objects, you can use a similar format to
that used by the RegulatoryGraph
. The only difference is that now each line can be either
a regulation, or a function declaration (the order of declarations does not matter).
Furthermore, you can prefix a line with #
to mark that line as a comment which will be
skipped by the parser. Together, this is what we refer to as the .aeon
format.
use biodivine_lib_param_bn::BooleanNetwork;
use std::convert::TryFrom;
// Notice that C is implicitly parametrised since we do not specify an update function for it.
// Also, explicit parameters are not declared, they are inferred from declared functions.
let bn = BooleanNetwork::try_from(r"
A -> B
C -|? B
# Update function of variable B:
$B: A
C -> A
B -> A
A -| A
$A: C | f(A, B)
").unwrap();
// The same format is also used by the default `Display` implementation.
// However, note that the comments are not preserved!
assert_eq!(bn, BooleanNetwork::try_from(bn.to_string().as_str()).unwrap())
Aside from this, BooleanNetwork
allows you to access the underlying RegulatoryGraph
by calling BooleanNetwork.as_graph()
. But in fact, a lot of the commonly used methods
of the RegulatoryGraph
are also implemented for the BooleanNetwork
(e.g.
get_variable_name
or regulators
), so the conversion often isn’t necessary.