Nuno D. Mendes

MUSA: a parameter free algorithm for the identification of biologically significant motifs

Nuno D. Mendes, Ana C. Casimiro, Pedro M. Santos, Isabel Sá-Correia, Arlindo L. Oliveira, Ana T. Freitas
Bioinformatics, 2006 doi:10.1093/bioinformatics/btl537

Motivation: The ability to identify complex motifs, i.e., non-contiguous nucleotide sequences, is a key feature of modern motif finders. Addressing this problem is extremely important, not only because these motifs can accurately model biological phenomena but because its extraction is highly dependent upon the appropriate selection of numerous search parameters.

Currently available combinatorial algorithms have proved to be highly efficient in exhaustively enumerating motifs (including complex motifs) which fulfill certain extraction criteria. However, one major problem with these methods is the large number of parameters that need to be specified.

Results: We propose a new algorithm, MUSA (Motif finding using an UnSupervised Approach), that can be used either to autonomously find over-represented complex motifs or to estimate search parameters for modern motif finders.

This method relies on a biclustering algorithm that operates on a matrix of co-occurrences of small motifs. The performance of this method is independent of the composite structure of the motifs being sought, making few assumptions about their characteristics.

The MUSA algorithm was applied to two data sets involving the bacterium Pseudomonas putida KT2440. The first one was composed of σ⁵⁴-dependent promoter sequences and the second data set included 54 promoter sequences of up-regulated genes in response to phenol, as suggested by quantitative proteomics. The results obtained indicate that this approach is very effective at identifying complex motifs of biological significance.

Availability: The MUSA algorithm is available upon request from the authors, and will be made available via a Web based interface.

Supplementary information: An appendix is available here