COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2010

Affinity purifcation followed by mass spectrometry identifcation (AP-MS) is an increasingly popular approach to observe protein-protein interactions (PPI) in vivo. One drawback of AP-MS, however, is that it is prone to detecting indirect interactions mixed with direct physical interactions. Therefore, the ability to distinguish direct interactions from indirect ones is of much interest.

We first propose a simple probabilistic model for the interactions captured by AP-MS experiments, under which the problem of separating direct interactions from indirect ones is formulated. Then, given idealized quantitative AP-MS data, we study the problem of identifying the most likely set of direct interactions that produced the observed data. We address this challenging graph theoretical problem by first characterizing signatures that can identify weakly connected nodes as well as dense regions of the network. The rest of the direct PPI network is then inferred using a genetic algorithm. Our algorithm shows a good performance on both simulated and biological networks with very high sensitivity and specificity. Then the algorithm is used to predict direct interactions from a set of AP-MS PPI data from yeast, and its performance is measured against a high-quality interaction dataset.

As the sensitivity of AP-MS pipeline improves, the fraction of indirect interactions detected will also increase, thereby making the ability to distinguish them even more desirable. Despite the simplicity of our model for indirect interactions, our method provides a good performance on the test networks.

This is joint work with Ashish Sabharwal, Adrian Vetta, and Mathieu Blanchette

We propose a method to approximate a closed 3D object with a union of overlapping spheres whose centres lie on the object's medial axis. When a large number of spheres is considered, this approximation may be used to recover differential properties of the shape's boundary. When a small number of spheres is used, our approximation is a valuable tool for applications in computer graphics. Specifically, in comparison with a state-of-the-art approach, our method works more than an order of magnitude faster and achieves a tighter approximation in terms of volume difference with the original object, while using fewer spheres. The spheres generated by our method are internal and tangent to the object, which permits an exact error analysis, fast updates under deformation, and conservative dilation. We demonstrate that a tight bounding volume hierarchy of our set of spheres may be constructed using rectangle swept spheres as bounding volumes. Further, we show that this hierarchy generally offers improved performance in approximate separation distance tests than a state-of-the-art sphere-based mesh approximation.

Part of our job is to sell our ideas. There are several mediums we should use, but a particularly important and challenging one is the Internet. The potential size of your audience in enormous and there seem to be an endless number of ways to present your work. We'll talk about this during our forum on Wednesday May 26, at 2:30 after a brief primer by myself (Alejandro Erickson). Topics will include some or all of the following:

1. Your audience and purpose behind Internet publishing. Is it for self promotion? Are you making tools for other students? For researchers? Do you want to generate interest in your research area?
2. Identifying the material you want to publish.
3. Available tools, their usefulness and learning curve. For example Wordpress websites, Flash, Javascript, HTML5
4. Confronting the web development: Maximize (the quality of your publications) subject to x <= what you can do or learn x >=0.
5. Sharing examples of interesting examples of CS Theory and Math homepages, as well as more substantial projects.
6. Reaching your audience with search results and such.

Many modern networks are reconfigurable, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company's organizational chart; infrastructure networks, such as an airline's transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks.

We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call self-healing.

Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of guarantees and limitations. We also discuss future directions and theoretical questions we would like to answer.

Scalar Vector Graphics (SVG) is the ISO web standard for 2D graphics. We will take a quick look at the SVG ISO working group homepage on the web. Then to some SVG examples published by the MAA (mathematics association of america), and a very brief introduction to an SVG file with explanation of a few tags.

Extensible 3D (X3D) is the ISO web standard for 3D graphics. We will look at the Web3D Consortium homepage, which is the ISO working group for X3D. An example of scripting an X3D file with Java will be shown, where spheres are made to follow the well known Lorenz attractor defined by a system of differential equations. The animation is real-time, and can be viewed from any angle, so it is quite hypnotic to interact with. Again, a very brief introduction to an X3D file with explanation of a few tags.