Bocker S.,Friedrich - Schiller University of Jena |
Bocker S.,Jena Center for Bioinformatics |
Briesemeister S.,University of Tubingen |
Algorithmica (New York) | Year: 2011
The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of ||, where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying k ≤ 25 |V|. In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title "Exact algorithms for cluster editing: Evaluation and experiments" in the Proceedings of the 7th Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.) © 2009 Springer Science+Business Media, LLC.
Bcker S.,Friedrich - Schiller University of Jena |
Bcker S.,Jena Center for Bioinformatics |
Bui Q.B.A.,Friedrich - Schiller University of Jena |
Truss A.,Friedrich - Schiller University of Jena
Theoretical Computer Science | Year: 2011
In this paper, we deal with restoring missing information in molecule databases: Many data formats only store the atoms' configuration but omit bond multiplicities. As this information is essential for various applications in chemistry, we consider the problem of recovering bond type information using a scoring function for the possible valences of each atomthe Bond Order Assignment problem. We show that the Bond Order Assignment is NP-hard, and its maximization version is MAX SNP-hard. We then give two exact fixed-parameter algorithms for the problem, where bond orders are computed via dynamic programming on a tree decomposition of the molecule graph. We evaluate our algorithm on a set of real molecule graphs and find that it works fast in practice. © 2010 Elsevier B.V. All rights reserved.
Gorlich D.,Jena Center for Bioinformatics |
Gorlich D.,Friedrich - Schiller University of Jena |
Artmann S.,Frege Center for Structural science |
Artmann S.,Friedrich - Schiller University of Jena |
And 2 more authors.
Biochimica et Biophysica Acta - General Subjects | Year: 2011
Background: We consider cells as biological systems that process information by means of molecular codes. Many studies analyze cellular information processing exclusively in syntactic terms (e.g., by measuring Shannon entropy of sets of macromolecules), and abstract completely from semantic aspects that are related to the meaning of molecular information. Methods: This mini-review focusses on semantic aspects of molecular information, particularly on codes that organize the semantic dimension of molecular information. First, a general conceptual framework for describing molecular information is proposed. Second, some examples of molecular codes are presented. Third, a mathematical approach that makes the identification of molecular codes in reaction networks possible, is developed. Results: By combining a systematic conceptual framework for describing molecular information and a mathematical approach to identify molecular codes, it is possible to give a formally consistent and empirically adequate model of the code-based semantics of molecular information in cells. General significance: Research on the semantics of molecular information is of great importance particularly to systems biology since molecular codes embedded in systems of interrelated codes govern main traits of cells. Describing cells as semantic systems may thus trigger new experiments and generate new insights into the fundamental processes of cellular information processing. This article is part of a Special Issue entitled Systems Biology of Microorganisms. © 2011 Elsevier B.V. All rights reserved.
Gruenert G.,Friedrich - Schiller University of Jena |
Ibrahim B.,German Cancer Research Center |
Lenser T.,Friedrich - Schiller University of Jena |
Lenser T.,Jena Center for Bioinformatics |
And 6 more authors.
BMC Bioinformatics | Year: 2010
Background: We suggest a new type of modeling approach for the coarse grained, particle-based spatial simulation of combinatorially complex chemical reaction systems. In our approach molecules possess a location in the reactor as well as an orientation and geometry, while the reactions are carried out according to a list of implicitly specified reaction rules. Because the reaction rules can contain patterns for molecules, a combinatorially complex or even infinitely sized reaction network can be defined.For our implementation (based on LAMMPS), we have chosen an already existing formalism (BioNetGen) for the implicit specification of the reaction network. This compatibility allows to import existing models easily, i.e., only additional geometry data files have to be provided.Results: Our simulations show that the obtained dynamics can be fundamentally different from those simulations that use classical reaction-diffusion approaches like Partial Differential Equations or Gillespie-type spatial stochastic simulation. We show, for example, that the combination of combinatorial complexity and geometric effects leads to the emergence of complex self-assemblies and transportation phenomena happening faster than diffusion (using a model of molecular walkers on microtubules). When the mentioned classical simulation approaches are applied, these aspects of modeled systems cannot be observed without very special treatment. Further more, we show that the geometric information can even change the organizational structure of the reaction system. That is, a set of chemical species that can in principle form a stationary state in a Differential Equation formalism, is potentially unstable when geometry is considered, and vice versa.Conclusions: We conclude that our approach provides a new general framework filling a gap in between approaches with no or rigid spatial representation like Partial Differential Equations and specialized coarse-grained spatial simulation systems like those for DNA or virus capsid self-assembly. © 2010 Gruenert et al; licensee BioMed Central Ltd.