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.