Protein sequence motifs are short conserved subsequences common to related protein sequences. The extraction of sequence motifs in proteins can help classify proteins families and predict protein functions, also provide valuable information about the evolution of species. However, the automatic protein sequence motif extraction is not straightforward because sequence motifs are often inexact and containing gaps. In this paper, we review currently available algorithms for protein sequence motif extraction, and propose a novel scheme to extract protein sequence motifs that allow mismatches and gaps from unaligned protein sequences. This scheme is based on a probabilistic model-Mismatch-allowed Probabilistic Suffix Tree (M-PST). In this scheme, an M-PST is first constructed from the unaligned protein sequences. The subsequences with highest likelihood scores, which are over-represented patterns, are further discovered with the M-PST. These subsequences are probable sequence motifs and outputted along with the position probability matrices.