### microRNA Bi-Targeting

### FRUUT

RNA secondary structures are often represented as trees, motivating the application of tree comparison tools to the detection of structural similarities and common motifs. We generalize some current approaches for RNA tree alignment, which are traditionally confined to *ordered rooted* mappings, to also consider *unordered unrooted* mappings.

Our algorithm generalizes previous algorithms that either solved the problem in an asymmetric manner, or were restricted to the rooted and/or ordered cases. Focusing here on the most general unrooted unordered case, we show that our algorithm
has an O(n_{T}n_{S} min(d_{T}, d_{S})) time complexity, where n_{T} and n_{S} are the number of nodes and d_{T} and d_{S} are the maximum node degrees in the input trees T and S, respectively. This maintains (and slightly improves) the time complexity of previous, less general algorithms for the problem.

### STRMS

### Context Fold

A machine learning based RNA secondary structure prediction tool. It allows flexible scoring model design, feature weight learning, and fast folding prediction.### cAlign

A tool for pairwise sequence alignment with regular expression path constrained. The tool gets as input two sequences and a regular expression constraint and return the optimal alignment in which the path is accepted by the regular expression.

The tool is written in Java by Nimrod Milo and Tamar Pinhas at the Computer Science Department of Ben-Gurion University of the Negev, Israel.

### RL-CSA

A tool for regular-language constrained pairwise global sequence alignment, which implements the following algorithms:- Arslan's algorithm appearing in
*"A.N. Arslan, Regular expression constrained sequence alignment, in: A. Apostolico, M. Crochemore, K. Park (Eds.), Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM 2005), Lecture Notes in Computer Science, vol. 3537, Springer, Berlin, 2005, pp. 322-333"*. - The algorithm of Chung, Lu and Tang, appearing in
*"Chung, Y., Lu, C., Tang, C.: Efficient algorithms for regular expression constrained sequence alignment. Information Processing Letters 103(6) (2007) 240-246"*. - Our Steiner tree based algorithm, to appear in
*"Kucherov, G., Pinhas, T., Ziv-Ukelson, M.: Regular Language Constrained Sequence Alignment Revisited, Proceedings of the IWOCA 2010 conference"*. - Our Straight-Line Program based algorithm, to appear in
*"Kucherov, G., Pinhas, T., Ziv-Ukelson, M.: Regular Language Constrained Sequence Alignment Revisited, Proceedings of the IWOCA 2010 conference"*.

### StemSearch

We extend*BLAST*approach to an efficient search for sequence RNA queries in large nucleotide databases, taking into account both sequence and structure features. Our tool is based on a structural representation of an RNA sequence by its potential stems. Potential stems in a genomic database are identified, annotated and indexed in a preprocessing stage.