Abstract We develop a computationally efficient method to simulate the transition of a protein between two conformations. Our method is based on a coarse-grained elastic network model in which distances between spatially proximal amino acids are interpolated between the values specified by the two end conformations. The computational speed of this method depends strongly on the choice of cutoff distance used to define interactions as measured by the density of entries of the constant linking/contact matrix. To circumvent this problem we introduce the concept of using a cutoff based on a maximum number of nearest neighbors. This generates linking matrices that are both sparse and uniform, hence allowing for efficient computations that are independent of the arbitrariness of cutoff distance choices. Simulation results demonstrate that the method developed here reliably generates feasible intermediate conformations, because our method observes steric constraints and produces monotonic changes in virtual bond and torsion angles. Applications are readily made to large proteins, and we demonstrate our method on lactate dehydrogenase, citrate synthase, and lactoferrin. We also illustrate how this framework can be used to complement experimental techniques that partially observe protein motions.