Back to search

University of British Columbia

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

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tajmir Riahi, Aryan
Contributors dc:contributor
  • Condon, Anne
  • Dao Duc, Khanh

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/93435

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Tajmir Riahi, Aryan. Optimal transport algorithms and metrics for 3D point-cloud alignment with applications to cryogenic electron microscopy. doctoral thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/93435