COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
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 selfhealing 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 massspectrometry 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 
Affinity purifcation followed by mass spectrometry identifcation (APMS) is an increasingly popular approach to observe proteinprotein interactions (PPI) in vivo. One drawback of APMS, 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 APMS experiments, under which the problem of separating direct interactions from indirect ones is formulated. Then, given idealized quantitative APMS 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 APMS PPI data from yeast, and its performance is measured against a highquality interaction dataset.
As the sensitivity of APMS 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 stateoftheart 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 stateoftheart spherebased mesh approximation.
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 spaceefficiency 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).
Here is an informal meeting that everyone is welcome to attend:
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:
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, peertopeer, wireless and adhoc 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 selfhealing.
Here, we present several fast and provably good distributed algorithms for selfhealing 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 realtime, 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.