FRUUT 2.46 – Fast RNA Unrooted Unordered Tree Alignment

FRUUT 2.46


FRUUT computes an RNA structure alignment of two given RNA molecules. We generalize 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.


Michal Ziv-Ukelson’s Research Group




  • Linux / Mac / Windows
  • Java





Algorithms Mol Biol. 2013 Apr 16;8(1):13. doi: 10.1186/1748-7188-8-13.
Unrooted unordered homeomorphic subtree alignment of RNA trees.
Milo N1, Zakov S, Katzenelson E, Bachmat E, Dinitz Y, Ziv-Ukelson M.

Leave a Reply

Your email address will not be published. Required fields are marked *


This site uses Akismet to reduce spam. Learn how your comment data is processed.