jgtz / booleandoi

README BooleanDOI

I) THE METHOD

This repository contains functions using GRASP algorithm to solve the target control problem in Boolean network model, proposed in a paper titled "Target Control in Logical Models Using the Domain of Influence of Nodes" submitted to the special issue ''Logical Modeling of Cellular Processes'' of Frontiers in Physiology. A preprint version is available at BioRxiv: https://www.biorxiv.org/content/early/2018/01/04/243246 .

This algorithm is based on a concept named logic domain of influence and a random heuristic algorithm called greedy randomized adaptive search procedure (GRASP). More details can be found in the paper [1] and [2].

The code is written in Python 2.7. The module requires NetworkX 1.11.

Correspondence can be directed to [email protected]. Please cite the corresponding paper when the code is used or adapted.

[1] PARDALOS, P. M., T. QIAN, and M. G. RESENDE (1998) “A Greedy Randomized Adaptive Search Procedure for the Feedback Vertex Set Problem,” Journal of Combinatorial Optimization, 2(4), pp. 399–412.

[2] FESTA, P., P. M. PARDALOS, and M. G. C. RESENDE (2001) “Algorithm 815: FORTRAN Subroutines for Computing Approximate Solutions of Feedback Set Problems Using GRASP,” ACM Trans. Math. Softw., 27(4), pp. 456–464

II) STRUCTURE OF MODULE

Related functions are stored in BooleanDOI_processing.py, BooleanDOI_DOI.py, BooleanDOI_TargetControl.py and qm.py.

qm.py is an external library for Quine--McCluskey algorithm written by George Prekas [email protected], whose work is based on code from Robert Dick [email protected] and Pat Maupin [email protected].

BooleanDOI_processing.py contains functions to do pre-processing for the target control algorithm. It contains functions that can read and write a Boolean rule file in the format of Booleannet. Specifically for the format of Booleannet file, the node states are indicated by node names, the future state of a node is indicated by an asterisk, and the rules use the Boolean operators "and", "or", "not", e.g. A*= B or C. (More details about Booleannet can be found in https://github.com/ialbert/booleannet ). It also contains functions to calculate the expanded network or reduced network from a Boolean network model constructed through reading a Boolean rule file as mentioned above. In the end, it contains a function to read the expanded network generated by Jorge's stable motif algorithm written in Java. (More details can be found in https://github.com/jgtz/StableMotifs ).

BooleanDOI_DOI.py contains functions to calculate the Logic Domain of Influence (LDOI) of a given node state set on the expanded network.

BooleanDOI_TargetControl.py contains functions to calculate solutions to a Target Control problem (on the expanded network).

example1.py contains an example illustrating how to use the code.

example1.txt is the corresponding Boolean rule file used in example1.py.

III) INSTRUCTIONS

(a) Logic Domain of Influence

To calculate the Logic Domain of Influence (LDOI) of a given node state set, just import BooleanDOI_DOI and call truncated_node_of_influence_BFS(G, source) .

To use this module, import FVS and call FVS() just as a regular function.
The function can take 6 paramters listed below and only the first (the graph) is neccessary.

Parameters

G : the given expanded network as an DiGraph

source : the list of node states that we are interested in to find LDOI

        source node can either be a single node or a list of nodes,
        
        DO NOT INCLUDE A NODE AND ITS NEGATION FOR SOURCE

Default Parameter Values

composite_node_delimiter='_' : as name suggested, used to parse a composite node, e.g. a composite node 'A_B' means A AND B for the default value

Negation_func= : the function to calculate the complementary node of a given node on the expanded network

Returns

LDOI in the format of a set,

complementary list for the visited part of the search

a list containing any found conflict name to the source during the search process

a list containing all the composte nodes that is not included in the LDOI

(b) Target Control

To apply the target control algorithm, just import BooleanDOI_TargetControl and call update_single_DOI() and GRASP_target_control().

For the GRASP_target_control function, the following parameters are needed Parameters

G_expanded: the input expanded_graph as a DiGraph object

Target : the target set

max_itr : the number of iterations that are repeated to find the solution

TDOI_BFS : a dictionary to store the LDOI of each node state set

flagged : a dictionary to store whether the LDOI of each node state set contains the negation of any target node

potential : a dictionary to store the composite nodes visited but not included during the search process for LDOI for each node state set

Default Parameter Values

candidates_score_index : the chosen heuristic greedy function,

                     '0' represents the size of LDOI, 
                     
                     '1' represents the size of composite nodes attached to the LDOI
                     
                     '2' represents the linear combination of the two above with the equal weight
                     
                     '3' represents the size of LDOI with penalization, penalized by multiplied with -1 for those containing                                      negation of any target
                     
                     '4' represents the size of LDOI with penalization, penalized by being subtracted by maximum LDOI for those                                  containing negation of any target

forbidden_nodes : the nodes that are forbiden to be used, both the positive states and the negative states will be forbidden

avail_nodes : the nodes that are available to be used, both the positive states and the negative states will be available

forbidden_node_states : the node states that are forbiden to be used

notice different meaning for the default value for forbidden_nodes and avail_nodes: when forbidden_nodes is empty, we do not forbid any node, when avail_nodes is empyty, we allow all nodes

Returns

solutions: a dictionay maps a tuple to a integer value

       the first element of the tuple is the solution as a sorted tuple

       the second element of the tuple is a Boolean value to indicate whether the LDOI of the solution is incompatible or not. True  means incompatible.
       
       The integer number is the frequency this solution is obtained during the max_itr iterations.

A Boolean value to indicate whether we found any solution.

Notice the current program will only report single node solution if they exist and the program will only begin to search for multi-node solution if single node solution does not exist. To change this behavior to search for multi-node from the beginning, change the True to False in line 435 of BooleanDOI_TargetControl.py

IV) EXAMPLES

(a) A simple network

More details can be found in example1.py

import networkx as nx

import BooleanDOI_processing as BDOIp

import BooleanDOI_TargetControl as BDOItc

Here we construct a Boolean network model from a written Boolean rules in the Booleannet format. The rules are store in the text file "example1.txt"

f = open("example1.txt",r)

lines = f.readlines()

f.close()

Gread, readnodes = BDOIp.form_network(lines, sorted_nodename = False)

Then one can obtain the expanded network by calling function Get_expanded_network

G_expanded = BDOIp.Get_expanded_network(Gread)

Then one can solve a target control problem as followed. First one need to initialize the three dictionary called TDOI_BFS, flagged and potential as a global variable. Then one can call the update_single_DOI to calculate the LDOI for each single node. Then one can call the GRASP_target_control algorithm to solve the target control algorithm.

TDOI_BFS, flagged, potential = {}, {}, {}

BDOItc.update_single_DOI(G_expanded, network_name='example1', TDOI_BFS, flagged, potential)

solutions, solution_found = BDOItc.GRASP_target_control(G_expanded, Target = set(['n2n']), max_itr = 500, TDOI_BFS, flagged, potential, custom_score_index = '3')

print solutions

A sample output looks like

defaultdict(<type 'int'>, {(('~n5n',), True): 195, (('n4n',), False): 301, (('n3n', 'n5n'), False): 4})

It means that ['~n5n'], ['n4n'], ['n3n','n5n'] are the solutions found, they are incompatible, compatible and compatible solution respectively, and they have been found 195, 301 and 4 times respectively during the 500 iterations. More specifically, ['~n5n'] (i.e., meaning the OFF state of node 5), ['n4n'] (i.e., the ON state of node 4), ['n3n','n5n'] (i.e., the ON state of node 3 coupled with the ON state of node 5) can yield the ON state of node 2 (the target). The first is incompatible (it has internal conflicts, so it is expected to be harder to implement in practice) and was found 195 times during the 500 iterations, the second is compatible (conflict-free) and was found 301 times, and the third is compatible and was found 4 times during the 500 iterations. After running the python script, three files are created. Their name starts with the network name and ends with "_flagged", "_potential", "_TDOI", respectively. These three files store the corresponding parameters “flagged”, “potential” and “TDOI_BFS” respectively, as mentioned above.

(b) EMT network

We also provide the Booleannet file of the EMT network (EMT.txt) and python demo file (EMTNetwork_TargetControl.py) using the target control algorithm. As this network has source nodes with constant node states (the last eight entries in EMT.txt), we did a network reduction to iteratively remove all the nodes with constant states and thus the python code is a little bit longer than the one for the simple example. However, the essential steps (line 142, 145 and 148) are essentially the same.

We also implement several options for this EMTNetwork_TargetControl.py by supplying three external parameters. These represent the target, the forbidden node (state) list and the custom score index (i.e. the greedy function). One can look into the python files to see exactly what these parameters correspond to. For example, one can run the python file using the command

python EMTNetwork_TargetControl.py 1 0 3

Here the 1 refers to the target set as ~EMT, 0 means no restriction and 3 means the fourth custom score. We also set the default parameters for this script. That is running command

python EMTNetwork_TargetControl.py

is equivalent to

python EMTNetwork_TargetControl.py 1 0 0

The output format of this script is similar to the above and the script will generate additional files. Besides those three files mentioned above, we also have two additional files, EMTreduced_Reduced_Rules.txt and EMTreduced_node_mapping.txt. The first file stores the Boolean rules corresponding to the reduced system, where additionally the node names are replaced by indices, and the mapping between node names and node indices is given in the second file.

In addition, we now upload all four models analyzed in our work (in both Booleannet and SBML formats) in the github directory (under folder models).

V) COPYRIGHT

The MIT License (MIT)

Copyright (c) 2017 Gang Yang and Reka Albert.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.