^May June – 2009 ^July

The leveraging of todays unprecedented capability to manipulate biological systems by state-of-the-art computational, mathematical and engineering techniques , may profoundly affect the way we approach the solution to pressing grand challenges such as the development of sustainable green energy, next generation healthcare, etc. The conceptual cornerstone of Synthetic Biology a field very much on its infancy- is that methodologies commonly used to design and construct non-biological artefacts (e.g. computer programs, airplanes, bridges, etc) might also be mastered to create designer living entities. Computational methods for modeling in Synthetic Biology consist of a list of instructions detailing an algorithm that can be executed and whose computation resembles the behavior of the biological system under study. This computational approach to modelling biological systems has been termed executable biology. In this talk I will describe current approaches for the automated generation and testing of executable biology models for synthetic biology.

The problem of carrying out cryptographic computations when the participating parties are rational in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret. Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this dependence on the actual utility values is really necessary and prove that in the basic setting, rational secret sharing cannot be achieved without it. On the positive side, we show that by somewhat relaxing the standard assumptions on the utility functions, it is possible to achieve utility independence. In addition to the above, observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario is not at all unlikely.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties' utilities for this attack is known, in which case it is possible to prevent this from happening.

This is a joint work with Yehuda Lindell.

The prevalence of large racks of interconnected processor nodes forces us to take another look at how to exploit parallelism when taking the join of large relations. Sometimes, there is a gain in total cost to be had by distributing pieces of each relation to several different nodes and computing the join of several large relations at once. The optimization problem is to pick the degree of replication of each relation, under the constraint that the total number of compute-nodes is fixed. We set up this problem as a nonlinear optimization and show that there is always a solution (which must be approximated by rounding to the nearest integers). For some of the most common types of join – star joins and chain joins – we give closed-form solutions to the optimization problem. Finally, we point out that the join algorithm we propose can be implemented using features already present in Hadoop, the open-source implementation of map-reduce

Predicting secondary structures of RNA molecules is a classic example of a biological problem which is solved via the usage of computational tools. The original algorithms for the RNA folding problem (dating back to the late 70's) solve it in O(n^3) time and O(n^2) space complexities (where n denotes the length of the input sequence, and can get up to several hundreds). While these complexities are reasonable for the processing of a single input, they are inadequate for modern analysis of genome-wide data, which may include several billions of input sequences. Recently, the running time was improved to O(nZ), where Z is a sparsity parameter that satisfies n < Z < n^2. In the talk, new results will be presented, which reduce the space complexity to O(Z), and the time complexity to O(LZ), where L is a sparsity parameter that satisfies L < n. The presented techniques extend to a family of RNA folding algorithms, which include more sophisticated problem variants with higher time and space complexities, as well as to algorithms from other fields, such as parsing sentences with a given probabilistic context free grammar.

Power consumption is a major issue in today's datacenters. I will give an overview of the general issue of power consumption in dataceneters and will focus on storage power consumption, which typically comprises a significant percentage of datacenter power. Understanding, managing, and reducing storage power consumption is an essential aspect of any efforts that address the total power consumption of datacenters. We developed a scalable power modeling method that estimates the power consumption of storage workloads. The modeling concept is based on identifying the major workload contributors to the power consumed by the disk arrays. To estimate the power consumed by a given host workload, our method translates the workload to the primitive activities induced on the disks. In addition, we identified that I/O queues have a fundamental influence on the power consumption. Our power estimation results are highly accurate, with only 2% deviation for typical random workloads with small transfer sizes (up to 8K), and a deviation of up to 8% for workloads with large transfer sizes. We successfully integrated our modeling into a power-aware capacity planning tool to predict system power requirements and integrated it into an online storage system to provide online estimation for the power consumed.

The path packing problem for graphs is defined as follows: given a supply graph G=(N,E), and a demand graph (T,S), what is the maximal number of edge-disjoint paths with the end-pair in S in G? The problem is considered under two assumptions: (1) the node degrees in NT T are even, and (2) the demand graph satisfies condition defined by A. Karzanov in his 1989 paper. For any demand graph violating the above condition, the problem is known to be NP-hard even under (1), and only a few cases satisfying (1) and (2) have been solved. The talk will address the relation between the path packing problem and an auxiliary flow problem and will contain a short survey of results achieved in my dissertation. No special background in graph theory! is required.

We study statistical properties of interacting protein interfaces and predict two strong, related effects: (i) statistically enhanced self-attraction of proteins; (ii) statistically enhanced attraction of proteins with similar structures. The effects originate in the fact that the probability to find a pattern self-match between two identical, interacting protein interfaces is always higher compared with the probability for a pattern match between two different, promiscuous protein interfaces. This theoretical finding explains statistical prevalence of homodimers in protein-protein interaction networks reported earlier. Further, our findings are confirmed by the analysis of curated database of protein complexes that showed highly statistically significant overrepresentation of dimers formed by structurally similar proteins with highly divergent sequences (“superfamily heterodimers”). We predict that significant fraction of heterodimers evolved from homodimers with the negative design evolutionary pressure applied against promiscuous homodimer formation. This is achieved through the formation of highly specific contacts formed by charged residues as demonstrated both in model and real superfamily heterodimers. In addition we introduce the notion of structural correlations of amino acid interface density. We predict that protein interfaces with enhanced structural correlations are statistically more promiscuous as compared with proteins possessing a lower degree of interface structural correlations.

References:

1. D. B. Lukatsky and E. I. Shakhnovich, Statistically Enhanced Promiscuity of Structurally Correlated Patterns, Phys. Rev. E 77, 020901(R) (2008). 2. D. B. Lukatsky, B. E. Shakhnovich, J. Mintseris, and E. I. Shakhnovich, Structural Similarity Enhances Interaction Propensity of Proteins, J. Mol. Biol. 365, 1596 (2007). 3. D. B. Lukatsky, K. B. Zeldovich, and E. I. Shakhnovich, Statistically Enhanced Self-Attraction of Random Patterns, Phys. Rev. Lett. 97, 178101 (2006). .