In this paper, we study the applicability of probabilistic solutions for the alignment of tertiary structure of proteins and discuss its difference with the deterministic algorithms. For this purpose, we introduce two Bayesian models and address a solution to add amino acid sequence and type (primary structure) to protein alignment. Furthermore, we will study the parameter estimation with Markov Chain Monte Carlo sampling from the posterior distribution. Finally, in order to see the effectiveness of these methods in the protein alignment, we have compared the parameter estimations in a real data set.