Many problems in bioinformatics are inference problems, that is, the problem objective is to infer something based upon a limited amount of information. In this work we explore two different inference problems in bioinformatics. The first problem is inferring the structure of signal transduction networks from interactions between pairs of cellular components. We present two contributions towards the solution to this problem: an mixed integer program that produces and exact solution, and an implementation of an approximation algorithm in Java that was originally described by DasGupta et al. An exact solution is obtained for a problem instance consisting of real data. The second problem this thesis examines is the problem of inferring complete haplotypes from informative SNPs. In this work we describe two variations of the linear algebraic method for haplotype prediction and tag SNP selection: Two different variants of the algorithm are described and implemented, and the results summarized.

The general goal of this project was to use computational biology to understand signal transduction mechanisms in prokaryotes. Its specific focus was to characterize the cytoplasmic domain of methyl-accepting chemotaxis proteins (MCP_CD), a protein domain central to the function of chemotaxis, the most complex signaling network in prokaryotes. Chemotaxis enables cells to sense and respond to multiple external and internal stimuli by actively navigating to an optimal environment. MCP_CD is a central part of this circuit, but its coiled coil structure is difficult to analyze using traditional tools of computational biology. In this project, a new method for analysis of the domain was developed and used to gain insight into its function and evolution. Research advance 1: Characterization of the MCP_CD protein domain. Before this work, MCP_CD was known to have two distinct functional regions: the signaling region that activates the histidine kinase CheA and the methylation region where adaptation enzymes CheB and CheR store information about recent stimuli. The result of this project is classification of ~2000 MCP_CDs into twelve subfamilies. The unique mechanism of evolution of the domain has been clarified and precise boundaries of the adaptation and signaling regions determined. A new functional region, the flexible bundle subdomain, was identified and its contribution to the signaling mechanism elucidated by analysis of conserved sequence features. Conserved and variable sequence features in the adaptation and signaling subdomains led to a better understanding of the evolutionary history of the adaptation mechanism and of alternative higher-order arrangements of receptors within the membrane. Research advance 2: Development of a sensor / kinase correlation algorithm to couple diverse MCP_CD and kinase subfamilies. The receptor diversity discovered in this work is complemented by diversity in the kinases with which they interact. In this work, an algorithm was developed to associate receptor / kinase pairs which facilitated understanding of the function and evolution of chemotaxis. Research advance 3: Development of Cheops, a database of chemotaxis pathways. The Cheops (Chemotaxis operons) database presents the results of the sensor / kinase correlation algorithm and the information about receptor and kinase diversity in an integrated and intuitive way.

Lebende Organismen sind komplexe Systeme von miteinander interagierenden Komponen- ten. Ein entscheidender Schritt zum besseren Verständnis solcher biologischen Systeme ist die Erstellung biologischer Netzwerke, welche unser bisheriges Verständnis dieser Systeme widerspiegelt. Verschiedene Ansätze zur Netzwerk-Rekonstruktion unterscheiden sich zwar in ihrem Zweck und ihrer Komplexität, allerding haben sie ein gemeinsames Ziel: die Übersetzung des biologischen Wissens in ein mathematisches Modell zur Aufdeckung von Inkonsistenzen und Wissenslücken innerhalb der Rekonstruktionen durch computerbasierte Analysen. Während es für metabolische Netzwerke bereits gut entwickelte Rekonstruktionsansätze gibt, existieren derzeit nur wenige Ansätze für Signal-Transduktionsnetzwerke. In dieser Arbeit stelle ich eine Methode zur systematischen und komprimierten Rekonstruk- tion von Signal-Transduktionsnetzwerken vor – rxncon. Diese Methode hat zwei grundlegende Aspekte: Einerseits haben wir eine Sprache zur Rekonstruktion biologischer Netzwerke entwickelt, die die Probleme kombinatorischer Komplexität durch die Kombination von Zuständen während des Rekonstruktionsprozesses angeht. Diese kombinatorische Komplexität wird durch die Verwendung kontextfreier Grammatik und der Beschreibung der Daten auf derselben Ebene wie experimentelle Erkenntnisse umgangen. Andererseits haben wir eine computerbasierte Struktur zur Interpretation und zum Export entwickelt, welche es ermöglicht das rekonstruierte Wissen in mathematische Modelle und unterschiedliche Visualisierungsformate zu übersetzen. Dadurch sind wir in der Lage, erstens Signal-Transduktionsnetzwerke detailliert zu rekon- struieren, zweitens diese Netzwerke in ausführbare Boolesche Modelle zur Verbesserung, Evaluation und Validierung dieser Netzwerke zu übersetzen und drittens diese Netzwerke als Regelbasierte Modelle zu exportieren. Daher ermöglicht rxncon die Rekonstruktion, Validierung und Simulation von umfangreichen Signal-Transduktionsnetzwerken und verbindet dadurch den Rekonstruktionsprozess mit klassischen mathematischen Modellierungsansätzen. / Living organisms are complex systems of interacting components. A crucial step to understand those complex biological systems is the construction of biological networks that re ect our current knowledge of the system. The scope and coverage of different network reconstructions can differ, but they have one aim in common – to convert the knowledge into a mathematical model enabling computational analysis to nd possible inconsistencies and gaps. While reconstruction methods for metabolic networks are well established, only a few methods exist for reconstructing cellular signal- transduction networks. In this thesis, I present a method – rxncon – enabling a systematised and condensed reconstruction of signal-transduction networks. This method has two aspects. On the one hand, we developed a language for reconstructing biological networks. The language addresses the issue, that states are combined in signal-transduction networks, which create a large number of speci c states, generating highly complex structures. Due to the context-free grammar in the language and the description of the data on the same level of detail as biological ndings we can largely avoid the combinatorial complexity. On the other hand, we developed a framework for interpreting and exporting this knowledge into different mathematical models and visualisation formats, enabling a work ow to: 1) reconstruct mechanistic detailed signal-transduction network, 2) convert them into an executable Boolean model for evaluation, validation and improvement of the network and 3) export the reconstructed model into a rule-based model. Hence, rxncon has the potential to reconstruct, validate and simulate large-scale signalling networks – bridging large scale network reconstruction and classical mathematical modelling approaches.