AG OR/ML - Dr.Stefan Pickl |
AG OR/ML - Dr.Stefan Pickl |
The analysis of DNA expression data is one of the main problems in computational molecular biology which leads to an application of combinatorial and algorithmic techniques. DNA chips have ignited the imagination of theorists for over a decade. The data set we regard are taken from experiments with DNA microarray chips.
At first we present an approach to identify certain regions on the chip. This regions correlates with a certain behavior of the gene. The analysis of gene expression then leads to the information whether a gene is expressed or not and, if two different expression states of the same organism of particular genes differs in both states (so called fold-change). Molecular biologists speak of gene expression patterns.
The underlying data sets of such gene expression patterns consist of time-series experiments. The range of the pixel intensity on the DNA chip is represented by the interval [1,65000]. Several algorithms were proposed to construct a certain model out of time series data of mRNA and protein concentrations (Minimum Weight Solutions to Linear Equations MWSLE). By that approach the problem can be solved in polynomial time, if the number of genes influencing the expression of the target gene is constant (Chen et al). If this number is not constant (as in reality) the MWSLE is NP-complete.
The modelling approach of de Hoon et al is based on Chen et al . They use only mRNA measurements and their approach does not need the same mentioned preconditions as the two algorithms proposed by Chen et al . De Hoon et al determine the number and places of the nonzero parameters by the so called Akaikes Information Criterion. We present a more flexible approach which exploits strongly combinatorial information.
At the end we present a discrete approximation problem and a solution for the mixed integer problem which occur when we restrict the solution space.
