Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Characterization of ergodic hidden Markov sources
No full textAn algebraic criterim for the ergodicity of discrete random sources is presented. For finite-dimensional sources, which contain hidden Markov sources as a subclass, the criterium can be effectively computed. This result is obtained on the background of a novel, elementary theory of discrete random sources, which is based on linear spaces spanned by word functions, and linear operators on these spaces. An outline of basic elements of this theory is provided
A Fast 2-Approximation of Minimum Manhattan Networks
No full textGiven a set P of n points in the plane, a Manhattan network of P is a network that contains a rectilinear shortest path between every pair of points of P. A minimum Manhattan network of P is a Manhattan network of minimum total length. It is unknown whether it is NP-hard to construct a minimum Manhattan network. The best approximations published so far are a combinatorial 3-approximation algorithm in time O(n log n), and an LP-based 2-approximation algorithm. We present a new combinatorial 2-approximation for this problem in time O(n log n)
Inference of an Oscillating Model for the Yeast Cell Cycle
No full textHigh-throughput techniques allow to measure hundreds of cell components simultaneously. The inference of interactions between cell components from these experimental data facilitates the understanding of complex regulatory processes. Differential equations have been established to model the dynamic behavior of these regulatory networks quantitatively. Usually traditional regression methods to estimate model parameters fail in this setting, since they overfit the data. This is even the case, if the focus is on modeling subnetworks of at most a few tens of components. In a Bayesian learning approach, this problem is avoided by a restriction of the search space with prior probability distributions over model parameters. This paper combines both, differential equation models and a Bayesian approach. We model the periodic behavior of proteins involved in the cell cycle of the budding yeast {it Saccharomyces cerevisiae} with differential equations, which are based on chemical reaction kinetics. One property of these systems is that they usually converge to a steady state, and lots of efforts have been made to explain the observed periodic behavior. We introduce an approach to infer an oscillating network from experimental data. First, an oscillating core network is learned. This is extended by further components by using a Bayesian approach in a second step. A specifically designed hierarchical prior distribution over interaction strengths prevents overfitting and drives the solutions to sparse networks with only a few significant interactions. We apply our method to a simulated and a real world dataset and reveal main regulatory interactions. Moreover, we are able to reconstruct the dynamic behavior of the network
Simultaneous Geometric Graph Embeddings
No full textWe consider the following problem known as simultaneous geometric graph embedding (SGE). Given a set of planar graphs on a shared vertex set, decide whether the vertices can be placed in the plane in such a way that for each graph the straight-line drawing is planar. We partially settle an open problem of Erten and Kobourov and show that even for two graphs the problem is NP-hard. We also show that the problem of computing the rectilinear crossing number of a graph can be reduced to a simultaneous geometric graph embedding problem; this implies that placing SGE in NP will be hard, since the corresponding question for rectilinear crossing number is a longstanding open problem. However, rather like rectilinear crossing number, SGE can be decided in PSPACE
Schranken für den minimalen orientierten Durchmesser
No full textIn this thesis, we consider the problem of finding an orientation of an undirected graph with minimal diameter. We show a relation between the minimum oriented diameter diam_{min}(G) of an undirected graph and the size gamma(G) of a minimal dominating set, which improves an upper bound discovered by Fomin et al. We show if G is a strongly connected graph, then: diam_{min}(G)leq 4gamma(G). Furthermore, if we have a graph G and a dominating set D , not necessarily a minimal dominating set of G , we show how to construct an orientation H of G in polynomial time fulfilling diam(H)leq 4|D|. Furthermore, we determine the exact upper bound for {C_3,C_4} -free graphs. If G is a strongly connected {C_3,C_4} -free graph, then the following holds: diam_{min}(G)leq 3gamma(G)+1. We consider bidirected graphs and characterize undirected graphs that allow a strongly connected bidirection. We show, that for those graphs a bidirected orientation ar{H} exist with diam(ar{H})leq 10gamma(ar{H})-5
Beschleunigung ausgewählter paralleler Standard Template Library Algorithmen
No full textA diploma thesis presenting a hardware-oriented parallelization of the C++ Standard Template Library. Strategies like thread pooling and thread affinity are used to enable speedups already for small input sizes and to best exploit the underlying hardware. Comparisons with existing approaches are used for evaluations
Local Cuts Revisited
No full textWe present a variant of the local cut generation procedure by Applegate, Bixby, Chvatal and Cook. Unlike the original procedure, our method immediately yields a facet of the projected polytope as the solution of a single LP, without the need of the time-consuming tilting step. Moreover, our facets have big volume in general
A Basic Toolbox for Constrained Quadratic 0/1 Optimization
No full textIn many practical applications, the task is to optimize a non-linear function over a well-studied polytope P as, e.g., the matching polytope or the travelling salesman polytope (TSP). In this paper, we focus on quadratic objective functions. Prominent examples are the quadratic assignment and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems,they have to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvatal and Cook for faster solution of large-scale traveling salesman instances. By extensive experiments, we show that both methods can drastically accelerate the solution of constrained quadratic 0/1 problems
Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses
No full textWe present an algorithm for the calculation of exact ground states of two-dimensional Ising spin glasses with free boundary conditions in at least one direction. Studying spin-glass physics through analyzing their ground-state properties has a long history. Although there exist polynomial-time algorithms for the two-dimensional planar case, where the problem of finding ground states is transformed to a minimum weighted perfect matching problem, the reachable system sizes have been limited both by the needed CPU time and memory requirements. Using Kasteleyn cities, we calculate accurate ground states for huge two-dimensional planar Ising spin-glass lattices (up to 3000x3000 spins) within reasonable time. According to our knowledge, these are the largest sizes currently available. Kasteleyn cities were recently also used by Thomas and Middleton in the context of extended ground states on the torus. Domain walls can be computed using reoptimization. Finally, the correctness of heuristically computed ground states can easily be verified