Analysis of Randomised Search Heuristics for Dynamic Optimisation.

Dynamic optimisation is an area of application where randomised search heuristics like evolutionary algorithms and artificial immune systems are often successful. The theoretical foundation of this important topic suffers from a lack of a generally accepted analytical framework as well as a lack of widely accepted example problems. This article tackles both problems by discussing necessary conditions for useful and practically relevant theoretical analysis as well as introducing a concrete family of dynamic example problems that draws inspiration from a well-known static example problem and exhibits a bi-stable dynamic. After the stage has been set this way, the framework is made concrete by presenting the results of thorough theoretical and statistical analysis for mutation-based evolutionary algorithms and artificial immune systems.

Oxidative protein folding in the intermembrane space of human mitochondria.

The mitochondrial intermembrane space hosts a machinery for oxidative protein folding, the mitochondrial disulfide relay. This machinery imports a large number of soluble proteins into the compartment, where they are retained through oxidative folding. Additionally, the disulfide relay enhances the stability of many proteins by forming disulfide bonds. In this review, we describe the mitochondrial disulfide relay in human cells, its components, and their coordinated collaboration in mechanistic detail. We also discuss the human pathologies associated with defects in this machinery and its protein substrates, providing a comprehensive overview of its biological importance and implications for health.

Mutation rate matters even when optimizing monotonic functions.

Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotonic. These functions have the property that whenever only 0-bits are changed to 1, then the objective value strictly increases. Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant c in the mutation probability p(n) = c/n can make a decisive difference. We show that if c < 1, then the (1+1) EA finds the optimum of every such function in Θ(n log n) iterations. For c = 1, we can still prove an upper bound of O(n(3/2)). However, for c ≥ 16, we present a strictly monotonic function such that the (1+1) EA with overwhelming probability needs 2(Ω(n)) iterations to find the optimum. This is the first time that we observe that a constant factor change of the mutation probability changes the runtime by more than a constant factor.

A two-step mitochondrial import pathway couples the disulfide relay with matrix complex I biogenesis.

Mitochondria critically rely on protein import and its tight regulation. Here, we found that the complex I assembly factor NDUFAF8 follows a two-step import pathway linking IMS and matrix import systems. A weak targeting sequence drives TIM23-dependent NDUFAF8 matrix import, and en route, allows exposure to the IMS disulfide relay, which oxidizes NDUFAF8. Import is closely surveyed by proteases: YME1L prevents accumulation of excess NDUFAF8 in the IMS, while CLPP degrades reduced NDUFAF8 in the matrix. Therefore, NDUFAF8 can only fulfil its function in complex I biogenesis if both oxidation in the IMS and subsequent matrix import work efficiently. We propose that the two-step import pathway for NDUFAF8 allows integration of the activity of matrix complex I biogenesis pathways with the activity of the mitochondrial disulfide relay system in the IMS. Such coordination might not be limited to NDUFAF8 as we identified further proteins that can follow such a two-step import pathway.

The Orf9b protein of SARS-CoV-2 modulates mitochondrial protein biogenesis.

The severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) expresses high amounts of the protein Orf9b to target the mitochondrial outer membrane protein Tom70. Tom70 serves as an import receptor for mitochondrial precursors and, independently of this function, is critical for the cellular antiviral response. Previous studies suggested that Orf9b interferes with Tom70-mediated antiviral signaling, but its implication for mitochondrial biogenesis is unknown. In this study, we expressed Orf9b in human HEK293 cells and observed an Orf9b-mediated depletion of mitochondrial proteins, particularly in respiring cells. To exclude that the observed depletion was caused by the antiviral response, we generated a yeast system in which the function of human Tom70 could be recapitulated. Upon expression of Orf9b in these cells, we again observed a specific decline of a subset of mitochondrial proteins and a general reduction of mitochondrial volume. Thus, the SARS-CoV-2 virus is able to modulate the mitochondrial proteome by a direct effect of Orf9b on mitochondrial Tom70-dependent protein import.

CLUSTER guide RNAs enable precise and efficient RNA editing with endogenous ADAR enzymes in vivo.

RNA base editing represents a promising alternative to genome editing. Recent approaches harness the endogenous RNA-editing enzyme adenosine deaminase acting on RNA (ADAR) to circumvent problems caused by ectopic expression of engineered editing enzymes, but suffer from sequence restriction, lack of efficiency and bystander editing. Here we present in silico-optimized CLUSTER guide RNAs that bind their target messenger RNAs in a multivalent fashion, achieve editing with high precision and efficiency and enable targeting of sequences that were not accessible using previous gRNA designs. CLUSTER gRNAs can be genetically encoded and delivered using viruses, and are active in a wide range of cell lines. In cell culture, CLUSTER gRNAs achieve on-target editing of endogenous transcripts with yields of up to 45% without bystander editing. In vivo, CLUSTER gRNAs delivered to mouse liver by hydrodynamic tail vein injection edited reporter constructs at rates of up to 10%. The CLUSTER approach opens avenues for drug development in the field of RNA base editing.

On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation.

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that OneMax is an easiest function with unique optimum while Trap is a hardest. In this paper we extend the analysis of easiest function classes to the contiguous somatic hypermutation (CHM) operator used in artificial immune systems. We define a function MinBlocks and prove that it is an easiest function for the (1+1) EA using CHM, presenting both a runtime and a fixed budget analysis. Since MinBlocks is, up to a factor of 2, a hardest function for standard bit mutations, we consider the effects of combining both operators into a hybrid algorithm. We rigorously prove that by combining the advantages of k operators, several hybrid algorithmic schemes have optimal asymptotic performance on the easiest functions for each individual operator. In particular, the hybrid algorithms using CHM and SBM have optimal asymptotic performance on both OneMax and MinBlocks. We then investigate easiest functions for hybrid schemes and show that an easiest function for a hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator.