Background

Assembly theory is a theoretical framework that aims to characterize complexity, natural selection, and evolvability of structures that do not have explicit genetic inheritance. Its key quantitative measure is the assembly index, i.e., the number of recursive subconstructions required to build a target structure starting from basic units. Calculating a structure’s exact assembly index is known to be NP-hard; nevertheless, branch-and-bound algorithms exist that can efficiently handle these calculations for small molecules. The Daymude and Mathis labs maintain assembly-theory, the state-of-the-art, open-source Rust/Python package for assembly index calculations: https://github.com/DaymudeLab/assembly-theory.

Research Goals

The scholar team will work to ideate, implement, and evaluate potential algorithmic improvements for assembly index calculations. Specifically, the scholar team will (1) read and understand the background literature on assembly theory, (2) read and understand the state-of-the-art algorithmic approaches and their implementations, (3) implement novel bounding strategies based on graph kernelizations and reductions, (4) experiment with approximation algorithms with quantified error, (5) implement benchmarks and conduct performance evaluations, and (6) contribute final versions of these improvements to the assembly-theory Rust/Python package.

Skills Needed

Basic understanding of the Linux command line; good ability to program at least one programming language (Rust/C++ preferred, but Python okay); A grade in CSE 310 (CSE 450 or competitive programming is a huge bonus); interest in interdisciplinary research

Skills Gained

Branch-and-bound algorithms; approximation algorithms; dynamic programming; high-performance implementation in Rust; benchmarking in Rust; open-source contributions and maintenance; working understanding of assembly theory and origins of life research