are you also involved in those G-protein sequences?
Anyway, you might want to look into the literature on sequence match
distributions. An excellent book is Waterman's new "Intro to
computational Biology". There is considerable literature (which I do not
have at hand) on using the Gibb's sampling distribution. I've
tentatively thought that the distribution could be modified under the
assumption of random trees; however, I would imagine that this has
already been done..