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.
- Linux / Mac / Windows
:: MORE INFORMATION
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.