Home > Research > Publications & Outputs > An integer optimization approach for reverse en...
View graph of relations

An integer optimization approach for reverse engineering of gene regulatory networks

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

An integer optimization approach for reverse engineering of gene regulatory networks. / Cordone, Roberto; Lulli, Guglielmo.

In: Discrete Applied Mathematics, Vol. 161, No. 4-5, 03.2013, p. 580-592.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Author

Cordone, Roberto ; Lulli, Guglielmo. / An integer optimization approach for reverse engineering of gene regulatory networks. In: Discrete Applied Mathematics. 2013 ; Vol. 161, No. 4-5. pp. 580-592.

Bibtex

@article{7bebff27dd8d440e9af0113f22452075,
title = "An integer optimization approach for reverse engineering of gene regulatory networks",
abstract = "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. ",
keywords = "Gene regulatory networks, Lagrangian relaxation, Tabu search, Variable neighborhood search",
author = "Roberto Cordone and Guglielmo Lulli",
year = "2013",
month = mar,
doi = "10.1016/j.dam.2012.02.010",
language = "English",
volume = "161",
pages = "580--592",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "4-5",

}

RIS

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 -