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(nTnS min(dT, dS)) time complexity, where nT and nS are the number of nodes and dT and dS 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".