University of the Negev
Department of Computer Science
Structural RNA Motif Search
STRMS is an RNA motif search tool.
The algorithm of STRMS consists of two phases, the pre-processing phase and the comparison phase. In the pre-processing phase we prepare the target database for a variety of future queries. The pre-processing stage consists of partitioning the target text into given size consecutive overlapping windows with a predefined overlap, then folding each window (by mfold (Zuker, 2003)) which yields optimal and few sub-optimal structures, and finally converting each structure to a tree representation. We are left with a tree database (TDB).
In the second phase, we are given the query sequence and structure and convert the structure to a tree representation. We start the search with a tree alignment. In this stage we allow inputs of the specific RNA motif constraints such as simple pseudoknots, minor sequence conservation, and structural element length constraints. All target candidates that are found matching under these constraints are reported, sorted by score.
For more details please refer to:
Isana Veksler-Lublinsky, Michal Ziv-Ukelson, Danny Barash and Klara Kedem. A Structure Based Flexible Search Method for ncRNA motifs. Journal of Computational Biology 14(7): 908-926, 2007.