My current research is primarily in the area of algorithms for computational biology. In particular, I have been studying the cophylogeny reconstruction problem. In this problem, we are given two evolutionary trees (e.g. a host and parasite tree, a species tree and a gene tree, etc.) and the mapping between their leaves. The objective is to find the least cost mapping of one tree onto the other, subject to a set of biologically plausible operations, that preserves the tip mappings. We have shown that this problem is NP-complete under a variety of models and have developed algorithms for special cases that can then be used in heuristics for the general case. The Jane cophylogeny software tool developed at Harvey Mudd is based on these results. I began working on this problem while on sabbatical at the School of Information Technology in Sydney, Australia. I am indebted to Professor Michael Charleston for introducing me to this problem and for a fruitful and stimulating collaboration.
My earlier research addressed the problem of designing efficient communication algorithms in optical networks employing wavelength-division multiplexting (WDM). Although many of these problems are NP-complete in general, my collaborators and I have obtained efficient optimal algorithms for a number of important special cases and approximation algorithms for many of the general problems. We have also recently examined on-line versions of these problems using competitive analysis.
A number of Harvey Mudd and off-campus students have taken an active role in these and prior research projects, resulting in a number of student co-authored research papers. The following students have participated in research in my group to date: Eli Brandt ('95), Tom Hehre ('96), Kevin Watkins ('97), Andrew Hutchings ('98), Mark Reyes ('98), Dominic Mazzoni ('99), Ranjith Rajagopalan ('99), Janet Davis ('99), William Williams ('99), Jascha Swisher ('00), Peter Boothe ('00), Greg Rae ('00), and Jeff Hartline ('01), Kurt Dresner ('02), Ethan Drucker ('02), Katie Ray ('02), Ed Miller ('03), Dustin Barnard ('03), Wesley Turner ('03), Will Chang ('04), Ian Ferrel ('04), Adrian Mettler ('04), Brian Tagiku ('05), Tim Carnes ('05), David Buchfuhrer ('06), Laura Elisa Celis ('06), Esteban Molina-Estolano ('06), Ben Birnbaum (Washington University, '06), Karyn Benson (Wellesley University, '06), Jeffrey Hartline, Chris Conow (Cal Poly Pomona, '10), Daniel Fielder ('11), Yaniv Ovadia ('10), Tselil Schramm ('12), John Peebles ('13), Anak Yodpinyanee ('12), Benjamin Cousins (Clemson Univ., '12), Kevin Black ('12), Andrew Michaud ('15), Nicole Wein ('15), David Lingenbrink ('14), Jordan Ezzell ('13), Becca Thomas ('14).
Last modified July 2011 by email@example.com