Novel Algorithm Infers Particle Trajectories in Cell Point Clouds

A point cloud is a set of discrete data points in a three-dimensional (3D) coordinate system. Each point represents a single spatial measurement that—when taken together—collectively embody the entire external surface of a 3D shape or object. Because researchers usually cannot identify the motion of the singular particles that comprise the cloud, they must instead examine the cloud’s movement as a whole.

Point clouds find applications in a variety of settings, including computer-aided design, geographic information systems, robotic path planning, and cell movement. During the 2024 SIAM Conference on Mathematics of Data Science, which is currently taking place in Atlanta, Ga., Caroline Moosmüller of the University of North Carolina at Chapel Hill presented a novel algorithm that infers continuous trajectories of point clouds, even when individual particles undergo splitting or are of nonuniform mass. She evaluates her method on simulated cell data.

Moosmüller proposed an extension of an existing approach [3] that models cells as point clouds and investigates the evolution of cells in a gene space (e.g., cell reprogramming). She seeks to design an efficient, intrinsic numerical scheme that is based on B-splines. “We want to infer trajectories that describe the process of how point clouds move,” she said, adding that doing so is a classical interpolation or approximation problem that occurs in infinite-dimensional space. “We’re hoping to make things more efficient and produce a code that is more flexible.”

Optimal transport is a natural choice of framework with which to explore this type of problem in the Wasserstein space [2]. “Because the particles [in the point cloud] move over time, we can’t follow them individually,” Moosmüller said. “So we need to find the most likely or efficient choice.” She then presented two different types of optimal transport. Monge’s formulation yields the Wasserstein distance and provides a map that illustrates the specific points that go/map to other points. Alternatively, Kantorovich’s formulation—which has a coupling component because particles can split or merge—is essentially the discrete version of Monge’s formulation. “This is a linear problem with linear constraints,” Moosmüller said. She next introduced the concept of Wasserstein geodesics, which explores the shortest path from one place to another. One can think of geodesics as an averaging operator because it computes the midpoint of two different point clouds.

Unlike previous techniques, Moosmüller’s proposed Wasserstein-Lane-Riesenfeld (WLR) algorithm effectively handles trajectory splitting and nonuniform mass [1]. It is an expansion of the classical Lane-Riesenfeld algorithm: an iterative scheme for the computation of B-splines that depends on degree and refinement level. “Depending on how often you cut off, you will get a different degree of B-spline — which means a different degree of smoothness,” Moosmüller said. Her expanded WLR algorithm measures valued data by replacing the linear average with the geodesic midpoint (also known as the OT average). It’s intrinsic to the Wasserstein geometry and can carry out trajectory approximation with high precision and at a chosen level of refinement.

Moosmüller then demonstrated her algorithm’s performance by showing that when a mass splits unevenly (e.g., weighted splitting), the trajectory bends towards the larger portion of mass (see Figure 1). “This is a very natural thing to happen,” she said. “If you have a lot of mass in the beginning, you will split it. And if there’s more mass on one side, you will bend towards that.” She also confirmed that the WLR algorithm successfully conducted trajectory inference on a variety of datasets (see Figure 2).

Moosmüller concluded her presentation by noting that other frameworks—such as the four-point scheme—can likewise achieve interpolation due to the flexibility of the original Lane-Riesenfeld algorithm, which is easily extendable to other subdivision schemes. While she utilizes Wasserstein geometry, researchers could feasibly choose something else. “What I’m trying to advertise is that there’s a broad range of things we can be doing with this idea,” she said, “You just need a complete metric space that has a geodesic property and you’re good to go.”

References
[1] Banerjee, A., Lee, H., Sharon, N., & Moosmüller, C. (2024). Efficient trajectory inference in Wasserstein space using consecutive averaging. Preprint, arXiv:2405.19679v1.
[2] Chewi, S., Clancy, J., Le Gouic, T., Rigollet, P., Stepaniants, G., & Stromme, A.J. (2021). Fast and smooth interpolation on Wasserstein space. In Proceedings of the 24th international conference on artificial intelligence and statistics (AISTATS). Society for Artificial Intelligence and Statistics.
[3] Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., … Lander, E.S. (2019). Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4), 928-943.