Comparing multiple RNA secondary structures using tree comparisons

Abstract

In a previous paper, an algorithm was presented for analyzing multiple RNA secondary structures utilizing a multiple string alignment algorithm. In this paper we present another approach to the problem of comparing many secondary structures by utilizing a very efficient tree-matching algorithm that will compare two trees in O(|T₁|×|T₂|× L₁ × L₂) in the worst case and very close to O(|T₁|×|T₂|) for average trees representing secondary structures. The result of the pairwise comparison algorithm is then used with acluster algorithm to produce a multiple structure clustering which can be displayed in ataxonomy tree to show related structures.