Optimal transport algorithms and metrics for 3D point-cloud alignment with applications to cryogenic electron microscopy

This dissertation explores how Optimal Transport (OT) theory and related mathematical frameworks can advance the analysis of cryogenic electron microscopy (cryo-EM) data. Specifically, we address the rigid-body alignment problem across different settings and scenarios by developing a comprehensive set of computational tools. We begin by establishing the mathematical foundations of our approach, introducing Centroidal Voronoi Tessellation (CVT) as a method for simplifying cryo-EM density maps—the first step in our pipeline. Building on this foundation, we present a series of alignment methods tailored to distinct challenges in structural biology. First, we introduce AlignOT, which leverages a stochastic gradient descent (SGD)-like algorithm operating on the Wasserstein distance to achieve fast and accurate alignment when initial map positions are relatively close. Next, we present EMPOT, an alignment method that utilizes the unbalanced Gromov-Wasserstein divergence to align partial density maps while eliminating the requirement for close initial positioning. We demonstrate the effectiveness of both methods through comprehensive benchmarking experiments on standard datasets, showing competitive or superior performance compared to existing approaches. We then introduce a novel variant of the Gromov-Wasserstein distance, designed to simultaneously match multiple objects to a single target called the Joint Gromov-Wasserstein divergence (JGW). We establish theoretical properties of this new variant and propose an efficient method for its approximation. Through experiments both within and beyond the cryo-EM domain, we provide proof-of-concept demonstrations of our method's effectiveness and versatility. Finally, to ensure accessibility for the scientific community, we implement all these methods as a ChimeraX bundle, facilitating their integration into existing cryo-EM analysis workflows.