This paper proposes an efficient clustering method for protein sequences, using Affinity propagation algorithm (AP) and post-processing. In order to optimize the clustering result, post-processing is used to improve the clustering result of AP. To measure the similarity between two protein sequences, an improved alignment-free similarity measure is presented. This method is evaluated and compared with other algorithms on six protein sequences data sets. Experimental results demonstrate the effective performance of the proposed method.