@phdthesis{395, abstract = {Autism spectrum disorders (ASD) are a group of genetic disorders often overlapping with other neurological conditions. Despite the remarkable number of scientific breakthroughs of the last 100 years, the treatment of neurodevelopmental disorders (e.g. autism spectrum disorder, intellectual disability, epilepsy) remains a great challenge. Recent advancements in geno mics, like whole-exome or whole-genome sequencing, have enabled scientists to identify numerous mutations underlying neurodevelopmental disorders. Given the few hundred risk genes that were discovered, the etiological variability and the heterogeneous phenotypic outcomes, the need for genotype -along with phenotype- based diagnosis of individual patients becomes a requisite. Driven by this rationale, in a previous study our group described mutations, identified via whole - exome sequencing, in the gene BCKDK – encoding for a key regulator of branched chain amin o acid (BCAA) catabolism - as a cause of ASD. Following up on the role of BCAAs, in the study described here we show that the solute carrier transporter 7a5 (SLC7A5), a large neutral amino acid transporter localized mainly at the blood brain barrier (BBB), has an essential role in maintaining normal levels of brain BCAAs. In mice, deletion of Slc7a5 from the endothelial cells of the BBB leads to atypical brain amino acid profile, abnormal mRNA translation and severe neurolo gical abnormalities. Additionally, deletion of Slc7a5 from the neural progenitor cell population leads to microcephaly. Interestingly, we demonstrate that BCAA intracerebroventricular administration ameliorates abnormal behaviors in adult mutant mice. Furthermore, whole - exome sequencing of patients diagnosed with neurological dis o r ders helped us identify several patients with autistic traits, microcephaly and motor delay carrying deleterious homozygous mutations in the SLC7A5 gene. In conclusion, our data elucidate a neurological syndrome defined by SLC7A5 mutations and support an essential role for t he BCAA s in human bra in function. Together with r ecent studies (described in chapter two) that have successfully made the transition into clinical practice, our findings on the role of B CAAs might have a crucial impact on the development of novel individualized therapeutic strategies for ASD. }, author = {Tarlungeanu, Dora-Clara}, issn = {2663-337X}, pages = {88}, publisher = {Institute of Science and Technology Austria}, title = {{The branched chain amino acids in autism spectrum disorders }}, doi = {10.15479/AT:ISTA:th_992}, year = {2018}, } @phdthesis{418, abstract = {The aim of this thesis was the development of new strategies for optical and optogenetic control of proliferative and pro-survival signaling, and characterizing them from the molecular mechanism up to cellular effects. These new light-based methods have unique features, such as red light as an activator, or the avoidance of gene delivery, which enable to overcome current limitations, such as light delivery to target tissues and feasibility as therapeutic approach. A special focus was placed on implementing these new light-based approaches in pancreatic β-cells, as β-cells are the key players in diabetes and especially their loss in number negatively affects disease progression. Currently no treatment options are available to compensate the lack of functional β-cells in diabetic patients. In a first approach, red-light-activated growth factor receptors, in particular receptor tyrosine kinases were engineered and characterized. Receptor activation with light allows spatio-temporal control compared to ligand-based activation, and especially red light exhibits deeper tissue penetration than other wavelengths of the visible spectrum. Red-light-activated receptor tyrosine kinases robustly activated major growth factor related signaling pathways with a high temporal resolution. Moreover, the remote activation of the proliferative MAPK/Erk pathway by red-light-activated receptor tyrosine kinases in a pancreatic β-cell line was also achieved, through one centimeter thick mouse tissue. Although red-light-activated receptor tyrosine kinases are particularly attractive for applications in animal models due to the deep tissue penetration of red light, a drawback, especially with regard to translation into humans, is the requirement of gene therapy. In a second approach an endogenous light-sensitive mechanism was identified and its potential to promote proliferative and pro-survival signals was explored, towards light-based tissue regeneration without the need for gene transfer. Blue-green light illumination was found to be sufficient for the activation of proliferation and survival promoting signaling pathways in primary pancreatic murine and human islets. Blue-green light also led to an increase in proliferation of primary islet cells, an effect which was shown to be mostly β-cell specific in human islets. Moreover, it was demonstrated that this approach of pancreatic β-cell expansion did not have any negative effect on the β-cell function, in particular on their insulin secretion capacity. In contrast, a trend for enhanced insulin secretion under high glucose conditions after illumination was detected. In order to unravel the detailed characteristics of this endogenous light-sensitive mechanism, the precise light requirements were determined. In addition, the expression of light sensing proteins, OPN3 and rhodopsin, was detected. The observed effects were found to be independent of handling effects such as temperature differences and cytochrome c oxidase dependent ATP increase, but they were found to be enhanced through the knockout of OPN3. The exact mechanism of how islets cells sense light and the identity of the photoreceptor remains unknown. Summarized two new light-based systems with unique features were established that enable the activation of proliferative and pro-survival signaling pathways. While red-light-activated receptor tyrosine kinases open a new avenue for optogenetics research, by allowing non-invasive control of signaling in vivo, the identified endogenous light-sensitive mechanism has the potential to be the basis of a gene therapy-free therapeutical approach for light-based β-cell expansion.}, author = {Gschaider-Reichhart, Eva}, issn = {2663-337X}, pages = {107}, publisher = {Institute of Science and Technology Austria}, title = {{Optical and optogenetic control of proliferation and survival }}, doi = {10.15479/AT:ISTA:th_913}, year = {2018}, } @phdthesis{1127, abstract = {Plant hormone auxin and its transport between cells belong to the most important mechanisms controlling plant development. Auxin itself could change localization of PINs and thereby control direction of its own flow. We performed an expression profiling experiment in Arabidopsis roots to identify potential regulators of PIN polarity which are transcriptionally regulated by auxin signalling. We identified several novel regulators and performed a detailed characterization of the transcription factor WRKY23 (At2g47260) and its role in auxin feedback on PIN polarity. Gain-of-function and dominant-negative mutants revealed that WRKY23 plays a crucial role in mediating the auxin effect on PIN polarity. In concordance, typical polar auxin transport processes such as gravitropism and leaf vascular pattern formation were disturbed by interfering with WRKY23 function. In order to identify direct targets of WRKY23, we performed consequential expression profiling experiments using a WRKY23 inducible gain-of-function line and dominant-negative WRKY23 line that is defunct in PIN re-arrangement. Among several genes mostly related to the groups of cell wall and defense process regulators, we identified LYSINE-HISTIDINE TRANSPORTER 1 (LHT1; At5g40780), a small amino acid permease gene from the amino acid/auxin permease family (AAAP), we present its detailed characterisation in auxin feedback on PIN repolarization, identified its transcriptional regulation, we propose a potential mechanism of its action. Moreover, we identified also a member of receptor-like protein kinase LRR-RLK (LEUCINE-RICH REPEAT TRANSMEMBRANE PROTEIN KINASE PROTEIN 1; LRRK1; At1g05700), which also affects auxin-dependent PIN re-arrangement. We described its transcriptional behaviour, subcellular localization. Based on global expression data, we tried to identify ligand responsible for mechanism of signalling and suggest signalling partner and interactors. Additionally, we described role of novel phytohormone group, strigolactone, in auxin-dependent PIN re-arrangement, that could be a fundament for future studies in this field. Our results provide first insights into an auxin transcriptional network targeting PIN localization and thus regulating plant development. We highlighted WRKY23 transcriptional network and characterised its mediatory role in plant development. We identified direct effectors of this network, LHT1 and LRRK1, and describe their roles in PIN re-arrangement and PIN-dependent auxin transport processes.}, author = {Prat, Tomas}, issn = {2663-337X}, pages = {131}, publisher = {Institute of Science and Technology Austria}, title = {{Identification of novel regulators of PIN polarity and development of novel auxin sensor}}, year = {2017}, } @phdthesis{1155, abstract = {This dissertation concerns the automatic verification of probabilistic systems and programs with arrays by statistical and logical methods. Although statistical and logical methods are different in nature, we show that they can be successfully combined for system analysis. In the first part of the dissertation we present a new statistical algorithm for the verification of probabilistic systems with respect to unbounded properties, including linear temporal logic. Our algorithm often performs faster than the previous approaches, and at the same time requires less information about the system. In addition, our method can be generalized to unbounded quantitative properties such as mean-payoff bounds. In the second part, we introduce two techniques for comparing probabilistic systems. Probabilistic systems are typically compared using the notion of equivalence, which requires the systems to have the equal probability of all behaviors. However, this notion is often too strict, since probabilities are typically only empirically estimated, and any imprecision may break the relation between processes. On the one hand, we propose to replace the Boolean notion of equivalence by a quantitative distance of similarity. For this purpose, we introduce a statistical framework for estimating distances between Markov chains based on their simulation runs, and we investigate which distances can be approximated in our framework. On the other hand, we propose to compare systems with respect to a new qualitative logic, which expresses that behaviors occur with probability one or a positive probability. This qualitative analysis is robust with respect to modeling errors and applicable to many domains. In the last part, we present a new quantifier-free logic for integer arrays, which allows us to express counting. Counting properties are prevalent in array-manipulating programs, however they cannot be expressed in the quantified fragments of the theory of arrays. We present a decision procedure for our logic, and provide several complexity results.}, author = {Daca, Przemyslaw}, issn = {2663-337X}, pages = {163}, publisher = {Institute of Science and Technology Austria}, title = {{Statistical and logical methods for property checking}}, doi = {10.15479/AT:ISTA:TH_730}, year = {2017}, } @phdthesis{818, abstract = {Antibiotics have diverse effects on bacteria, including massive changes in bacterial gene expression. Whereas the gene expression changes under many antibiotics have been measured, the temporal organization of these responses and their dependence on the bacterial growth rate are unclear. As described in Chapter 1, we quantified the temporal gene expression changes in the bacterium Escherichia coli in response to the sudden exposure to antibiotics using a fluorescent reporter library and a robotic system. Our data show temporally structured gene expression responses, with response times for individual genes ranging from tens of minutes to several hours. We observed that many stress response genes were activated in response to antibiotics. As certain stress responses cross-protect bacteria from other stressors, we then asked whether cellular responses to antibiotics have a similar protective role in Chapter 2. Indeed, we found that the trimethoprim-induced acid stress response protects bacteria from subsequent acid stress. We combined microfluidics with time-lapse imaging to monitor survival, intracellular pH, and acid stress response in single cells. This approach revealed that the variable expression of the acid resistance operon gadBC strongly correlates with single-cell survival time. Cells with higher gadBC expression following trimethoprim maintain higher intracellular pH and survive the acid stress longer. Overall, we provide a way to identify single-cell cross-protection between antibiotics and environmental stressors from temporal gene expression data, and show how antibiotics can increase bacterial fitness in changing environments. While gene expression changes to antibiotics show a clear temporal structure at the population-level, it is unclear whether this clear temporal order is followed by every single cell. Using dual-reporter strains described in Chapter 3, we measured gene expression dynamics of promoter pairs in the same cells using microfluidics and microscopy. Chapter 4 shows that the oxidative stress response and the DNA stress response showed little timing variability and a clear temporal order under the antibiotic nitrofurantoin. In contrast, the acid stress response under trimethoprim ran independently from all other activated response programs including the DNA stress response, which showed particularly high timing variability in this stress condition. In summary, this approach provides insight into the temporal organization of gene expression programs at the single-cell level and suggests dependencies between response programs and the underlying variability-introducing mechanisms. Altogether, this work advances our understanding of the diverse effects that antibiotics have on bacteria. These results were obtained by taking into account gene expression dynamics, which allowed us to identify general principles, molecular mechanisms, and dependencies between genes. Our findings may have implications for infectious disease treatments, and microbial communities in the human body and in nature. }, author = {Mitosch, Karin}, issn = {2663-337X}, pages = {113}, publisher = {Institute of Science and Technology Austria}, title = {{Timing, variability and cross-protection in bacteria – insights from dynamic gene expression responses to antibiotics}}, doi = {10.15479/AT:ISTA:th_862}, year = {2017}, } @phdthesis{819, abstract = {Contagious diseases must transmit from infectious to susceptible hosts in order to reproduce. Whilst vectored pathogens can rely on intermediaries to find new hosts for them, many infectious pathogens require close contact or direct interaction between hosts for transmission. Hence, this means that conspecifics are often the main source of infection for most animals and so, in theory, animals should avoid conspecifics to reduce their risk of infection. Of course, in reality animals must interact with one another, as a bare minimum, to mate. However, being social provides many additional benefits and group living has become a taxonomically diverse and widespread trait. How then do social animals overcome the issue of increased disease? Over the last few decades, the social insects (ants, termites and some bees and wasps) have become a model system for studying disease in social animals. On paper, a social insect colony should be particularly susceptible to disease, given that they often contain thousands of potential hosts that are closely related and frequently interact, as well as exhibiting stable environmental conditions that encourage microbial growth. Yet, disease outbreaks appear to be rare and attempts to eradicate pest species using pathogens have failed time and again. Evolutionary biologists investigating this observation have discovered that the reduced disease susceptibility in social insects is, in part, due to collectively performed disease defences of the workers. These defences act like a “social immune system” for the colony, resulting in a per capita decrease in disease, termed social immunity. Our understanding of social immunity, and its importance in relation to the immunological defences of each insect, continues to grow, but there remain many open questions. In this thesis I have studied disease defence in garden ants. In the first data chapter, I use the invasive garden ant, Lasius neglectus, to investigate how colonies mitigate lethal infections and prevent them from spreading systemically. I find that ants have evolved ‘destructive disinfection’ – a behaviour that uses endogenously produced acidic poison to kill diseased brood and to prevent the pathogen from replicating. In the second experimental chapter, I continue to study the use of poison in invasive garden ant colonies, finding that it is sprayed prophylactically within the nest. However, this spraying has negative effects on developing pupae when they have had their cocoons artificially removed. Hence, I suggest that acidic nest sanitation may be maintaining larval cocoon spinning in this species. In the next experimental chapter, I investigated how colony founding black garden ant queens (Lasius niger) prevent disease when a co-foundress dies. I show that ant queens prophylactically perform undertaking behaviours, similar to those performed by the workers in mature nests. When a co-foundress was infected, these undertaking behaviours improved the survival of the healthy queen. In the final data chapter, I explored how immunocompetence (measured as antifungal activity) changes as incipient black garden ant colonies grow and mature, from the solitary queen phase to colonies with several hundred workers. Queen and worker antifungal activity varied throughout this time period, but despite social immunity, did not decrease as colonies matured. In addition to the above data chapters, this thesis includes two co-authored reviews. In the first, we examine the state of the art in the field of social immunity and how it might develop in the future. In the second, we identify several challenges and open questions in the study of disease defence in animals. We highlight how social insects offer a unique model to tackle some of these problems, as disease defence can be studied from the cell to the society. }, author = {Pull, Christopher}, issn = {2663-337X}, pages = {122}, publisher = {Institute of Science and Technology Austria}, title = {{Disease defence in garden ants}}, doi = {10.15479/AT:ISTA:th_861}, year = {2017}, } @phdthesis{820, abstract = {The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown. In Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates. In Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness. To start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background.}, author = {Jesse, Fabienne}, issn = {2663-337X}, pages = {87}, publisher = {Institute of Science and Technology Austria}, title = {{The lac operon in the wild}}, doi = {10.15479/AT:ISTA:th_857}, year = {2017}, } @phdthesis{821, abstract = {This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the static analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms. Our contributions can be broadly grouped into five categories. Our first contribution is a set of new algorithms and data structures for the quantitative and data-flow analysis of programs, based on the graph-theoretic notion of treewidth. It has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth. We utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs. In most cases we make an algebraic treatment of the considered problem, where several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases. We exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems, and provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase. We also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework, namely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems. Our second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis. In particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis. Additionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is (i)~linear in the number of call sites and (ii)~only logarithmic in the size of the whole library, as opposed to linear in the size of the whole library. Finally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth. This hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity. Our third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework. In this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures the magnitude of their respective effect. The Quantitative Interprocedural Analysis problem asks to determine whether there exists an infinite run of the program where the long-run ratio of the bad weights over the good weights is above a given threshold. We illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework, and present some case studies to this direction. Our fourth contribution is a new dynamic partial-order reduction for the stateless model checking of concurrent programs. Traditional approaches rely on the standard Mazurkiewicz equivalence between traces, by means of partitioning the trace space into equivalence classes, and attempting to explore a few representatives from each class. We present a new dynamic partial-order reduction method called the Data-centric Partial Order Reduction (DC-DPOR). Our algorithm is based on a new equivalence between traces, called the observation equivalence. DC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence. Depending on the program, the new partitioning can be even exponentially coarser. Additionally, DC-DPOR spends only polynomial time in each explored class. Our fifth contribution is the use of automata and game-theoretic verification techniques in the competitive analysis and synthesis of real-time scheduling algorithms for firm-deadline tasks. On the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints. On the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show how the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games.}, author = {Pavlogiannis, Andreas}, issn = {2663-337X}, pages = {418}, publisher = {Institute of Science and Technology Austria}, title = {{Algorithmic advances in program analysis and their applications}}, doi = {10.15479/AT:ISTA:th_854}, year = {2017}, } @phdthesis{837, abstract = {The hippocampus is a key brain region for memory and notably for spatial memory, and is needed for both spatial working and reference memories. Hippocampal place cells selectively discharge in specific locations of the environment to form mnemonic represen tations of space. Several behavioral protocols have been designed to test spatial memory which requires the experimental subject to utilize working memory and reference memory. However, less is known about how these memory traces are presented in the hippo campus, especially considering tasks that require both spatial working and long -term reference memory demand. The aim of my thesis was to elucidate how spatial working memory, reference memory, and the combination of both are represented in the hippocampus. In this thesis, using a radial eight -arm maze, I examined how the combined demand on these memories influenced place cell assemblies while reference memories were partially updated by changing some of the reward- arms. This was contrasted with task varian ts requiring working or reference memories only. Reference memory update led to gradual place field shifts towards the rewards on the switched arms. Cells developed enhanced firing in passes between newly -rewarded arms as compared to those containing an unchanged reward. The working memory task did not show such gradual changes. Place assemblies on occasions replayed trajectories of the maze; at decision points the next arm choice was preferentially replayed in tasks needing reference memory while in the pure working memory task the previously visited arm was replayed. Hence trajectory replay only reflected the decision of the animal in tasks needing reference memory update. At the reward locations, in all three tasks outbound trajectories of the current arm were preferentially replayed, showing the animals’ next path to the center. At reward locations trajectories were replayed preferentially in reverse temporal order. Moreover, in the center reverse replay was seen in the working memory task but in the other tasks forward replay was seen. Hence, the direction of reactivation was determined by the goal locations so that part of the trajectory which was closer to the goal was reactivated later in an HSE while places further away from the goal were reactivated earlier. Altogether my work demonstrated that reference memory update triggers several levels of reorganization of the hippocampal cognitive map which are not seen in simpler working memory demand s. Moreover, hippocampus is likely to be involved in spatial decisions through reactivating planned trajectories when reference memory recall is required for such a decision. }, author = {Xu, Haibing}, issn = {2663-337X}, pages = {93}, publisher = {Institute of Science and Technology Austria}, title = {{Reactivation of the hippocampal cognitive map in goal-directed spatial tasks}}, doi = {10.15479/AT:ISTA:th_858}, year = {2017}, } @phdthesis{838, abstract = {In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. }, author = {Rybar, Michal}, issn = {2663-337X}, pages = {86}, publisher = {Institute of Science and Technology Austria}, title = {{(The exact security of) Message authentication codes}}, doi = {10.15479/AT:ISTA:th_828}, year = {2017}, } @phdthesis{839, abstract = {This thesis describes a brittle fracture simulation method for visual effects applications. Building upon a symmetric Galerkin boundary element method, we first compute stress intensity factors following the theory of linear elastic fracture mechanics. We then use these stress intensities to simulate the motion of a propagating crack front at a significantly higher resolution than the overall deformation of the breaking object. Allowing for spatial variations of the material's toughness during crack propagation produces visually realistic, highly-detailed fracture surfaces. Furthermore, we introduce approximations for stress intensities and crack opening displacements, resulting in both practical speed-up and theoretically superior runtime complexity compared to previous methods. While we choose a quasi-static approach to fracture mechanics, ignoring dynamic deformations, we also couple our fracture simulation framework to a standard rigid-body dynamics solver, enabling visual effects artists to simulate both large scale motion, as well as fracturing due to collision forces in a combined system. As fractures inside of an object grow, their geometry must be represented both in the coarse boundary element mesh, as well as at the desired fine output resolution. Using a boundary element method, we avoid complicated volumetric meshing operations. Instead we describe a simple set of surface meshing operations that allow us to progressively add cracks to the mesh of an object and still re-use all previously computed entries of the linear boundary element system matrix. On the high resolution level, we opt for an implicit surface representation. We then describe how to capture fracture surfaces during crack propagation, as well as separate the individual fragments resulting from the fracture process, based on this implicit representation. We show results obtained with our method, either solving the full boundary element system in every time step, or alternatively using our fast approximations. These results demonstrate that both of these methods perform well in basic test cases and produce realistic fracture surfaces. Furthermore we show that our fast approximations substantially out-perform the standard approach in more demanding scenarios. Finally, these two methods naturally combine, using the full solution while the problem size is manageably small and switching to the fast approximations later on. The resulting hybrid method gives the user a direct way to choose between speed and accuracy of the simulation. }, author = {Hahn, David}, issn = {2663-337X}, pages = {124}, publisher = {Institute of Science and Technology Austria}, title = {{Brittle fracture simulation with boundary elements for computer graphics}}, doi = {10.15479/AT:ISTA:th_855}, year = {2017}, } @phdthesis{202, abstract = {Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions.}, author = {Pleska, Maros}, issn = {2663-337X}, pages = {126}, publisher = {Institute of Science and Technology Austria}, title = {{Biology of restriction-modification systems at the single-cell and population level}}, doi = {10.15479/AT:ISTA:th_916}, year = {2017}, } @phdthesis{6287, abstract = {The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's.}, author = {Nikitenko, Anton}, issn = {2663-337X}, pages = {86}, publisher = {Institute of Science and Technology Austria}, title = {{Discrete Morse theory for random complexes }}, doi = {10.15479/AT:ISTA:th_873}, year = {2017}, } @phdthesis{6291, abstract = {Bacteria and their pathogens – phages – are the most abundant living entities on Earth. Throughout their coevolution, bacteria have evolved multiple immune systems to overcome the ubiquitous threat from the phages. Although the molecu- lar details of these immune systems’ functions are relatively well understood, their epidemiological consequences for the phage-bacterial communities have been largely neglected. In this thesis we employed both experimental and theoretical methods to explore whether herd and social immunity may arise in bacterial popu- lations. Using our experimental system consisting of Escherichia coli strains with a CRISPR based immunity to the T7 phage we show that herd immunity arises in phage-bacterial communities and that it is accentuated when the populations are spatially structured. By fitting a mathematical model, we inferred expressions for the herd immunity threshold and the velocity of spread of a phage epidemic in partially resistant bacterial populations, which both depend on the bacterial growth rate, phage burst size and phage latent period. We also investigated the poten- tial for social immunity in Streptococcus thermophilus and its phage 2972 using a bioinformatic analysis of potentially coding short open reading frames with a signalling signature, encoded within the CRISPR associated genes. Subsequently, we tested one identified potentially signalling peptide and found that its addition to a phage-challenged culture increases probability of survival of bacteria two fold, although the results were only marginally significant. Together, these results demonstrate that the ubiquitous arms races between bacteria and phages have further consequences at the level of the population.}, author = {Payne, Pavel}, issn = {2663-337X}, pages = {83}, publisher = {Institute of Science and Technology Austria}, title = {{Bacterial herd and social immunity to phages}}, year = {2017}, } @phdthesis{938, abstract = {The thesis encompasses several topics of plant cell biology which were studied in the model plant Arabidopsis thaliana. Chapter 1 concerns the plant hormone auxin and its polar transport through cells and tissues. The highly controlled, directional transport of auxin is facilitated by plasma membrane-localized transporters. Transporters from the PIN family direct auxin transport due to their polarized localizations at cell membranes. Substantial effort has been put into research on cellular trafficking of PIN proteins, which is thought to underlie their polar distribution. I participated in a forward genetic screen aimed at identifying novel regulators of PIN polarity. The screen yielded several genes which may be involved in PIN polarity regulation or participate in polar auxin transport by other means. Chapter 2 focuses on the endomembrane system, with particular attention to clathrin-mediated endocytosis. The project started with identification of several proteins that interact with clathrin light chains. Among them, I focused on two putative homologues of auxilin, which in non-plant systems is an endocytotic factor known for uncoating clathrin-coated vesicles in the final step of endocytosis. The body of my work consisted of an in-depth characterization of transgenic A. thaliana lines overexpressing these putative auxilins in an inducible manner. Overexpression of these proteins leads to an inhibition of endocytosis, as documented by imaging of cargoes and clathrin-related endocytic machinery. An extension of this work is an investigation into a concept of homeostatic regulation acting between distinct transport processes in the endomembrane system. With auxilin overexpressing lines, where endocytosis is blocked specifically, I made observations on the mutual relationship between two opposite trafficking processes of secretion and endocytosis. In Chapter 3, I analyze cortical microtubule arrays and their relationship to auxin signaling and polarized growth in elongating cells. In plants, microtubules are organized into arrays just below the plasma membrane, and it is thought that their function is to guide membrane-docked cellulose synthase complexes. These, in turn, influence cell wall structure and cell shape by directed deposition of cellulose fibres. In elongating cells, cortical microtubule arrays are able to reorient in relation to long cell axis, and these reorientations have been linked to cell growth and to signaling of growth-regulating factors such as auxin or light. In this chapter, I am addressing the causal relationship between microtubule array reorientation, growth, and auxin signaling. I arrive at a model where array reorientation is not guided by auxin directly, but instead is only controlled by growth, which, in turn, is regulated by auxin.}, author = {Adamowski, Maciek}, issn = {2663-337X}, pages = {117}, publisher = {Institute of Science and Technology Austria}, title = {{Investigations into cell polarity and trafficking in the plant model Arabidopsis thaliana }}, doi = {10.15479/AT:ISTA:th_842}, year = {2017}, } @phdthesis{961, abstract = {Cell-cell contact formation constitutes the first step in the emergence of multicellularity in evolution, thereby allowing the differentiation of specialized cell types. In metazoan development, cell-cell contact formation is thought to influence cell fate specification, and cell fate specification has been implicated in cell-cell contact formation. However, remarkably little is yet known about whether and how the interaction and feedback between cell-cell contact formation and cell fate specification affect development. Here we identify a positive feedback loop between cell-cell contact duration, morphogen signaling and mesendoderm cell fate specification during zebrafish gastrulation. We show that long lasting cell-cell contacts enhance the competence of prechordal plate (ppl) progenitor cells to respond to Nodal signaling, required for proper ppl cell fate specification. We further show that Nodal signalling romotes ppl cell-cell contact duration, thereby generating an effective positive feedback loop between ppl cell-cell contact duration and cell fate specification. Finally, by using a combination of theoretical modeling and experimentation, we show that this feedback loop determines whether anterior axial mesendoderm cells become ppl progenitors or, instead, turn into endoderm progenitors. Our findings reveal that the gene regulatory networks leading to cell fate diversification within the developing embryo are controlled by the interdependent activities of cell-cell signaling and contact formation.}, author = {Barone, Vanessa}, issn = {2663-337X}, pages = {109}, publisher = {Institute of Science and Technology Austria}, title = {{Cell adhesion and cell fate: An effective feedback loop during zebrafish gastrulation}}, doi = {10.15479/AT:ISTA:th_825}, year = {2017}, } @phdthesis{992, abstract = {An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of variables, a finite domain of labels, and a set of constraints, each constraint acting on a subset of the variables. The goal is to find an assignment of labels to its variables that satisfies all constraints (or decide whether one exists). If we allow more general “soft” constraints, which come with (possibly infinite) costs of particular assignments, we obtain instances from a richer class called Valued Constraint Satisfaction Problem (VCSP). There the goal is to find an assignment with minimum total cost. In this thesis, we focus (assuming that P 6 = NP) on classifying computational com- plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core content of the work. In one of them, we consider VCSPs parametrized by a constraint language, that is the set of “soft” constraints allowed to form the instances, and finish the complexity classification modulo (missing pieces of) complexity classification for analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect matching algorithm. This generalization contributes to complexity classfications in two ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean CSPs in which every variable may appear in at most two constraints and second, it settles full classification of Boolean CSPs with planar drawing (again parametrized by a constraint language).}, author = {Rolinek, Michal}, issn = {2663-337X}, pages = {97}, publisher = {Institute of Science and Technology Austria}, title = {{Complexity of constraint satisfaction}}, doi = {10.15479/AT:ISTA:th_815}, year = {2017}, } @phdthesis{1121, abstract = {Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species boundaries, is a major evolutionary force shaping microbial genomes that facilitates adaptation to new environments as well as resistance to antimicrobial drugs. As such, understanding the mechanisms and constraints that determine the outcomes of HGT events is crucial to understand the dynamics of HGT and to design better strategies to overcome the challenges that originate from it. Following the insertion and expression of a newly transferred gene, the success of an HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore, predicting the impact of HGT on the genetic composition of a population critically depends on the distribution of fitness effects (DFE) of horizontally transferred genes. However, to date, we have little knowledge of the DFE of newly transferred genes, and hence little is known about the shape and scale of this distribution. It is particularly important to better understand the selective barriers that determine the fitness effects of newly transferred genes. In spite of substantial bioinformatics efforts to identify horizontally transferred genes and selective barriers, a systematic experimental approach to elucidate the roles of different selective barriers in defining the fate of a transfer event has largely been absent. Similarly, although the fact that environment might alter the fitness effect of a horizontally transferred gene may seem obvious, little attention has been given to it in a systematic experimental manner. In this study, we developed a systematic experimental approach that consists of transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an Escherichia coli host, and estimating the fitness effects of these transferred genes at a constant expression level by performing competition assays against the wild type. In chapter 2, we performed one-to-one competition assays between a mutant strain carrying a transferred gene and the wild type strain. By using flow cytometry we estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these fitness effects could be predicted by any of the intrinsic properties of the genes, namely, functional category, degree of complexity (protein-protein interactions), GC content, codon usage and length. Our analyses revealed that the functional category and length of the genes act as potential selective barriers. Finally, using the same procedure with the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is the most prominent selective barrier to HGT. In chapter 3, using the same set of genes we investigated the role of environment on the success of HGT events. Under six different environments with different levels of stress we performed more complex competition assays, where we mixed all 44 mutant strains carrying transferred genes with the wild type strain. To estimate the fitness effects of genes relative to wild type we used next generation sequencing. We found that the DFEs of horizontally transferred genes are highly dependent on the environment, with abundant gene–by-environment interactions. Furthermore, we demonstrated a relationship between average fitness effect of a gene across all environments and its environmental variance, and thus its predictability. Finally, in spite of the fitness effects of genes being highly environment-dependent, we still observed a common shape of DFEs across all tested environments.}, author = {Acar, Hande}, issn = {2663-337X}, pages = {75}, publisher = {Institute of Science and Technology Austria}, title = {{Selective barriers to horizontal gene transfer}}, year = {2016}, } @phdthesis{1122, abstract = {Computer graphics is an extremely exciting field for two reasons. On the one hand, there is a healthy injection of pragmatism coming from the visual effects industry that want robust algorithms that work so they can produce results at an increasingly frantic pace. On the other hand, they must always try to push the envelope and achieve the impossible to wow their audiences in the next blockbuster, which means that the industry has not succumb to conservatism, and there is plenty of room to try out new and crazy ideas if there is a chance that it will pan into something useful. Water simulation has been in visual effects for decades, however it still remains extremely challenging because of its high computational cost and difficult artdirectability. The work in this thesis tries to address some of these difficulties. Specifically, we make the following three novel contributions to the state-of-the-art in water simulation for visual effects. First, we develop the first algorithm that can convert any sequence of closed surfaces in time into a moving triangle mesh. State-of-the-art methods at the time could only handle surfaces with fixed connectivity, but we are the first to be able to handle surfaces that merge and split apart. This is important for water simulation practitioners, because it allows them to convert splashy water surfaces extracted from particles or simulated using grid-based level sets into triangle meshes that can be either textured and enhanced with extra surface dynamics as a post-process. We also apply our algorithm to other phenomena that merge and split apart, such as morphs and noisy reconstructions of human performances. Second, we formulate a surface-based energy that measures the deviation of a water surface froma physically valid state. Such discrepancies arise when there is a mismatch in the degrees of freedom between the water surface and the underlying physics solver. This commonly happens when practitioners use a moving triangle mesh with a grid-based physics solver, or when high-resolution grid-based surfaces are combined with low-resolution physics. Following the direction of steepest descent on our surface-based energy, we can either smooth these artifacts or turn them into high-resolution waves by interpreting the energy as a physical potential. Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new workflow where practitioners can re-simulate part of an existing simulation, such as removing a solid obstacle, adding a new splash or locally changing the resolution. Such changes can easily lead to new waves in the re-simulated region that would reflect off of the new simulation boundary, effectively ruining the illusion of a seamless simulation boundary between the existing and new simulations. Our non-reflecting boundaries makes sure that such waves are absorbed.}, author = {Bojsen-Hansen, Morten}, issn = {2663-337X}, pages = {114}, publisher = {Institute of Science and Technology Austria}, title = {{Tracking, correcting and absorbing water surface waves}}, doi = {10.15479/AT:ISTA:th_640}, year = {2016}, } @phdthesis{1123, abstract = {Motivated by topological Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps. We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3. An important guiding idea for our work was that suffciency of the DPC, together with an old result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN . In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC. In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power. }, author = {Mabillard, Isaac}, issn = {2663-337X}, pages = {55}, publisher = {Institute of Science and Technology Austria}, title = {{Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture}}, year = {2016}, }