RNACluster: An integrated tool for RNA secondary structure comparison and clustering.

RNA structure comparison is a fundamental problem in structural biology, structural chemistry, and bioinformatics. It can be used for analysis of RNA energy landscapes, conformational switches, and facilitating RNA structure prediction. The purpose of our integrated tool RNACluster is twofold: to provide a platform for computing and comparison of different distances between RNA secondary structures, and to perform cluster identification to derive useful information of RNA structure ensembles, using a minimum spanning tree (MST) based clustering algorithm. RNACluster employs a cluster identification approach based on a MST representation of the RNA ensemble data and currently supports six distance measures between RNA secondary structures. RNACluster provides a user-friendly graphical interface to allow a user to compare different structural distances, analyze the structure ensembles, and visualize predicted structural clusters.

Protein fold recognition through application of residual dipolar coupling data.

Residual dipolar coupling (RDC) represents one of the most exciting emerging NMR techniques for studying protein structures. However, solving a protein structure using RDC data alone is a highly challenging problem as it often requires that the starting structure model be close to the actual structure of a protein, for the structure calculation procedure to be effective. We report in this paper a computer program, RDC-PROSPECT, for identification of a structural homolog or analog of a target protein in PDB, which best matches the 15N-1H RDC data of the protein recorded in a single ordering medium. The identified structural homolog/analog can then be used as a starting model for RDC-based structure calculation. Since RDC-PROSPECT uses only RDC data and predicted secondary structure information, its performance is virtually independent of sequence similarity between a target protein and its structural homolog/analog, making it applicable to protein targets out of the scope of current protein threading techniques. We have tested RDC-PROSPECT on all 15N-1H RDC data (representing 33 proteins) available in the BMRB database and the literature. The program correctly identified the structural folds for approximately 80% of the target proteins, significantly better than previously reported results, and achieved an average alignment accuracy of 97.9% residues within 4-residue shift. Through a careful algorithmic design, RDC-PROSPECT is at least one order of magnitude faster than previously reported algorithms for principal alignment frame search, making our algorithm fast enough for large-scale applications.

Minimum spanning trees for gene expression data clustering.

This paper describes a new framework for microarray gene-expression data clustering. The foundation of this framework is a minimum spanning tree (MST) representation of a set of multi-dimensional gene expression data. A key property of this representation is that each cluster of the expression data corresponds to one subtree of the MST, which rigorously converts a multi-dimensional clustering problem to a tree partitioning problem. We have demonstrated that though the inter-data relationship is greatly simplified in the MST representation, no essential information is lost for the purpose of clustering. Two key advantages in representing a set of multi-dimensional data as an MST are: (1) the simple structure of a tree facilitates efficient implementations of rigorous clustering algorithms, which otherwise are highly computationally challenging; and (2) as an MST-based clustering does not depend on detailed geometric shape of a cluster, it can overcome many of the problems faced by classical clustering algorithms. Based on the MST representation, we have developed a number of rigorous and efficient clustering algorithms, including two with guaranteed global optimality. We have implemented these algorithms as a computer software EXCAVATOR. To demonstrate its effectiveness, we have tested it on two data sets, i.e., expression data from yeast Saccharomyces cerevisiae, and Arabidopsis expression data in response to chitin elicitation.

An editing environment for DNA sequence analysis and annotation (extended abstract).

This paper presents a computer system for analyzing and annotating large-scale genomic sequences. The core of the system is a multiple-gene structure identification program, which predicts the most "probable" gene structures based on the given evidence, including pattern recognition, EST and protein homology information. A graphics-based user interface provides an environment which allows the user to interactively control the evidence to be used in the gene identification process. To overcome the computational bottleneck in the database similarity search used in the gene identification process, we have developed an effective way to partition a database into a set of sub-databases of "related" sequences, and reduced the search problem on a large database to a signature identification problem and a search problem on a much smaller sub-database. This reduces the number of sequences to be searched from N to O ([square root of] N) on average, and hence greatly reduces the search time, where N is the number of sequences in the original database. The system provides the user with the ability to facilitate and modify the analysis and modeling in real time.

Modeling the 3-D RNA distribution in the Balbiani ring granule.

Mature Balbiani Ring (BR) granules in situ were stained with the nucleic acid specific stain, osmium ammine-B, recorded by electron spectroscopic imaging and reconstructed by electron microscope tomography to examine the three-dimensional (3-D) distribution of BR heterogeneous nuclear RNA (hnRNA). The BR2 granules contain ca. 37 kb of mRNA. Reconstructed BR granules were selected to emphasize one of the prevalent conformations seen in the sectioned salivary glands, the en face or "pin-wheel" conformation. A variety of image processing and volume-rendering operations were applied to the set of reconstructed BR granules. Some of the conclusions of this study are the following: (1) RNA distribution is not uniform throughout the granule; (2) RNA is condensed into about ten particles per granule, which all appear to possess approximately the same RNA stain density; (3) heterogeneity exists in the positions and sizes of particles within the various BR granules. These data argue for the folding of a beaded ribbon, consisting of connected particulate condensations of BR mRNA, possessing considerable 3-D flexibility, even in the packaged state. A comparison of this beaded-ribbon model and a prior folded hnRNP fiber model is also presented.