Earthmover-based manifold learning for analyzing molecular conformation spaces

EARTHMOVER-BASED MANIFOLD LEARNING FOR ANAL YZING MOLECULAR CONFORMA TION SPACES Nathan Zelesko Amit Moscovich Joe Kileel Amit Singer, Department of Mathematics, Brown University Program in Applied and Computational Mathematics, Princeton University Department of Mathematics, Princeton University ABSTRACT In this paper, we propose a novel approach for manifold learning that combines the Earthmover's distance (EMD) with the diffusion maps method for dimensionality reduction. We demonstrate the potential benefits of this approach for learning shape spaces of proteins and other flexible macromolecules using a simulated dataset of 3-D density maps that mimic the nonuniform rotary motion of A TP synthase. Our results show that EMD-based diffusion maps require far fewer samples to recover the intrinsic geometry than the standard diffusion maps algorithm that is based on the Euclidean distance. To reduce the computational burden of calculating the EMD for all volume pairs, we employ a wavelet-based approximation to the EMD which reduces the computation of the pairwise EMDs to a computation of pairwise weighted-null 1 distances between wavelet coefficient vectors. Index T erms -- Shape space, dimensionality reduction, Wasserstein metric, diffusion maps, Laplacian eigenmaps, cryo-electron microscopy 1. INTRODUCTION Proteins and other macromolecules are elastic structures that may deform in various ways.