Integer linear programming based solutions for construction of biological networks

Download

index.pdf

Date

2014

Author

Eren Özsoy, Öykü

Metadata

Show full item record

Item Usage Stats

278
views

110
downloads

Inference of gene regulatory or signaling networks from perturbation experiments and gene expression assays is one of the challenging problems in bioinformatics. Recently, the inference problem has been formulated as a reference network editing problem and it has been show that finding the minimum number of edit operations on a reference network in order to comply with perturbation experiments is an NP-complete problem. In this dissertation, we propose linear programming based solutions for reconstruction of biological networks. We propose an integer linear programming (ILP) model for reconstruction of signaling networks from RNAi data and a reference network. The ILP model guarantees the optimal solution; however, is practical only for small networks of size 10-15 genes due to computational complexity. In order to scale for large networks, we propose a divide and conquer based heuristic, in which a given reference network is divided into smaller sub-networks that are solved separately and the solutions are merged together to form the solution for the large network. However the solution that we have developed for reconstruction of signaling networks using RNA interference data is not suitable for networks with multiple sources and sinks. In order to handle such networks, we use gene expression data and develop another ILP based graph theoretical method. We validate our proposed approaches on real, semi-synthetic and synthetic data sets, and comparison with the state of the art shows that our proposed approaches are able to scale better.

Subject Keywords

Gene expression, Gene regulatory networks., RNA, Integer programming., Bioinformatics.

URI

http://etd.lib.metu.edu.tr/upload/12617325/index.pdf
https://hdl.handle.net/11511/23571

Collections

Graduate School of Informatics, Thesis

Suggestions

OpenMETU
Core

Mathematical Modeling and Approximation of Gene Expression Patterns Yılmaz, Fatih; Öktem, Hüseyin Avni (2004-09-03) This study concerns modeling, approximation and inference of gene regulatory dynamics on the basis of gene expression patterns. The dynamical behavior of gene expressions is represented by a system of ordinary differential equations. We introduce a gene-interaction matrix with some nonlinear entries, in particular, quadratic polynomials of the expression levels to keep the system solvable. The model parameters are determined by using optimization. Then, we provide the time-discrete approximation of our time...
Partially Observable Gene Regulatory Network Control Without a Boundary on Horizon Erdogdu, Utku; Polat, Faruk; Alhajj, Reda (2012-11-09) Gene regulatory networks (GRNs) govern the protein transcription process in the cell and interactions among genes play a vital role in determining the biosynthesis rate of proteins. By using intervention techniques discovered by biological research it is possible to control a GRN, thus promoting or demoting the expression rate of a certain gene. In this work, this control task is studied in a partially observable setting where interventions lack perfect knowledge of the expression level of all genes. Moreov...
Employing decomposable partially observable Markov decision processes to control gene regulatory networks Erdogdu, Utku; Polat, Faruk; Alhajj, Reda (2017-11-01) Objective: Formulate the induction and control of gene regulatory networks (GRNs) from gene expression data using Partially Observable Markov Decision Processes (POMDPs).
Inference of Gene Regulatory Networks Via Multiple Data Sources and a Recommendation Method Ozsoy, Makbule Gulcin; Polat, Faruk; Alhajj, Reda (2015-11-12) Gene regulatory networks (GRNs) are composed of biological components, including genes, proteins and metabolites, and their interactions. In general, computational methods are used to infer the connections among these components. However, computational methods should take into account the general features of the GRNs, which are sparseness, scale-free topology, modularity and structure of the inferred networks. In this work, observing the common aspects between recommendation systems and GRNs, we decided to ...
Comparing Clustering Techniques for Real Microarray Data Purutçuoğlu Gazi, Vilda (2012-08-29) The clustering of genes detected as significant or differentially expressed provides useful information to biologists about functions and functional relationship of genes. There are variant types of clustering methods that can be applied in genomic data. These are mainly divided into the two groups, namely, hierarchical and partitional methods. In this paper, as the novelty, we perform a detailed clustering analysis for the recently collected boron microarray dataset to investigate biologically more interes...

Citation Formats

Ö. Eren Özsoy, “Integer linear programming based solutions for construction of biological networks,” Ph.D. - Doctoral Program, Middle East Technical University, 2014.