File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: On construction and control of probabilistic Boolean networks
Title  On construction and control of probabilistic Boolean networks 

Authors  
Advisors  
Issue Date  2012 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Chen, X. [陈曦]. (2012). On construction and control of probabilistic Boolean networks. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4832960 
Abstract  Modeling gene regulation is an important problem in genomic research. The Boolean network (BN) and its generalization Probabilistic Boolean network (PBN) have been proposed to model genetic regulatory interactions.
BN is a deterministic model while PBN is a stochastic model. In a PBN, on one hand, its stationary distribution gives important information about the longrun behavior of the network. On the other hand, one may be interested in system synthesis which requires the construction of networks from the observed stationary distribution. This results in an inverse problem of constructing PBNs from a given stationary distribution and a given set of Boolean Networks (BNs), which is illposed and challenging, because there may be many networks or no network having the given properties and the size of the inverse problem is huge. The inverse problem is first formulated as a constrained least squares problem. A heuristic method is then proposed based on the conjugate gradient (CG) algorithm, an iterative method, to solve the resulting least squares problem. An estimation method for the parameters of the PBNs is also discussed. Numerical examples are then given to demonstrate the effectiveness of the proposed methods.
However, the PBNs generated by the above algorithm depends on the initial guess and is not unique. A heuristic method is then proposed for generating PBNs from a given transition probability matrix. Unique solution can be obtained in this case. Moreover, these algorithms are able to recover the dominated BNs and therefore the major structure of the network.
To further evaluate the feasible solutions, a maximum entropy approach is proposed using entropy as a measure of the fitness. Newton’s method in conjunction with the CG method is then applied to solving the inverse problem. The convergence rate of the proposed method is demonstrated. Numerical examples are also given to demonstrate the effectiveness of our proposed method.
Another important problem is to find the optimal control policy for a PBN so as to avoid the network from entering into undesirable states. By applying external control, the network is desired to enter into some state within a few time steps. For PBN CONTROL, people propose to find a control sequence such that the network will terminate in the desired state with a maximum probability. Also, the problem of minimizing the maximum cost is considered. Integer linear programming (ILP) and dynamic programming (DP) in conjunction with hard constraints are then employed to solve the above problems. Numerical experiments are given to demonstrate the effectiveness of our algorithms. A hardness result is demonstrated and suggests that PBN CONTROL is harder than BN CONTROL. In addition, deciding the steady state probability in PBN for a specified global state is demonstrated to be NPhard.
However, due to the high computational complexity of PBNs, DP method is computationally inefficient for a large size network. Inspired by the state reduction strategies studied in [86], the DP method in conjunction with state reduction approach is then proposed to reduce the computational cost of the DP method. Numerical examples are given to demonstrate both the effectiveness and the efficiency of our proposed method. 
Degree  Doctor of Philosophy 
Subject  Genetic regulation  Mathematical models. Algebra, Boolean. Control theory. 
Dept/Program  Mathematics 
Persistent Identifier  http://hdl.handle.net/10722/173904 
HKU Library Item ID  b4832960 
DC Field  Value  Language 

dc.contributor.advisor  Ching, WK   
dc.contributor.advisor  Tsing, NK   
dc.contributor.author  Chen, Xi   
dc.contributor.author  陈曦   
dc.date.issued  2012   
dc.identifier.citation  Chen, X. [陈曦]. (2012). On construction and control of probabilistic Boolean networks. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4832960   
dc.identifier.uri  http://hdl.handle.net/10722/173904   
dc.description.abstract  Modeling gene regulation is an important problem in genomic research. The Boolean network (BN) and its generalization Probabilistic Boolean network (PBN) have been proposed to model genetic regulatory interactions. BN is a deterministic model while PBN is a stochastic model. In a PBN, on one hand, its stationary distribution gives important information about the longrun behavior of the network. On the other hand, one may be interested in system synthesis which requires the construction of networks from the observed stationary distribution. This results in an inverse problem of constructing PBNs from a given stationary distribution and a given set of Boolean Networks (BNs), which is illposed and challenging, because there may be many networks or no network having the given properties and the size of the inverse problem is huge. The inverse problem is first formulated as a constrained least squares problem. A heuristic method is then proposed based on the conjugate gradient (CG) algorithm, an iterative method, to solve the resulting least squares problem. An estimation method for the parameters of the PBNs is also discussed. Numerical examples are then given to demonstrate the effectiveness of the proposed methods. However, the PBNs generated by the above algorithm depends on the initial guess and is not unique. A heuristic method is then proposed for generating PBNs from a given transition probability matrix. Unique solution can be obtained in this case. Moreover, these algorithms are able to recover the dominated BNs and therefore the major structure of the network. To further evaluate the feasible solutions, a maximum entropy approach is proposed using entropy as a measure of the fitness. Newton’s method in conjunction with the CG method is then applied to solving the inverse problem. The convergence rate of the proposed method is demonstrated. Numerical examples are also given to demonstrate the effectiveness of our proposed method. Another important problem is to find the optimal control policy for a PBN so as to avoid the network from entering into undesirable states. By applying external control, the network is desired to enter into some state within a few time steps. For PBN CONTROL, people propose to find a control sequence such that the network will terminate in the desired state with a maximum probability. Also, the problem of minimizing the maximum cost is considered. Integer linear programming (ILP) and dynamic programming (DP) in conjunction with hard constraints are then employed to solve the above problems. Numerical experiments are given to demonstrate the effectiveness of our algorithms. A hardness result is demonstrated and suggests that PBN CONTROL is harder than BN CONTROL. In addition, deciding the steady state probability in PBN for a specified global state is demonstrated to be NPhard. However, due to the high computational complexity of PBNs, DP method is computationally inefficient for a large size network. Inspired by the state reduction strategies studied in [86], the DP method in conjunction with state reduction approach is then proposed to reduce the computational cost of the DP method. Numerical examples are given to demonstrate both the effectiveness and the efficiency of our proposed method.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.source.uri  http://hub.hku.hk/bib/B48329605   
dc.subject.lcsh  Genetic regulation  Mathematical models.   
dc.subject.lcsh  Algebra, Boolean.   
dc.subject.lcsh  Control theory.   
dc.title  On construction and control of probabilistic Boolean networks   
dc.type  PG_Thesis   
dc.identifier.hkul  b4832960   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Mathematics   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b4832960   
dc.date.hkucongregation  2012   