Nuno D. Mendes

Inference of Complex Motifs using Biclustering Techniques

Nuno D. Mendes
Supervised by Ana T. Freitas and Arlindo L. Oliveira
Master's Thesis, IST, Universidade Técnica de Lisboa, 2005

In this thesis we propose a method to estimate search parameters for modern combinatorial motif finders, with an emphasis on the identification of complex motifs. Currently available combinatorial algorithms have proved to be highly efficient in exhaustively enumerating motifs which fulfill certain extraction criteria. Addressing the problem of identifying complex motifs 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.

Our method relies on a matrix of co-occurrences that, for each pair of small sequences of length λ, stores the number of input sequences in which the most common configuration of these small sequences occurs in. Using biclustering techniques it is possible to group elements of the matrix to form larger, possibly complex, motifs.

The proposed approach is not guaranteed to find all interesting correlations in the input sequences. However, it allows the efficient identification of unusual features referring to motifs that would otherwise require an exhaustive search in the parameter space to be extracted. This is particularly important when searching for complex motifs.

The experimental results show that this approach can effectively identify a set of important motif features that can guide the specification of search parameters for modern motif finders.

Keywords: Promoter prediction, Combinatorial algorithms, Motif extraction, Complex motifs, Biclustering techniques, Matrix of co-occurrences

Get a preprint: [ps] [ps.gz] [pdf] [pdf.gz]
Get a bibentry: [bib] [bbl]