2008 Events Archives
Conferences, Lectures and Workshops
MINOS 08
12-13 April 2008
Seminars
| Date | 11th November 2008 |
| Speaker | Prof. Fedor Fomin - University of Bergen |
| Title | Exact algorithms for NP hard problems |
| Abstract | It is a common belief that exponential time algorithms are
unavoidable when we want to find an exact solution of an NP hard
problem. The design of exact (moderately exponential) algorithms has a
long history dating back to Held and Karp's paper on the travelling
salesman problem in the early sixties. The last years have seen an
emerging interest in constructing exact algorithms for combinatorial
problems like Coloring, Max-Cut, 3-SAT, Minimum Dominating Set,
Treewidth, and Maximum Independent Set.
In this talk we overview some recent results and techniques in the area of exact algorithms and conclude with several open problems. |
| Date | 18th November 2008 |
| Speaker | Dr. Yee-Whye Teh - Gatsby Institute, University College London |
| Title | Bayesian Language Models |
| Abstract | We study Bayesian probabilistic models of natural languages. The models are based upon two ideas. First, languages have power law statistical behaviour with a few very common events and very many rare events; we model this with a class of nonparametric Bayesian models called Pitman-Yor processes. Second, language models are very large and language data sparse, thus smoothing (or sharing of information) across the models is essential to the success of the models; we use the concept of hierarchical Bayesian modelling to achieve smoothing. Put together, our hierarchical Pitman-Yor language model succeeds in achieving state-of-the-art performance. We show that interpolated Kneser-Ney (one of the best and most well-known smoothing techniques) can be interpreted as an approximation to the hierarchical Pitman-Yor language model. We also show that an extension of our model can address the issue of domain adaptation in a principled Bayesian fashion. |
| Date | 9th December 2008 |
| Speaker | Dr. Victor Lesk - Imperial College |
| Title | Fast correlation methods in protein-protein docking |
| Abstract | Protein-protein docking, or modelling the molecular geometry of a binary protein complex starting from the structures of its component interactors, promises to form the basis for new techniques in drug design, prediction of binding, of binding affinity and binding sites. It also constitues an additional source for inferring an organism's interactome. Protein-protein docking has been studied since the 1970's, and is a computationally intensive task: almost all docking protocols begin by a fine-grained scan of the space of models generated by the six basic rigid-body transformations of one of the component interactors with respect to the other. When assigning a relative score to the models, desirable properties include shape complementarity (SC) between the interactors, favorable electrostatic interactions (ES) and desolvation of hydrophobic groups (DE). If these properties can be expressed as dot products, then fast correlation algorithms based on fast Fourier transforms (FFTs) can be used. FFTs confer vastly improved scalability in scoring these large numbers of models. We describe how to represent interacting protieins numerically such that the dot product is a plausible measure of SC, ES or DE. If space is partitioned regularly into N boxes (as in FTDock, ZDock, DOT, PIPER protein docking software) then the FFT can improve the N-dependence of the computation time from N2 to N ln N for scoring the N models which have the interactors in some predefined relative orientation. A partitioning into spherical polars, used in David Ritchie's HEX technique, can also gain from the FFT and has other attractive features. Fast correlation scoring has two drawbacks: loss of detail when the input structures are discretized, and loss of discrimination in scoring metrics when they are adapted to correlation form. |