Board Member Highlight: CRA Board Member Ran Libeskind-Hadas

By Ran Libeskind-Hadas

In The Origin of Species, Charles Darwin wrote: “I can understand how a flower and a bee might slowly become, either simultaneously or one after the other, modified and adapted in the most perfect manner to each other, by the continued preservation of individuals presenting mutual and slightly favourable deviations of structure.”

Darwin was imagining how pairs of species—in this case, flowers and bees—might symbiotically coevolve. Indeed, many pairs of species appear to have evolved in tandem either in a mutually beneficial way or, in some cases, in a type of arms war between host and parasite species, with the parasite evolving features to exploit the host and the host evolving features to defend itself against the parasite.

My research explores algorithmic methods for determining whether a pair of species are likely to have coevolved and, if so, finding the “best” scenarios that explain their evolutionary histories. This work explores the computational complexity of these reconciliation problems, seeks to develop efficient reconciliation algorithms where possible, and, ultimately, to implement these algorithms in practical tools for biologists and educators.

The computational complexity of these reconciliation problems depends on the particular biological events that we seek to model. We’ve shown that in some models the reconciliation problem is not only NP-hard but it’s even difficult to find an approximately optimal solution. In other cases, the reconciliation problem can be solved by efficient polynomial time algorithms.

Encouraging Undergraduate Student Research
Over the last 15 years, I’ve worked with undergraduates—both from Harvey Mudd and other colleges and universities—on a variety of problems related to these phylogenetic reconciliation problems. First- and second-year students have made valuable contributions to the development of software tools and third- and fourth-year students proved the NP-hardness of the reconciliation problem in one widely studied biological model, proved the APX-hardness of the problem in another model, and have developed efficient polynomial time algorithms for a number of these problems.

Over a five-year span, multiple groups of students developed a software reconciliation tool called Jane 4 that integrates many of our efficient algorithms. Jane 4 is among the most widely used tools for this problem among evolutionary biologists.

While I’m very excited about the research area itself and its potential for supporting the research of biologists, I’m equally excited about working with enthusiastic and curious undergraduates. I’ve found that when a bright undergraduate is provided with a well-scoped problem, and I don’t tell them in advance that I think it’s a difficult probem, they often make extraordinary progress and, ultimately, often end up as the first authors of conference and journal papers. It’s difficult for me to imagine a greater pleasure than being witness to a student making their first original discovery and seeing them realize that they possess the potential to become an exceptional researcher.

On the CRA board, I hope to encourage and promote all activities related to undergraduate research and the pipeline to graduate school. In spite of ballooning undergraduate enrollments in computer science, the number of students going on for Ph.D.s has remained relatively flat. By providing enthusiastic undergraduates with rich and rewarding research opportunities, we ultimately nurture the long-term health of our research community.

About the Author
Ran Libeskind-Hadas is the R. Michael Shanahan Professor of Computer Science at Harvey Mudd College. He is a member of the board of directors of the Computing Research Association and has served three terms as the co-chair of the CRA Education Committee. He received an A.B. in applied mathematics from Harvard University and a M.S. and Ph.D. in computer science at the University of Illinois Urbana-Champaign (UIUC). He is the recipient of the UIUC Distinguished Alumni Educator Award and both the junior and senior faculty teaching and mentoring awards at Harvey Mudd.