Comparing multiple RNA secondary structures using tree comparisons |
| |
| Authors: | Shapiro, Bruce A. Zhang, Kaizhong |
| |
| Affiliation: | Image Processing Section, Laboratory of Mathematical Biology, Division of Cancer Biology and Diagnosis, National Institutes of Health Frederick, MD 21701, USA
1Advanced Scientific Computer Laboratory Program Resources, Inc., National Cancer Institute, Frederick Cancer Research Facility, National Institutes of Health Frederick, MD 21701, USA |
| |
| Abstract: | In a previous paper, an algorithm was presented for analyzingmultiple RNA secondary structures utilizing a multiple stringalignment algorithm. In this paper we present another approachto the problem of comparing many secondary structures by utilizinga very efficient tree-matching algorithm that will compare twotrees in O(|T1|x|T2|x L1 x L2) in the worst case and very closeto O(|T1|x|T2|) for average trees representing secondary structures.The result of the pairwise comparison algorithm is then usedwith acluster algorithm to produce a multiple structure clusteringwhich can be displayed in ataxonomy tree to show related structures. Received on September 15, 1989; accepted on June 12, 1990 |
| |
| Keywords: | |
| 本文献已被 Oxford 等数据库收录！ |
|
