Dataset Information

SMOTIF: efficient structured pattern and profile motif search.

ABSTRACT: BACKGROUND:A structured motif allows variable length gaps between several components, where each component is a simple motif, which allows either no gaps or only fixed length gaps. The motif can either be represented as a pattern or a profile (also called positional weight matrix). We propose an efficient algorithm, called SMOTIF, to solve the structured motif search problem, i.e., given one or more sequences and a structured motif, SMOTIF searches the sequences for all occurrences of the motif. Potential applications include searching for long terminal repeat (LTR) retrotransposons and composite regulatory binding sites in DNA sequences. RESULTS:SMOTIF can search for both pattern and profile motifs, and it is efficient in terms of both time and space; it outperforms SMARTFINDER, a state-of-the-art algorithm for structured motif search. Experimental results show that SMOTIF is about 7 times faster and consumes 100 times less memory than SMARTFINDER. It can effectively search for LTR retrotransposons and is well suited to searching for motifs with long range gaps. It is also successful in finding potential composite transcription factor binding sites. CONCLUSION:SMOTIF is a useful and efficient tool in searching for structured pattern and profile motifs. The algorithm is available as open-source at: http://www.cs.rpi.edu/~zaki/software/sMotif/.

SUBMITTER: Zhang Y

PROVIDER: S-EPMC1679804 | biostudies-literature | 2006 Nov

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

SMOTIF: efficient structured pattern and profile motif search.

Zhang Yongqiang Y Zaki Mohammed J MJ

Algorithms for molecular biology : AMB 20061121

<h4>Background</h4>A structured motif allows variable length gaps between several components, where each component is a simple motif, which allows either no gaps or only fixed length gaps. The motif can either be represented as a pattern or a profile (also called positional weight matrix). We propose an efficient algorithm, called SMOTIF, to solve the structured motif search problem, i.e., given one or more sequences and a structured motif, SMOTIF searches the sequences for all occurrences of th ...[more]

PMID: 17118189

Similar Datasets

Project description:MotivationThe motif discovery problem consists of finding over-represented patterns in a collection of biosequences. It is one of the classical sequence analysis problems, but still has not been satisfactorily solved in an exact and efficient manner. This is partly due to the large number of possibilities of defining the motif search space and the notion of over-representation. Even for well-defined formalizations, the problem is frequently solved in an ad hoc manner with heuristics that do not guarantee to find the best motif.ResultsWe show how to solve the motif discovery problem (almost) exactly on a practically relevant space of IUPAC generalized string patterns, using the p-value with respect to an i.i.d. model or a Markov model as the measure of over-representation. In particular, (i) we use a highly accurate compound Poisson approximation for the null distribution of the number of motif occurrences. We show how to compute the exact clump size distribution using a recently introduced device called probabilistic arithmetic automaton (PAA). (ii) We define two p-value scores for over-representation, the first one based on the total number of motif occurrences, the second one based on the number of sequences in a collection with at least one occurrence. (iii) We describe an algorithm to discover the optimal pattern with respect to either of the scores. The method exploits monotonicity properties of the compound Poisson approximation and is by orders of magnitude faster than exhaustive enumeration of IUPAC strings (11.8 h compared with an extrapolated runtime of 4.8 years). (iv) We justify the use of the proposed scores for motif discovery by showing our method to outperform other motif discovery algorithms (e.g. MEME, Weeder) on benchmark datasets. We also propose new motifs on Mycobacterium tuberculosis.Availability and implementationThe method has been implemented in Java. It can be obtained from http://ls11-www.cs.tu-dortmund.de/people/marschal/paa_md/.

Project description:The idea that populations are spatially structured has become a very powerful concept in ecology, raising interest in many research areas. However, despite dispersal being a core component of the concept, it typically does not consider the movement behavior underlying any dispersal. Using individual-based simulations in continuous space, we explored the emergence of a spatially structured population in landscapes with spatially heterogeneous resource distribution and with organisms following simple area-concentrated search (ACS); individuals do not, however, perceive or respond to any habitat attributes per se but only to their foraging success. We investigated the effects of different resource clustering pattern in landscapes (single large cluster vs. many small clusters) and different resource density on the spatial structure of populations and movement between resource clusters of individuals. As results, we found that foraging success increased with increasing resource density and decreasing number of resource clusters. In a wide parameter space, the system exhibited attributes of a spatially structured populations with individuals concentrated in areas of high resource density, searching within areas of resources, and "dispersing" in straight line between resource patches. "Emigration" was more likely from patches that were small or of low quality (low resource density), but we observed an interaction effect between these two parameters. With the ACS implemented, individuals tended to move deeper into a resource cluster in scenarios with moderate resource density than in scenarios with high resource density. "Looping" from patches was more likely if patches were large and of high quality. Our simulations demonstrate that spatial structure in populations may emerge if critical resources are heterogeneously distributed and if individuals follow simple movement rules (such as ACS). Neither the perception of habitat nor an explicit decision to emigrate from a patch on the side of acting individuals is necessary for the emergence of such spatial structure.

Dataset Information

SMOTIF: efficient structured pattern and profile motif search.

Publications

SMOTIF: efficient structured pattern and profile motif search.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets