Abduction Based Drug Target Discovery Using Boolean Control Network 59by control parameters based on abduction principle (Sect. 3 ) and finally, we show
its application in breast cancer (Sect. 4 ).
2 Boolean Control Network
In this section we first review the main theoretical elements used in this article,
namely: propositional logic, Boolean network and then we introduce Boolean
control network.
2.1 Propositional Logic
A propositional formula is inductively constructed from atoms composed of con-
stants (False/0, True/1) and variablesV, unary negation operator¬, and binary
logical operators (e.g.,∧/conjunction/and,∨/disjunction/or). Aliteralis either
an atom or its negation. Given a formulaf,V(f) denotes the set of variables
occurring inf. For example, letfαbe the propositional formula representing the
exclusiveorbetween atomx 1 and the negation of atomx 2 ,fα=(x 1 ¬x 2 ), the
variables areV(fα)={x 1 ,x 2 }and the literals arex 1 and¬x 2 .LetX′⊆Xbe a
subset of variablesf↓X′is the restriction of a formulafto the literals involving
the variables ofX′.
Acubesyntactically denotes a conjunction of literals and aclauseadis-
junction. In this article, cubes and clauses will be assimilated to literal sets
when needed. Adisjunctive normal form(dnf) of a formula is a disjunction
of cubes (ie.,
∨
i∧
jilji) whereas aconjunctive normal form(cnf) is a con-
junction of clauses (ie.,
∧∨
jilji). Any formula can be transformed indnf
or incnf. For example, adnfoffαis (x 1 ∧x 2 )∨(¬x 1 ∧¬x 2 ) and acnfis
(¬x 1 ∨x 2 )∧(x 1 ∨¬x 2 ).
Let aninterpretationI:V→{ 0 , 1 }be a mapping assigning a truth value to
each variable^3 ,amodelof a formulaf,I |=f, is an interpretation such that the
formula is evaluated to True and asatisfiableformula admits a model at least.
For example,fαis satisfiable because the interpretationsI 1 ={x 1 =1,x 2 =1}
andI 2 ={x 1 =0,x 2 =0}are both models offα.
Formulaf 1 entailsformulaf 2 , denoted byf 1 |=f 2 , if and only if any model
off 1 is also a model off 2 (ie.,f 1 |=f 2
def
==∀I:I |=f 1 =⇒ I|=f 2 ). Hence,
the entailment defines a partial order on formulas.
AmintermCIof an interpretationIis the unique cube such thatV(I)=
V(CI) fulfillingI |=CI. For the exampleC 1 =x 1 ∧x 2 andC 2 =¬x 1 ∧¬x 2 are
the minterms ofI 1 andI 2 respectively. A cubeCentailing a formulafis said an
implicantoffand it isprimeif it ceases to be one when deprived of any literal.
Considering the example,C 1 ,C 2 are both prime implicants offαwithI 1 and
I 2 as model respectively, thus entailingfα:C 1 |=fα,C 2 |=fα. Notice that by
contrast to a minterm, an implicant does not necessary involve all the variables
of the formula (e.g.,x 1 is an implicant of (x 1 ∨x 2 )∧(x 1 ∨x 3 )).
(^3) A mapping will be describedx=vinstead ofx→vfor the sake of simplicity.