使用树状比较法比较多个RNA二级结构

Comparing multiple RNA secondary structures using tree comparisons.

作者信息

Shapiro B A, Zhang K Z

机构信息

Image Processing Section, National Cancer Institute, National Institutes of Health, Frederick, MD 21701.

出版信息

Comput Appl Biosci. 1990 Oct;6(4):309-18. doi: 10.1093/bioinformatics/6.4.309.

DOI:10.1093/bioinformatics/6.4.309

PMID:1701685

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([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.

摘要

在之前的一篇论文中，提出了一种利用多序列比对算法来分析多个RNA二级结构的算法。在本文中，我们提出了另一种解决比较多个二级结构问题的方法，即利用一种非常高效的树匹配算法，该算法在最坏情况下以O([T1]×[T2]×L1×L2)的时间复杂度比较两棵树，对于表示二级结构的平均树而言，其时间复杂度非常接近O([T1]×[T2])。然后，将成对比较算法的结果与聚类算法一起使用，以生成多个结构聚类，这些聚类可以显示在分类树中以展示相关结构。