When we think of videos, we almost always take the frame order for granted. After all, someone must have generated that video in some way. However, if one was given a bag of randomly ordered frames, how would one go about ordering them to be coherent?
This problem is inspired by the data generated by the Linac Coherent Light Source (LCLS) facility at the Stanford Linear Accelerator Center. This facility can take an “image” of a biological molecule, acquiring data such as the (x, y, z) coordinates of all the atoms and the angles between the important bonds present in the backbone. However, because the procedure destroys every molecule after each “snapshot,” we end up with many images of the biological molecule in different states and conformations that are part of their dynamics trajectory. Here, the dynamics trajectory is analogous to the frame order of a video; at the LCLS facility, we get frames of the video without the information about their relative orders.
The motivation is to order these images so that we can learn something about the dynamics about the protein. For this project, we approached this problem step by step, first by applying our algorithm on very simple simulated datasets and then moving onto the reconstruction of shuffled biological molecule simulations.
In this project, we describe the steps to reconstruct a frame order from a series of images with the ultimate goal being the reconstruction of protein trajectories.
We apply nonlinear dimensionality reduction to generate a graph of frames with edges representing distances. From the graph we reconstruct our frame order through various means such as finding the long path in the minimum spanning tree.
We show promise of this approach through reconstructing the frame order of simple biological simulations.