| Abstract: |
The use of free energy-based algorithms to compute RNA secondary structures produces, in general, large numbers of foldings. Recent research has addressed the problem of grouping structures into a small number of clusters and computing a representative folding for each cluster. At the heart of this problem is the need to compute a quantity that measures the difference between pairs of foldings. We introduce a new concept, the relaxed base-pair (RBP) score, designed to give a more biologically realistic measure of the difference between structures than the base-pair (BP) metric, which simply counts the number of base pairs in one structure but not the other. The degree of relaxation is determined by a single relaxation parameter, t. When t = 0, (no relaxation) our method is the same as the BP metric. At the other extreme, a very large value of t will give a distance of 0 for identical structures and 1 for structures that differ. Scores can be recomputed with different values of t, at virtually no extra computation cost, to yield satisfactory results. Our results indicate that relaxed measures give more stable and more meaningful clusters than the BP metric. We also use the RBP score to compute representative foldings for each cluster. Copyright © 2010 RNA Society. |
| Keywords: |
cluster analysis; computational biology; analytic method; algorithms; rna; messenger rna; rna, messenger; nucleotide sequence; measurement; base pairing; models, molecular; thermodynamics; rna stability; nucleic acid conformation; protein secondary structure; rna structure; structure analysis; stochastic processes; phylogeny; base-pair metric; centroid structure; cluster; consensus structure; k-means clustering; medioid structure; minimum free energy structure; relaxed base-pair score; representative structure; rna secondary structure; spectral clustering; relaxed base pair score; haloarcula; methanobacteriaceae; rna, archaeal; rna, ribosomal, 5s
|
