A Gibbs sampler for the detection of subtle motifs in multiple sequences

Author

Lawrence, Charles E. ; Altschul, Stephen F. ; Wootton, John C. ; Boguski, Mark S. ; Neuwald, Andrew F. ; Liu, Jun S.

Author_Institution

Wadsworth Labs., Albany, NY, USA

Volume

5

fYear

1994

fDate

4-7 Jan. 1994

Firstpage

245

Lastpage

254

Abstract

We describe a statistically based algorithm that aligns protein sequences by means of predictive inference. Using residue frequencies, this Gibbs sampling algorithm iteratively selects alignments in accordance with their conditional probabilities. The newly formed alignments in turn update an evolving residue frequency model. When equilibrium is reached the most probable alignment can be identified. If a detectable pattern is present, generally convergence is rapid. Effectively, the algorithm finds optimal local multiple alignments in linear time (seconds on current workstations). Its use is illustrated on test sets of lipocalins and prenyltranferases.<>

Keywords

image recognition; inference mechanisms; medical image processing; probability; proteins; Gibbs sampler; conditional probabilities; detectable pattern; evolving residue frequency model; lipocalins; multiple sequences; optimal local multiple alignments; predictive inference; prenyltranferases; protein sequences; residue frequencies; statistically based algorithm; subtle motifs;

fLanguage

English

Publisher

ieee

Conference_Titel

System Sciences, 1994. Proceedings of the Twenty-Seventh Hawaii International Conference on

Conference_Location

Wailea, HI, USA

Print_ISBN

0-8186-5090-7

Type

conf

DOI

10.1109/HICSS.1994.323572

Filename

323572