MC-PSC (Multi-Criteria Protein Structure Comparison) is one of the GCAs (Grand Challenge Applications) in the field of structural proteomics. The solution of the MC-PSC grand challenge requires the use of distributed algorithms, architectures and environments. This paper is aimed at the analysis of the scalability of our newly developed distributed algorithm for MC-PSC in the grid environment. The scalability in the grid environment indicates the capacity of the distributed algorithm to effectively utilize an increasing number of processors across multiple sites. The results of the experiments conducted on the UK's NGS (National Grid Service) infrastructure are reported in terms of speedup, efficiency and cross-site communication overhead.