Comparing multiple RNA secondary structures using tree comparisons.
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([T1] X [T2] X L1 X L2) in the worst case and very close to O([T1] X [T2]) for average trees representing secondary structures. The result of the pairwise comparison algorithm is then used with a cluster algorithm to produce a multiple structure clustering which can be displayed in a taxonomy tree to show related structures.
Image Processing Section, National Cancer Institute, National Institutes of Health, Frederick, MD 21701.
B A
BA
Shapiro
K Z
KZ
Zhang
D000465:Algorithms; D001483:Base Sequence; D008432:Mathematical Computing; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry / Q000648:ultrastructure*; D012984:Software
D012313:RNA