An integer linear programming approach for finding deregulated subgraphs in regulatory networks. 2012

Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
Department of Human Genetics, Saarland University, 66421 Homburg/Saar, Germany. cbackes@bioinf.uni-sb.de

Deregulation of cell signaling pathways plays a crucial role in the development of tumors. The identification of such pathways requires effective analysis tools that facilitate the interpretation of expression differences. Here, we present a novel and highly efficient method for identifying deregulated subnetworks in a regulatory network. Given a score for each node that measures the degree of deregulation of the corresponding gene or protein, the algorithm computes the heaviest connected subnetwork of a specified size reachable from a designated root node. This root node can be interpreted as a molecular key player responsible for the observed deregulation. To demonstrate the potential of our approach, we analyzed three gene expression data sets. In one scenario, we compared expression profiles of non-malignant primary mammary epithelial cells derived from BRCA1 mutation carriers and of epithelial cells without BRCA1 mutation. Our results suggest that oxidative stress plays an important role in epithelial cells of BRCA1 mutation carriers and that the activation of stress proteins may result in avoidance of apoptosis leading to an increased overall survival of cells with genetic alterations. In summary, our approach opens new avenues for the elucidation of pathogenic mechanisms and for the detection of molecular key players.

UI MeSH Term Description Entries
D009154 Mutation Any detectable and heritable change in the genetic material that causes a change in the GENOTYPE and which is transmitted to daughter cells and to succeeding generations. Mutations
D011382 Programming, Linear A technique of operations research for solving certain kinds of problems involving many variables where a best value or set of best values is to be found. It is most likely to be feasible when the quantity to be optimized, sometimes called the objective function, can be stated as a mathematical expression in terms of the various activities within the system, and when this expression is simply proportional to the measure of the activities, i.e., is linear, and when all the restrictions are also linear. It is different from computer programming, although problems using linear programming techniques may be programmed on a computer. Linear Programming
D001940 Breast In humans, one of the paired regions in the anterior portion of the THORAX. The breasts consist of the MAMMARY GLANDS, the SKIN, the MUSCLES, the ADIPOSE TISSUE, and the CONNECTIVE TISSUES. Breasts
D004847 Epithelial Cells Cells that line the inner and outer surfaces of the body by forming cellular layers (EPITHELIUM) or masses. Epithelial cells lining the SKIN; the MOUTH; the NOSE; and the ANAL CANAL derive from ectoderm; those lining the RESPIRATORY SYSTEM and the DIGESTIVE SYSTEM derive from endoderm; others (CARDIOVASCULAR SYSTEM and LYMPHATIC SYSTEM) derive from mesoderm. Epithelial cells can be classified mainly by cell shape and function into squamous, glandular and transitional epithelial cells. Adenomatous Epithelial Cells,Columnar Glandular Epithelial Cells,Cuboidal Glandular Epithelial Cells,Glandular Epithelial Cells,Squamous Cells,Squamous Epithelial Cells,Transitional Epithelial Cells,Adenomatous Epithelial Cell,Cell, Adenomatous Epithelial,Cell, Epithelial,Cell, Glandular Epithelial,Cell, Squamous,Cell, Squamous Epithelial,Cell, Transitional Epithelial,Cells, Adenomatous Epithelial,Cells, Epithelial,Cells, Glandular Epithelial,Cells, Squamous,Cells, Squamous Epithelial,Cells, Transitional Epithelial,Epithelial Cell,Epithelial Cell, Adenomatous,Epithelial Cell, Glandular,Epithelial Cell, Squamous,Epithelial Cell, Transitional,Epithelial Cells, Adenomatous,Epithelial Cells, Glandular,Epithelial Cells, Squamous,Epithelial Cells, Transitional,Glandular Epithelial Cell,Squamous Cell,Squamous Epithelial Cell,Transitional Epithelial Cell
D005260 Female Females
D005786 Gene Expression Regulation Any of the processes by which nuclear, cytoplasmic, or intercellular factors influence the differential control (induction or repression) of gene action at the level of transcription or translation. Gene Action Regulation,Regulation of Gene Expression,Expression Regulation, Gene,Regulation, Gene Action,Regulation, Gene Expression
D005910 Glioma Benign and malignant central nervous system neoplasms derived from glial cells (i.e., astrocytes, oligodendrocytes, and ependymocytes). Astrocytes may give rise to astrocytomas (ASTROCYTOMA) or glioblastoma multiforme (see GLIOBLASTOMA). Oligodendrocytes give rise to oligodendrogliomas (OLIGODENDROGLIOMA) and ependymocytes may undergo transformation to become EPENDYMOMA; CHOROID PLEXUS NEOPLASMS; or colloid cysts of the third ventricle. (From Escourolle et al., Manual of Basic Neuropathology, 2nd ed, p21) Glial Cell Tumors,Malignant Glioma,Mixed Glioma,Glial Cell Tumor,Glioma, Malignant,Glioma, Mixed,Gliomas,Gliomas, Malignant,Gliomas, Mixed,Malignant Gliomas,Mixed Gliomas,Tumor, Glial Cell,Tumors, Glial Cell
D006801 Humans Members of the species Homo sapiens. Homo sapiens,Man (Taxonomy),Human,Man, Modern,Modern Man
D000230 Adenocarcinoma A malignant epithelial tumor with a glandular organization. Adenocarcinoma, Basal Cell,Adenocarcinoma, Granular Cell,Adenocarcinoma, Oxyphilic,Adenocarcinoma, Tubular,Adenoma, Malignant,Carcinoma, Cribriform,Carcinoma, Granular Cell,Carcinoma, Tubular,Adenocarcinomas,Adenocarcinomas, Basal Cell,Adenocarcinomas, Granular Cell,Adenocarcinomas, Oxyphilic,Adenocarcinomas, Tubular,Adenomas, Malignant,Basal Cell Adenocarcinoma,Basal Cell Adenocarcinomas,Carcinomas, Cribriform,Carcinomas, Granular Cell,Carcinomas, Tubular,Cribriform Carcinoma,Cribriform Carcinomas,Granular Cell Adenocarcinoma,Granular Cell Adenocarcinomas,Granular Cell Carcinoma,Granular Cell Carcinomas,Malignant Adenoma,Malignant Adenomas,Oxyphilic Adenocarcinoma,Oxyphilic Adenocarcinomas,Tubular Adenocarcinoma,Tubular Adenocarcinomas,Tubular Carcinoma,Tubular Carcinomas
D000465 Algorithms A procedure consisting of a sequence of algebraic formulas and/or logical steps to calculate or determine a given task. Algorithm

Related Publications

Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
April 2018, BMC systems biology,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
January 2004, Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
September 2022, Journal of computational biology : a journal of computational molecular cell biology,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
January 2017, BMC bioinformatics,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
May 2021, Bioinformatics (Oxford, England),
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
January 2013, PloS one,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
September 2012, BMC systems biology,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
January 2022, IEEE/ACM transactions on computational biology and bioinformatics,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
December 2014, Neural computation,
Christina Backes, and Alexander Rurainski, and Gunnar W Klau, and Oliver Müller, and Daniel Stöckel, and Andreas Gerasch, and Jan Küntzer, and Daniela Maisel, and Nicole Ludwig, and Matthias Hein, and Andreas Keller, and Helmut Burtscher, and Michael Kaufmann, and Eckart Meese, and Hans-Peter Lenhof
May 2009, Journal of computational biology : a journal of computational molecular cell biology,
Copied contents to your clipboard!