CAG Schedule of Talks: Summer 2010

Schedule of Talks: Summer 2010

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Wed. May 26 2:30pm ECS 642 Alejandro Erickson Showcasing your CS Theory and Math ideas on the Internet
Fri. June 4 2:30pm ECS 660 Amitabh Trehan Algorithms for self-healing in networks
Wed. June 9 2:30pm ECS 642 Russell Campbell Scalar Vector Graphics (SVG)
Fri. June 18 2:30pm ECS 104 Ethan Kim Predicting direct protein interactions from affinity purification mass-spectrometry data
Tues. June 22 2:30pm ECS 104 Svetlana Stolpner Medial Spheres for Shape Approximation
Fri. June 25 1:30pm ECS 130 Michael McGuffin Visualizing Trees and Graphs

Upcoming Talks

Predicting direct protein interactions from affinity purification mass-spectrometry data
Ethan Kim
School of Computer Science, McGill University
Friday June 18, 2:30pm, ECS 104

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

Medial Spheres for Shape Approximation
Svetlana Stolpner
School of Computer Science, McGill University
Tuesday June 22, 2:30pm, ECS 104

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.

Visualizing Trees and Graphs
Michael McGuffin
Ecole de technologie superieure (ETS), Montreal, Quebec
Friday June 25, 1:30am, ECS 130

This talk will cover recent research in information visualization conducted at ETS in Montreal. First, we'll spend 5 minutes seeing how we can analyze the space-efficiency of drawings of trees using asymptotic analysis, allowing the depth of the tree to go to infinity (work published in the journal Information Visualization in 2010) Then, we'll spend about 35 minutes seeing how popup widgets, gestural interaction, and hybrids of parallel coordinates + scatterplot matrices can help with network visualization (InfoVis 2009 paper). as well as work from an upcoming paper).

Previous talks:

Here is an informal meeting that everyone is welcome to attend:

Forum: Showcasing your CS Theory and Math ideas on the Internet
Moderated by Alejandro Erickson
Wednesday May 26, 2:30, ECS642

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.

Algorithms for self-healing in networks
Amitabh Trehan
Department of Computer Science, University of New Mexico
Friday June 4, 2:30pm, ECS 660

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.

Forum: Scalar Vector Graphics (SVG)
Moderated by Russell Campbell
Wednesday June 9, 2:30, ECS642

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.

CAG Schedule of Talks: Summer 2010 / maintained by Wendy Myrvold / / revised June 14, 2010