Efficient seeded tree alignment algorithm for finding similarity between two RNA secondary structures

Abstract

This thesis presents an efficient O(n3) time algorithm for solving the seeded tree alignment problem that finds the similarity between two RNA secondary structures. In the seeded tree alignment problem, a large tree, representing an RNA secondary structure, is converted into a small tree known as seeded tree. In this problem, a comparison operation is being placed to find the similarity between necessary seed pair of two seeded trees and finally the overall trees. Before finding the similarity score between seed pairs, it is necessary to rearrange all primary seeds in planar way to form untanglegram whenever the primary seeds are arranged in heavily non planar way. Our proposed algorithm is more efficient than the best known algorithm that needs O(n3.5) time. Moreover, our algorithm can solve the seeded tree alignment problem efficiently in O(n3) time even if the two seeded trees form heavy tanglegram.