^December January – 2008 ^February

Until recently, the study of gene regulation has focused mostly on two major mechanisms: the regulation of transcription (typically described in terms of the binding to transcription factors to specific DNA sequence motifs) and on direct protein-protein interactions. A string of high-throuhput experiments, however, has resulted in overwhelming evidence that several other layers of regulation are of comparable importance and cannot be neglected. Indeed, at least half of the diversity of the observable transcriptome is comprised by non-coding RNAs, and novel types and classes of ncRNAs keep being discovered. The oldest and best known, but as it seems by no means the only one of these RNA-mediated mechanism is post-transcriptional regulation through microRNAs. Anti-sense transcription is another one of the better-known effects.

In my presentation I will briefly review recent findings, both experimental and computational, that suggest that a substantial fraction of transcripts has regulatory function. Then I will focus on bioinformatics approaches to disentangle - at least partially - the various layers using two systems as examples: direct RNA-RNA and RNA-protein interactions. Because of their abundance (even though we understand very few specific systems in detail), we cannot ignore these multiple regulatory layers in attempts to reconstruct and eventually understand gene regulation networks.

Tools that analyze and modify binary code are crucial to many areas of computer science, including cyber forensics, program tracing, debugging, testing, performance profiling, performance modeling, and software engineering. Many tools used to support these activities have significant limitations in functionality, efficiency, accuracy, portability and availability.

Our goal is the design and implementation of a new framework that will allow for interoperability of the static and dynamic code modification, and enable the sharing and leveraging of this complex technology.

Characteristics of this framework include: multi-architecture, multi-format, and multi-operating system; library-based; open source; extensible data structures; exportable data structures; batch enabled; testable, with each separate component provided with a detailed test suite; and functions with non-contiguous and shared code.

This component-based approach requires identifying key portable and multi-platform abstractions at every level of functionality. Transitioning to this model successfully will enable us to break the "hero model" of tool development of having each group trying to produce its own end-to-end complete tool sets.

In previous work on mediation and negotiation support systems, we have focused upon using integrative bargaining. When end-users of our family-mediation and plea-bargaining systems have evaluated our systems, they commented that the systems met their personal needs, but not the interests of fairness or justice. For example, in Family Mediation, they meet the interests of the parents and not the children.

For negotiation support systems to be widely used, issues of fairness and justice must be addressed. We are currently developing measures for assessing the outcomes of online negotiation in the legal domains of sentencing, plea-bargaining and family mediation. Such methods will form the basis of a new model for evaluating fairness and consistency within online dispute resolution systems. This model will inform the construction of fairer and more consistent systems of IT based negotiation support.

We conclude by discussing a new project we are about to commence focusing upon developing negotiation support systems that promote constructive relationships following disputes.

Precise control of gene activation lies at the heart of nearly all biological processes. However, despite enormous advances in understanding this process from both experimental and theoretical perspectives, we are still missing a quantitative description of the underlying transcriptional control mechanisms, and the remaining questions, such as how DNA sequence elements 'compute' expression from the inputs they receive, are still very basic. In this talk, I will present our progress towards the ultimate goal of developing integrated quantitative models for transcription regulation. I will describe a novel thermodynamic model that computes gene activation patterns as a function of DNA sequence and show that this model accurately predicts gene activation patterns in fly from DNA sequence alone.

We often like to build a model for one scenario based on data from similar or nearby cases. For example, consider the problem of building a model which predicts a sentiment about books from short reviews, using reviews and sentiment of DVDs. Another example is of learning movies preference for one viewer from ratings provided by other similar users. There is a natural tradeoff between using data from more users and using data from only similar users.

In this talk, I will discuss the problem of learning good models using data from multiple related or similar sources. I will present a theoretical approach which extends the standard probably approximately correct (PAC) learning framework, and show how it can be applied in order to determine which sources of data should be used and how. The bounds explicitly model the inherit tradeoff between building a model from many but inaccurate data sources or building it from a few accurate data sources. The theory shows that optimal combinations of sources can improve performance bounds on some tasks.

Live Distributed Objects Prof. Kenneth P. Birman Abstract Although we've been building distributed systems for decades, it remains remarkably difficult to get them right. Distributed software is hard to design and the tools available to developers have lagged far behind the options for building and debugging non-distributed programs targeting desktop environments. At Cornell, we're trying to change this dynamic. The first part of this talk will describe "Live Distributed Objects", a new and remarkably easy way to create distributed applications, with little or no programming required (in fact, the talk will include a demo of how this works). Supporting these kinds of objects forced us to confront a number of scalability, security and performance questions not addressed by prior research on distributed computing platforms. The second part will look at Cornell's Quicksilver system and the approach it uses to solve these problems

This research is joint with PhD candidate Krzys Ostrowski (the "real" leader on the effort) and with Danny Dolev.

Abstract Machine learning algorithms are often used to extract rules and structure from large datasets, and have been successfully used in fields such as machine vision, natural language processing and computational biology. With the growing availability of text and images on the web, and high-throughput experiments in biology, learning algorithms are becoming a key tool for organizing, searching, and interpreting this data.

Learning algorithms are typically required to work with very large datasets of high dimensional signals. Thus scalability of algorithms is a key issue that must be addressed. In this talk I will show how the concept of convex duality can be used to design simple and scalable algorithms, and to help understand convergence of previously existing ones.

I will first address the problem of probabilistic inference in multivariate distributions, and show how convex duality results in simple convergent message passing algorithms for this problem. Specifically, I will show that approximate inference may be cast as a geometric program, where coordinate descent yields message passing updates. These results resolve a long standing problem regarding the convergence of message passing algorithms for approximate inference.

I will next address the problem of learning classifiers from labeled data, and present an exponentiated gradient algorithm that is also derived using convex duality. The algorithm can be shown to converge, and its convergence rate can be analyzed. I will conclude by showing an application of the algorithm to a large scale natural language parsing task, and demonstrate that it converges significantly faster than previous state of the art algorithms.

Abstract Worst-case complexity, which measures the performance of algorithms with respect to the most difficult instances of the problem at hand, is a standard and convenient complexity measure. On the other hand, average-case complexity, which measures the performance of algorithms with respect to typical (or simply random) instances, may be a more realistic complexity measure for instances that actually appear in practice. Furthermore, it seems to be the right measure in settings where computational hardness is beneficial (e.g. in cryptography and pseudo-randomness).

A central question in theoretical computer science is for which classes of computational problems (and against which families of algorithms) there is an equivalence between their worst-case and average-case complexities.

This question and the techniques to attack it are related to many other areas in computer science such as cryptography, pseudo-randomness, error-correcting codes, program checking and learning.

In this survey talk I will describe some recent results on worst-case/average-case equivalence. I will concentrate on two important classes of computational problems: NP and EXPTIME.

Abstract RNA secondary structure is defined along with three different ways to display them. Two distinct approaches are presented for determining secondary structure from sequence data. The comparative method requires a multiple sequence alignment of a collection of homologous RNA sequences. It uses phylogeny to determine common, conserved base pairs that are more likely to be the result of evolution than to exist by chance. On the other hand, recursive algorithms may be used on single sequences to compute minimum free energy structures, partition functions and other biophysical quantities. These algorithms ignore evolution and use empirically derived energy parameters based on physical chemistry. Examples will be given for both methods.

The latter part of the lecture will include recent work on computing the entropy of the Boltzmann distribution of foldings and how this quantity may be used to judge the overall reliability of free energy based methods for particular molecules.