Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - An integer optimization approach for reverse engineering of gene regulatory networks
AU - Cordone, Roberto
AU - Lulli, Guglielmo
PY - 2013/3
Y1 - 2013/3
N2 - Gene regulatory networks are a common tool to describe the chemical interactions between genes in a living cell. This paper considers the Weighted Gene Regulatory Network (WGRN) problem, which consists in identifying a reduced set of interesting candidate regulatory elements which can explain the expression of all other genes. We provide an integer programming formulation based on a graph model and derive from it a branch-and-bound algorithm which exploits the Lagrangian relaxation of suitable constraints. This allows to determine lower bounds tighter than CPLEX on most benchmark instances, with the exception of the sparser ones. In order to determine feasible solutions for the problem, which appears to be a hard task for general-purpose solvers, we also develop and compare two metaheuristic approaches, namely a Tabu Search and a Variable Neighborhood Search algorithm. The experiments performed on both of them suggest that diversification is a key feature to solve the problem.
AB - Gene regulatory networks are a common tool to describe the chemical interactions between genes in a living cell. This paper considers the Weighted Gene Regulatory Network (WGRN) problem, which consists in identifying a reduced set of interesting candidate regulatory elements which can explain the expression of all other genes. We provide an integer programming formulation based on a graph model and derive from it a branch-and-bound algorithm which exploits the Lagrangian relaxation of suitable constraints. This allows to determine lower bounds tighter than CPLEX on most benchmark instances, with the exception of the sparser ones. In order to determine feasible solutions for the problem, which appears to be a hard task for general-purpose solvers, we also develop and compare two metaheuristic approaches, namely a Tabu Search and a Variable Neighborhood Search algorithm. The experiments performed on both of them suggest that diversification is a key feature to solve the problem.
KW - Gene regulatory networks
KW - Lagrangian relaxation
KW - Tabu search
KW - Variable neighborhood search
U2 - 10.1016/j.dam.2012.02.010
DO - 10.1016/j.dam.2012.02.010
M3 - Journal article
AN - SCOPUS:84873413969
VL - 161
SP - 580
EP - 592
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - 4-5
ER -