A sequential method for discovering probabilistic motifs in proteins.
OBJECTIVE
This paper proposes a greedy algorithm for learning a mixture of motifs model through likelihood maximization, in order to discover common substrings, known as motifs, from a given collection of related biosequences.


METHODS
The approach sequentially adds a new motif component to a mixture model by performing a combined scheme of global and local search for appropriately initializing the component parameters. A hierarchical clustering scheme is also applied initially which leads to the identification of candidate motif models and speeds up the global searching procedure.


RESULTS
The performance of the proposed algorithm has been studied in both artificial and real biological datasets. In comparison with the well-known MEME approach, the algorithm is advantageous since it identifies motifs with significant conservation and produces larger protein fingerprints.


CONCLUSIONS
The proposed greedy algorithm constitutes a promising approach for discovering multiple probabilistic motifs in biological sequences. By using an effective incremental mixture modeling strategy, our technique manages to successfully overcome the limitation of the MEME scheme which erases motif occurrences each time a new motif is discovered.
Blekas
K
K
Department of Computer Science, University of Ioannina, P.O. Box 1186, GR-45110 Ioannina, Greece. kblekas@cs.uoi.gr
Fotiadis
D I
DI
Likas
A
A
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D000595:Amino Acid Sequence / Q000235:genetics; D017124:Conserved Sequence / Q000235:genetics*; D006801:Humans; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D011336:Probability; D012680:Sensitivity and Specificity; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein / Q000379:methods*