Bipartite graph-based matching technique has a powerful ability to give a global and optimized matching result. At the same time, we can take the advantage of graph-based data representation used with the technique. Graph-based representation has the ability to encapsulate the attribute of the objects and also the relationship details among the elements of the compared objects. The combination of graph-based matching technique and graph-based data structure are best applied in protein tertiary structure matching because protein structure has rich information that needs to be handled with care. The main contribution of the paper is (1) to design bipartite graph matching for protein matching and also (2) to incorporate graph-based data structure called ‘reference frame’ originally used in computer vision into bipartite graph matching. The matching result is measured using exponential similarity function.