Greedy mixture learning for multiple motif discovery in biological sequences.
BACKGROUND
This paper studies the problem of discovering subsequences, known as motifs, that are common to a given collection of related biosequences, by proposing a greedy algorithm for learning a mixture of motifs model through likelihood maximization. The approach adds sequentially a new motif to a mixture model by performing a combined scheme of global and local search for appropriately initializing its parameters. In addition, a hierarchical partitioning scheme based on kd-trees is presented for partitioning the input dataset in order to speed-up the global searching procedure. The proposed method compares favorably over the well-known MEME approach and treats successfully several drawbacks of MEME.


RESULTS
Experimental results indicate that the algorithm is advantageous in identifying larger groups of motifs characteristic of biological families with significant conservation. In addition, it offers better diagnostic capabilities by building more powerful statistical motif-models with improved classification accuracy.
Blekas
Konstantinos
K
Department of Computer Science, University of Ioannina 45110 Ioannina, Greece. kblekas@cs.uoi.gr
Fotiadis
Dimitrios I
DI
Likas
Aristidis
A
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D000595:Amino Acid Sequence; D017124:Conserved Sequence / Q000235:genetics*; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*