Publications

Merge trees are fundamental data structures in computational topology. They track connected components in sublevel sets of scalar func- tions and can be used to compute 0-dimensional persistence diagrams, to construct contour trees on simply connected domains, and to quickly query the relationship between connected components in different sublevel sets. We introduce a representation of merge trees that tracks the nesting of their branches. We present algorithms to construct and manipulate the trees in this representation directly. We show that our algorithms are not only fast, outperforming Kruskal’s algorithm, but they are easy to parallelize in shared memory using double-word compare-and-swap operations. We present experiments that illustrate the scaling of our algorithms as functions of the data size and of the number of threads.
Springer Mathematics + Visualization

Maximum parsimony phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of hosts and parasites, genes and species, and other interdependent pairs. Since the problem of finding temporally feasible maximum parsimony reconciliations is NP-complete, current methods use either exact algorithms with exponential worst-case running time or heuristics that do not guarantee optimal solutions. We offer an efficient new approach that begins with a potentially infeasible maximum parsimony reconciliation and iteratively “repairs” it until it becomes temporally feasible. In a non-trivial number of cases, this approach finds solutions that are better than those found by the widely-used Jane heuristic.
BMC Bioinformatics

Consider two simple polygons with equal area. The Wallace–Bolyai–Gerwien theorem states that these polygons are scissors congruent, that is, they can be dissected into finitely many congruent polygonal pieces. We present an interactive application that visualizes this constructive proof.
Proceedings of the 32nd International Symposium on Computational Geometry

Phylogenetic tree reconciliation is an important technique for reconstructing the evolutionary histories of species and genes and other dependent entities. Reconciliation is typically performed in a maximum parsimony framework and the number of optimal reconciliations can grow exponentially with the size of the trees, making it difficult to understand the solution space. This paper demonstrates how a small number of reconciliations can be found that collectively contain the most highly supported events in the solution space. While we show that the formal problem is NP-complete, we give a $1-\frac1e$ approximation algorithm, experimental results that indicate its effectiveness, and the new DTL-RnB software tool that uses our algorithms to summarize the space of optimal reconciliations (www.cs.hmc.edu/dtlrnb).
IEEE/ACM Transactions on Computational Biology and Bioinformatics

Projects

  • Wikipath

    A web app that finds the shortest path between any two Wikipedia articles. First place finisher in advanced category at the Spring 2015 Claremont 5C hackathon.

  • Snakes on a Hyperplane

    An online multiplayer 3D snake game. People’s Choice winner at the Spring 2016 Claremont 5C Hackathon.

Contact