Colloquium Details
Flowers, Bees, and Algorithms
| Author: | Ran 'RON' Libeskind-Hadas Harvey Mudd College |
|---|---|
| Date: | May 19, 2011 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Virginia Lo |
Abstract
In the Origin of Species, Charles Darwin speculated that pairs of interacting species such as flowers and bees might slowly adapt "in the most perfect manner to each other" for their mutual benefit. Coevolution - the genetic change in one species in response to another - is abundantly evident in nature. It is of interest to epidemiologists and parasitologists (e.g. in the mutual evolution of viruses and their hosts) as well as to biologists in a variety of subdisciplines.
The cophlogeny reconstruction problem is a fundamental computational problem in the study of coevolution. This problem tries to find the "best" mapping of one phylogenetic tree (e.g. that of bees) onto another (e.g. that of flowers pollinated by those bees). We have recently shown that this problem is NP-complete and have also shown that the problem can be solved in polynomial time under certain conditions. These efficient algorithms for special cases have led to new heuristics that can find very good solutions in general.
In this talk, I will describe the biological motivation for this problem, describe some of the recent complexity and algorithmic results, and demonstrate our Jane software system that implements these algorithms. Finally, I will describe some recent biological studies that have used the Jane software.
Some results in this talk are joint work with Michael Charleston (University of Sydney, Australia); Daniel Fielder, Tselil Schramm, and Anak Yodpinyanee (Harvey Mudd College); Benjamin Cousins (Clemson University); and Chris Conow (USC).
Biography
Ran Libeskind-Hadas received the B.A. in applied mathematics from Harvard University and the M.S. and Ph.D. in computer science from the University of Illinois at Urbana-Champaign where he worked with C. L. Liu on algorithmic issues in fault-tolerant VLSI systems. Since 1993 he has been a faculty member at Harvey Mudd College where he is currently serving as Associate Dean of Faculty. Ran's research interests are in algorithms and computational biology. With colleagues at Harvey Mudd, he has also been involved in the development of new introductory computer science courses that are now being adapted for use at a number of other institutions.