Objective Nowadays, how to determine an accurate three-dimensional protein structure from nuclear magnetic resonance (NMR) spectroscopy experiments is a hot topic in biophysics, because understanding the spatial structure of a protein is crucial to research its function. However, this is a large challenge due to the serious lack of experimental data.Methods In this paper, the problem of protein structure determination was solved by matrix completion (MC) algorithms of recovering a distance matrix. Firstly, the initial distance matrix model was established, then its missing data were recovered by the MC algorithms at different sampling ratios. The subsequent stage involved adding the noise model to evaluate the noise resistance of the algorithms. Four proteins with different topological structures and 6 off-the-shelf MC algorithms were selected for testing.Results The results show that these algorithms have good performance in a certain range of sampling ratios and noises. More specifically, the advantages of different algorithms in the case of accurate sampling and noisy sampling are compared by analyzing the average and standard deviation of the root-mean-square deviation (RMSD) and computational time, which are two important indexes about algorithms.Conclusion We can conclude that 6 different MC algorithms have different performances and advantages for the problem of protein structure determination. These characteristics provide a basis for the development of a new MC algorithm. The results of this paper have potential promotion in the field of protein research based on MC algorithms.