In der klassischen Komplexitätstheorie unterscheiden wir zwischen der Klasse P von in Polynomialzeit lösbaren Problemen, und der Klasse NP-schwer von Problemen bei denen die allgemeine Annahme ist, dass diese nicht in Polynomialzeit lösbar sind. Allerdings sind viele Probleme, die wir lösen möchten, NP-schwer. Gleichzeitig besteht eine große Diskrepanz zwischen den empirisch beobachteten und den festgestellten worst-case Laufzeiten. Es ist bekannt, dass Vorverarbeitung oder Datenreduktion auf realen Instanzen zu Laufzeitverbesserungen führt. Hier stoßen wir an die Grenze der klassischen Komplexitätstheorie. Der Fokus dieser Arbeit liegt auf Vorverarbeitungsalgorithmen für NP-schwere Probleme. Unser Ziel ist es, bestimmte Instanzen eines NP-schweren Problems vorverarbeiten zu können, indem wir die Struktur betrachten. Genauer gesagt, für eine gegebene Instanz und einen zusätzlichen Parameter l, möchten wir in Polynomialzeit eine äquivalente Instanz berechnen, deren Größe und Parameterwert nur durch eine Funktion im Parameterwert l beschränkt ist. In der parametrisierten Komplexitätstheorie heißen diese Algorithmen Kernelisierung. Wir werden drei NP-schwere Graphenprobleme betrachten, nämlich Vertex Cover, Edge Dominating Set und Subset Feedback Vertex Set. Für Vertex Cover werden wir bekannte Ergebnisse für Kernelisierungen vereinheitlichen, wenn der Parameter die Größe einer Entfernungsmenge zu einer gegebenen Graphklasse ist. Anschließend untersuchen wir die Kernelisierbarkeit von Edge Dominating Set. Es stellt sich heraus, dass die Kernelisierbarkeit deutlich komplexer ist. Dennoch klassifizieren wir die Existenz einer polynomiellen Kernelisierung, wenn jeder Graph in der Graphklasse eine disjunkte Vereinigung von konstant großen Komponenten ist. Schließlich betrachten wir das Subset Feedback Vertex Set Problem und zeigen, dass es eine randomisierte polynomielle Kernelisierung hat, wenn der Parameter die Lösungsgröße ist. / In classical complexity theory, we distinguish between the class P, of polynomial-time solvable problems, and the class NP-hard, of problems where the widely-held belief is that we cannot solve these problems in polynomial time. Unfortunately, many of the problems we want to solve are NP-hard. At the same time, there is a large discrepancy between the empirically observed running times and the established worst-case bounds. Using preprocessing or data reductions on real-world instances is known to lead to huge improvements in the running time. Here we come to the limits of classical complexity theory. In this thesis, we focus on preprocessing algorithms for NP-hard problems. Our goal is to find ways to preprocess certain instances of an NP-hard problem by considering the structure of the input instance. More precisely, given an instance and an additional parameter l, we want to compute in polynomial time an equivalent instance whose size and parameter value is bounded by a function in the parameter l only. In the field of parameterized complexity, these algorithms are called kernelizations. We will consider three NP-hard graph problems, namely Vertex Cover, Edge Dominating Set, and Subset Feedback Vertex Set. For Vertex Cover, we will unify known results for kernelizations when parameterized by the size of a deletion set to a specified graph class. Afterwards, we study the existence of polynomial kernelizations for Edge Dominating Set when parameterized by the size of a deletion set to a graph class. We point out that the existence of polynomial kernelizations is much more complicated than for Vertex Cover. Nevertheless, we fully classify the existence of polynomial kernelizations when every graph in the graph class is a disjoint union of constant size components. Finally, we consider graph cut problems, especially the Subset Feedback Vertex Set problem. We show that this problem has a randomized polynomial kernelization when the parameter is the solution size.

Proteins adopt three-dimensional structures which serve as a starting point to understand protein function and their evolutionary ancestry. It is unclear how proteins fold in vivo and how this process can be recreated in silico in order to predict protein structure from sequence. Contact maps are a possibility to describe whether two residues are in spatial proximity and structures can be derived from this simplified representation. Coevolution or supervised machine learning techniques can compute contact maps from sequence: however, these approaches only predict sparse subsets of the actual contact map. It is shown that the composition of these subsets substantially influences the achievable reconstruction quality because most information in a contact map is redundant. No strategy was proposed which identifies unique contacts for which no redundant backup exists. The StructureDistiller algorithm quantifies the structural relevance of individual contacts and identifies crucial contacts in protein structures. It is demonstrated that using this information the reconstruction performance on a sparse subset of a contact map is increased by 0.4 A, which constitutes a substantial performance gain. The set of the most relevant contacts in a map is also more resilient to false positively predicted contacts: up to 6% of false positives are compensated before reconstruction quality matches a naive selection of contacts without any false positive contacts. This information is invaluable for the training to new structure prediction methods and provides insights into how robustness and information content of contact maps can be improved. In literature, the relevance of two types of residues for in vivo folding has been described. Early folding residues initiate the folding process, whereas highly stable residues prevent spontaneous unfolding events. The structural relevance score proposed by this thesis is employed to characterize both types of residues. Early folding residues form pivotal secondary structure elements, but their structural relevance is average. In contrast, highly stable residues exhibit significantly increased structural relevance. This implies that residues crucial for the folding process are not relevant for structural integrity and vice versa. The position of early folding residues is preserved over the course of evolution as demonstrated for two ancient regions shared by all aminoacyl-tRNA synthetases. One arrangement of folding initiation sites resembles an ancient and widely distributed structural packing motif and captures how reverberations of the earliest periods of life can still be observed in contemporary protein structures.

We derive the amplitude expansion for a phase-field-crystal (APFC) model that captures the basic physics of magneto-structural interactions. The symmetry breaking due to magnetization is demonstrated, and the characterization of the magnetic anisotropy for a bcc crystal is provided. This model enables a convenient coarse-grained description of crystalline structures, in particular when considering the features of the APFC model combined with numerical methods featuring inhomogeneous spatial resolution. This is shown by addressing the shrinkage of a spherical grainwithin amatrix, chosen as a prototypical system to demonstrate the influence of different magnetizations. These simulations serve as a proof of concept for the modeling of manipulation of dislocation networks and microstructures in ferromagnetic materials within the APFC model.

Bei der lichtinduzierten Oxidation von Wasser im Photosystem II (PSII) werden zwei wassermoleküle im katalytischen Zyklus des Metallclusters (Mn4CaO5) benötigt, und vier Protonen aus dem Cluster in den Lumen abgegeben. Daher ist es für das Verständnis des Mechanismus´ der Wasseroxidation von entscheidender Bedeutung, die Veränderung der Protonierungszustände am cluster während der Katalyse zu untersuchen. Hierbei sollten sowohl die Wasserkanäle für die Zuführung der Substratwassermoleküle als auch die Transportwege für die Freisetzung der Protonen untersucht werden. Deshalb wurde in meiner ersten Veröffentlichung ein neues Protokoll entwickelt, um einzelne große Kristalle von dPSII mit einer Länge von ~3 mm in der Längsachse zu züchten. Diese Kristalle mit einer Auflösung von ca. 8 Å gemessen. Um eine höhere Auflösung zu erzielen, ist die Verbesserung der Kristallqualität essenziell. Daher wurde in meiner zweiten Veröffentlichung die Struktur des Detergens-Protein-Komplexes von dPSII mit βDM, durch Anwendung von SANS in Kombination mit SAXS untersucht. Die Ergebnisse zeigten, dass βDM eine monomolekulare Schicht um dPSII bildet. Darüber hinaus konnten freie Mizellen von βDM in der Lösung nachgewiesen werden. Damit ist eine weitere Optimierung der βDM-Konzentration in der Proteinlösung erforderlich, um die Bildung von freien Mizellen zu minimieren. In meiner dritten Veröffentlichung wurde die strukturelle Dynamik in den Wasserkanälen, während des S2-S3 Übergangs mit Hilfe der XFEL untersucht. Ein Datensatz mit einer hohen Auflösung von 1,89 Å wurde durch die Zusammenführung von Daten gewonnen, die während des S2-S3 Übergangs gesammelt wurden. In Anbetracht der Analyse der zusammengeführten Daten und der einzelnen Zeitpunkte, die während des S2-S3 Übergangs gesammelt wurden, ist es wahrscheinlich, dass ein Substratwasser durch den O1-Kanal geliefert wird. Im Gegensatz dazu wird ein Proton aus dem Cluster durch den Cl1 Transportweg in Richtung Lumen freigesetzt. / The light-induced oxidation of water in Photosystem II (PSII) requires incorporating two water molecules in the catalytic cycle of the active metal cluster (Mn4CaO5). Furthermore, four protons are released towards the bulk from the cluster. Therefore, tracking the change of protonation states at the active catalytic site and the surrounding protein side chains during catalysis and elucidating the pathways of water substrate insertion and proton release are crucial to understanding the water oxidation mechanism. Therefore, in the first study of my work, a new protocol was developed to grow single large dPSIIcc crystals with a length of ~3 mm in the long axis. These crystals, soaked in D2O containing buffer, diffracted to about 8 Å resolution. Improving the crystal quality is crucial for achieving a better resolution. Consequently, in the second study of my work, the structure of the detergent-protein complex of βDM-dPSIIcc has been investigated by applying SANS in combination with SAXS. The results showed that βDM is forming a monomolecular layer around the dimeric PSII core complex (dPSIIcc). Moreover, the SAXS data detected a peak assigned to the free micelles of βDM. These results raise the necessity to optimize the βDM concentration in the protein solution to avoid the possible excess of free micelles. In the third study of my work, the structural dynamics in the water channels connecting the cluster to the lumen during the S2  S3 transition were investigated using serial femtosecond XFEL. A high-resolution data set was obtained at a resolution of 1.89 Å by combining data collected at RT. Considering the analysis of the combined data and the individual time points collected during the S2  S3 transition, it is likely that the substrate water insertion into the open coordination site of the Mn1 ion is delivered through the O1 channel. In contrast, a proton from the cluster is released towards the bulk through the Cl1 A channel.

Background: Structure-based drug repositioning has emerged as a promising alternative to conventional drug development. Regardless of the many success stories reported over the past years and the novel breakthroughs on the AI-based system AlphaFold for structure prediction, the availability of structural data for protein–drug complexes remains very limited. Whereas the chemical libraries contain millions of drug compounds, the vast majority of them do not have structures to crystallized targets,and it is, therefore, impossible to characterize their binding to targets from a structural view. However, the concept of building blocks offers a novel perspective on the structural problem. A drug compound is considered a complex of small chemical blocks or fragments, which confer the relevant properties to the drug and have a high proportion of functional groups involved in protein binding. Based on this, we propose a novel approach to expand the scope of structure-based repositioning approaches by transferring the structural knowledge from a fragment to a compound level. - Results: We fragmented over 100,000 compounds in the Protein Data Bank (PDB) and characterized the structural binding mode of 153,000 fragments to their crystallized targets. Using the fragment’s data, we were able to artificially reconstruct the binding mode of over 7,800 complexes between ChEMBL compounds and their known targets, for which no structural data is available. We proved that the conserved binding tendency of fragments, when binding to the same targets, highly influences the drug’s binding specificity and carries the key information to reconstruct full drugs binding mode. Furthermore, our approach was able to reconstruct multiple compound-target pairs at optimal thresholds and high similarity to the actual binding mode. - Conclusions: Such reconstructions are of great value and benefit structure-based drug repositioning since they automatically enlarge the technique’s scope and allow exploring the so far ‘unexplored compounds’ from a structural perspective. In general, the transfer of structural information is a promising technique that could be applied to any chemical library, to any compound that has no crystal structure available in PDB, and even to transfer any other feature that may be relevant for the drug discovery process and that due to data limitations is not yet fully available. In that sense, the results of this work document the full potential of structure-based screening even beyond PDB.

Projection is the problem of checking whether the execution of a given sequence of actions will achieve its goal starting from some initial state. In this paper, we study a setting where we combine a two-dimensional Description Logic of context (ConDL) with an action formalism. We choose a well-studied ConDL where both: the possible states of a dynamical system itself (object level) and also different context-dependent views on this system state (context level) are organised in relational structures and can be described using usual DL constructs. To represent how such a system and its views evolve we introduce a suitable action formalism. It allows to describe change on both levels. Furthermore, the observable changes on the object level due to an action execution can also be contextdependent. We show that the formalism is well-behaved in the sense that projection has the same complexity as standard reasoning tasks in case ALCO is the underlying DL.

Although being quite inexpressive, the description logic (DL) FL₀, which provides only conjunction, value restriction and the top concept as concept constructors, has an intractable subsumption problem in the presence of terminologies (TBoxes): subsumption reasoning w.r.t. acyclic FL₀ TBoxes is coNP-complete, and becomes even ExpTime-complete in case general TBoxes are used. In the present paper, we use automata working on infinite trees to solve both standard and non-standard inferences in FL₀ w.r.t. general TBoxes. First, we give an alternative proof of the ExpTime upper bound for subsumption in FL₀ w.r.t. general TBoxes based on the use of looping tree automata. Second, we employ parity tree automata to tackle non-standard inference problems such as computing the least common subsumer and the difference of FL₀ concepts w.r.t. general TBoxes.

The desire of builders and architects of maximum transparency and homogeneous surfaces in glass façades and glass structures extends to interior all-glass applications such as glass partitions or all-glass doors. In conventional glass systems the interconnections are performed by eye-catching fittings and clamping details that reduce the transparency and disturb the aesthetics. Novel glass–plastic-composite panels show a significantly reduced self-weight by composition of a polymer polymethylmethacrylate (PMMA) interlayer core and cover layers of thin glass. The innovative composites show high structural performance with optical properties of conventional glass. The panels allow for a direct connection into the thick PMMA interlayer core with the supporting structure or other panels. Such an integrated connection design reduces stress concentrations and allows for the development of small and unobtrusive fittings. Different integrated connections for the glass–plastic-composite panels have been designed and investigated. This article presents an experimental study on different connections, such as mechanically fastened and adhesively integrated, tested under tensile loading. Based on video analyses, crack progressions and failure mechanisms are evaluated and discussed in detail. The tests investigate temperature effects as well as the influence of the interlayer core thickness and glass type of the cover layers in varying build-ups. The comprehensive evaluation includes a description of the mechanical load-bearing behaviour in form of load versus displacement graphs as well as an investigation of crack progression and failure mechanisms for the final assessment. The results from this experimental study elucidate the structural characteristics of integrated connections in glass–plastic-composite panels under tensile loading and represent a basis for the ongoing development of real application fittings.

Armut ist kein statisches, isoliertes oder nur materielles Phänomen, sondern reproduziert sich strukturell und mit verstärkter Ausprägung in den nächsten Generationen. Ihre Ursache ist nicht rein wirtschaftlich, sondern die Konsequenz eines langen historischen Prozesses der Negierung und Ausbeutung, auch rassiell und geschlechtsspezifisch bedingt. Daher muss man das Problem der Indianer in Bolivien als Ergebnis der historischen und sozialen Verachtung und Annullierung von Seiten der Elite und Oligarchie verstehen, die ihre politische und ökonomische Teilnahme begrenzt haben. Leider hat dabei sogar die Bildung als Instrument gedient, um das dominante System zu rechtfertigen und die indianische Bevölkerung abzuwerten. Als Konsequenz dieser rassiellen Diskriminierung und Marginalisierung in Verbindung mit der wachsenden Armut ist ein sehr komplexes Phänomen entstanden, das man strukturelle Gewalt nennt. Unter der Betrachtung solcher Bedingungen im bolivianischen Kontext wird mit dieser Arbeit der Versuch unternommen, neue Bildungspolitiken vorzuschlagen, die als Fundament für eine bessere und gleichmäßige Verteilung der Möglichkeiten zur menschlichen Entwicklung und für die Konstruktion einer demokratischen Gesellschaft (Nation Building Prozess) dienen könnten. Dafür wird die Philosophie des Ordens der Salesianer als Referenz für neue Ansätze gewählt, bei denen die Bildung ein gemeinsames Konzept des Landes formuliert, das Vorurteile, Stereotypen und innere Grenzen, die sich von Generation zu Generation übertragen, ausräumt. Die Bedeutung der Bildung soll mit anderen Worten in deren Nutzung als Werkzeug für die Errichtung einer Friedenskultur liegen, die auf Toleranz, Solidarität und den Menschenrechten basiert, wobei die zwischeninstitutionelle Annäherung, Kooperation und der gegenseitige Austausch von Informationen und Erfahrungen in der Bildungsgemeinschaft (z.B. zwischen Don Bosco, Unicef oder Unesco) eine wichtige Rolle spielen.

Armut ist kein statisches, isoliertes oder nur materielles Phänomen, sondern reproduziert sich strukturell und mit verstärkter Ausprägung in den nächsten Generationen. Ihre Ursache ist nicht rein wirtschaftlich, sondern die Konsequenz eines langen historischen Prozesses der Negierung und Ausbeutung, auch rassiell und geschlechtsspezifisch bedingt. Daher muss man das Problem der Indianer in Bolivien als Ergebnis der historischen und sozialen Verachtung und Annullierung von Seiten der Elite und Oligarchie verstehen, die ihre politische und ökonomische Teilnahme begrenzt haben. Leider hat dabei sogar die Bildung als Instrument gedient, um das dominante System zu rechtfertigen und die indianische Bevölkerung abzuwerten. Als Konsequenz dieser rassiellen Diskriminierung und Marginalisierung in Verbindung mit der wachsenden Armut ist ein sehr komplexes Phänomen entstanden, das man strukturelle Gewalt nennt. Unter der Betrachtung solcher Bedingungen im bolivianischen Kontext wird mit dieser Arbeit der Versuch unternommen, neue Bildungspolitiken vorzuschlagen, die als Fundament für eine bessere und gleichmäßige Verteilung der Möglichkeiten zur menschlichen Entwicklung und für die Konstruktion einer demokratischen Gesellschaft (Nation Building Prozess) dienen könnten. Dafür wird die Philosophie des Ordens der Salesianer als Referenz für neue Ansätze gewählt, bei denen die Bildung ein gemeinsames Konzept des Landes formuliert, das Vorurteile, Stereotypen und innere Grenzen, die sich von Generation zu Generation übertragen, ausräumt. Die Bedeutung der Bildung soll mit anderen Worten in deren Nutzung als Werkzeug für die Errichtung einer Friedenskultur liegen, die auf Toleranz, Solidarität und den Menschenrechten basiert, wobei die zwischeninstitutionelle Annäherung, Kooperation und der gegenseitige Austausch von Informationen und Erfahrungen in der Bildungsgemeinschaft (z.B. zwischen Don Bosco, Unicef oder Unesco) eine wichtige Rolle spielen.