First Search & Biology Day

First Search & Biology day

---

Goal

The objective of this 1-day invitation-based workshop is to bring together researchers interested in the application of search and optimization to problems coming from biology. The day will see several technical presentations and will give ample time to discussions.

Programme

9:15-9:30 Welcoming + Coffee

9:30-10:15

“Algorithms for Maximum Satisfiability and Applications in Bioinformatics???, Joao Marques-Silva, University of Southampton.

Abstract: The problem of Maximum Satisfiability (MaxSAT) and some of its variants find an increasing number of practical applications in a wide range of areas. Examples include optimization problems in system verification and in bioinformatics. However, most practical instances of MaxSAT are too hard for existing branch and bound algorithms. One recent alternative to branch and bound MaxSAT algorithms is based on unsatisfiable subformula identification. This talk provides an overview of recent algorithms for MaxSAT based on unsatisfiable subformula identification. The talk also summarizes the application of MaxSAT in representative bioinformatics applications.

Biography: Joao Marques-Silva is Professor of Computer Science at the University of Southampton, UK. He received a PhD degree in Electrical Engineering and Computer Science from the University of Michigan, Ann Arbor, in 1995, and the Habiliation degree in Computer Science from the Technical University of Lisbon, Portugal, in 2004. His research interests include algorithms for constraint solving and optimization, and applications in formal methods, artificial intelligence, and bioinformatics.

10:25-11:10

“Searching, sampling and counting in RNA and gene networks", Olivier Martin, LPTMS et UMR de Genetique Vegetale, Univ. Paris-Sud

Abstract: High dimensional continuous or discrete spaces arise in the biological mapping of genotypes to phenotypes. At least three branches of biology tackle such systems. (1) Synthetic biology seeks to provide design rules to produce molecules or networks with given properties, corresponding to a guided search in these spaces.(2) Evolutionary biology asks questions about tiny subsets of these spaces which require reliable samplings of needles in hay-stacks. (3) Comparative genomics can use the absolute size of subsets to infer usefulness in data mining approaches, corresponding to counting needles in hay-stacks. I will discuss these three aspects in the context of RNA secondary structures and gene regulatory networks.

Biography: Pr. Olivier Martin is a Physicist at the University Paris-Sud. He is actually on a sabbatical at INRA.

11:20-12:05

“Automated parameter tuning: boosting performance while reducing algorithm development time??? Frank Hutter, University of British Columbia.

Abstract: Most state-of-the-art algorithms for solving hard problems are highly parameterized, and tuning their parameters for optimal overall performance is often a nontrivial and unsatisfying task. In this talk, I will argue that automatic methods for parameter tuning can find better parameter settings than manual methods, and that valuable human development time is saved by leaving the tuning to an automatic method. I will present a few different approaches to parameter tuning and discuss their respective pros and cons. The focus will be on a search-based method called ParamILS; in particular, I will present case studies showing that ParamILS can speed up a variety of algorithms, including search algorithms for protein folding, propositional satisfiability, and mixed integer programming. My hope is that in the near future most parameter tuning will be handled by automated methods, leaving algorithm designers free to do more interesting and valuable research.

Biography: Frank Hutter is a PhD candidate at the University of British Colombia

12:15-13 Lunch

13-13:45

“Generalizing the discrete analyses of genetic networks using constraints???, Fabien Corblin (joint work with Laurent Trilling, Eric Fanchon, Sébastien Tripodi). Lab. TIMC-IMAG, Grenoble.

Abstract: The goal of our work is to generalize the current existing discrete approaches for analyzing the properties of genetic networks as proposed by Thomas using concepts that are already available in constraint programming (CP). We show that Thomas' networks can be formalized, generalized and implemented using constraints that also incorporate features of model-checkers. At the limit the proposed approach combines both aspects of simulation and reverse engineering, but the ultimate goal is to allow biologists to explore the combined effects of various types of hypotheses such as the assumed gene interactions and the expected dynamic behavior. We have developed a constraint program that utilizes the assumed hypotheses expressed as data. When the data is interpreted by a CP processor the system is capable of responding to multiple queries that encompass simulation, reverse engineering and hybrid combination of the two. We apply this tool to several biological examples and illustrate how queries can provide insight to either confirming of negating the hypotheses.

Biography: Fabien Corblin is a PhD student from Université of Grenoble. His research interests are in bioinformatics, with a focus on the construction of biological networks from incomplete and/or inconsistent knowledge.

13:55-14:40

“Improving Search???, Horst Samulowitz, Microsoft Research, Cambridge.

Abstract: Many real-world problems do not have a simple algorithmic solution and casting these problems as search problems is often not only the simplest way of casting them, but also the most efficient way of solving them. In this talk I will present several techniques to advance search-based algorithms in the context of solving quantified Boolean formulas (QBF). QBF enables complex problems including planning, two-player games and verification to be captured in a compact fashion. I will discuss techniques ranging from straight forward pre-processing methods to more sophisticated online approaches such as dynamic partitioning. Furthermore, I will show that all of the presented techniques achieve an essential improvement of the search process when solving QBF. At the same time the displayed empirical results also reveal the orthogonality of the different techniques with respect to performance. Generally speaking each approach performs well on a particular subset of benchmarks, but performs poorly on others. Consequently, an adaptive employment of the available techniques that maximizes the performance would result in further improvements. I will demonstrate that such an adaptive approach can pay off in practice, by presenting the results of using machine learning methods to dynamically select the best variable ordering heuristics during search.

Biography: Recently Horst finished his PhD in Artificial Intelligence (AI) at the University of Toronto with Fahiem Bacchus. His current research is in the area of knowledge representation, constraint satisfaction and reasoning in AI. In particular, he developed several novel and award-winning techniques in order to solve real-world problems represented in an expressive logical language (Quantified Boolean Formulas - QBF). Currently he is a Post-Doc at Microsoft Research, Cambridge.

14:50-15:35

“Dynamic Problem Encoding for Optimization???, Nikolaus Hansen, MSR-INRIA joint lab.

Abstract: We describe a general method for rendering search independent of the representation of solutions, Adaptive Encoding. We specify Adaptive Encoding (AE) for continuous domain search including (incremental) changes of the coordinate system, that is, changes of the representation of solutions.An appropriate representation can make a difficult search problem easy. One attractive way to change the representation within AE is derived from the Covariance Matrix Adaptation (CMA). We can prove that adaptive encoding can recover the CMA Evolution Strategy, when suitably applied to an evolution strategy with step-size control only. The proof implies that adaptive encoding potentially provides the means to apply CMA-like representation changes to any search algorithm in continuous domain, for example particle swarm optimization or differential evolution (slides 1.3MB).

Biography: Nikolaus Hansen is a research scientist at INRIA Saclay. After studying medicine and mathematics, Nikolaus received his Ph.D. in civil engineering in 1998 from the Technical University Berlin, working under Ingo Rechenberg. Since then, he has been researching in evolutionary computation and computational science at the TU Berlin and at the ETH Zurich. His main research interests are learning and adaptation in evolutionary computation and the development of useful and efficient algorithms.

15:45-16:15 Coffee+Wrap up.


Directions

Centre de Recherche Commun INRIA-Microsoft Research,Parc Orsay Université, 28, rue Jean Rostand, 91893 Orsay Cedex, France

The Joint Centre is physically located in Orsay, plateau du Moulon. It is a building in an industrial park called "Parc Orsay Université", previously named "Parc Club Orsay" (see map).

How to go to Parc Orsay Université from Paris. Take RER B South, go out at station "Le Guichet". Then look for the bus 269.02 - it is a 6' ride, and the frequency is approximately one every 15'. Get out at "Parc Orsay Université", also named "Orsay - Parc Club". You may get the bus schedule (in PDF).

Some RER B trains only stops at "Orsay Ville". When at station, take the tunnel under the tracks and look for the bus 06-07. It crosses the University campus. Get out at "Bois des Rames" which is at 5 minutes by easy walk from the Joint Centre. The bus schedule is here. [Orsay Bus maps]

If you drive, take the N118 at Paris Pont de Sèvres. After 12km, take exit 9 "Centre Universitaire". More directions (in French) are given here.

When you arrive at Parc Orsay Université go straight to the first intersection, turn left, you will see a building marked "INRIA Futurs"; go in the same direction to the next building, you will find the Joint Centre (see map).

Here is a bird's eye view.