A Caltech Library Service

Fast Structural Alignment of RNAs by Optimizing the Adjoining Order of Profile-csHMMs

Yoon, Byung-Jun and Vaidyanathan, P. P. (2008) Fast Structural Alignment of RNAs by Optimizing the Adjoining Order of Profile-csHMMs. IEEE Journal of Selected Topics in Signal Processing, 2 (3). pp. 400-411. ISSN 1932-4553. doi:10.1109/JSTSP.2008.923846.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


A novel RNA structural alignment method has been proposed based on profile-csHMMs. In principle, the profile-csHMM based approach can handle any kind of RNA secondary structures including pseudoknots, and it has been shown that the proposed approach can find highly accurate RNA alignments. In order to find the optimal alignment, the method employs the SCA algorithm that can be used for finding the optimal state sequence of profile-csHMMs. The computational complexity of the SCA algorithm is not fixed, and it depends on the so-called adjoining order that describes how we can trace-back the optimal state sequence in a given profile-csHMM. Therefore, for fast RNA structural alignments, it is important to find the adjoining order that has the minimum computational cost. In this paper, we propose an efficient algorithm that can systematically find the optimal adjoining order that minimizes the computational cost for finding the RNA alignments. Numerical experiments show that employing the proposed algorithm can make the alignment speed up to 3.6 times faster, without any degradation in the quality of the RNA alignments.

Item Type:Article
Related URLs:
URLURL TypeDescription
Vaidyanathan, P. P.0000-0003-3003-7042
Additional Information:© Copyright 2008 IEEE. Manuscript received September 2, 2007; revised March 8, 2008. This work was supported in part by the National Science Foundation under Grant CCF-0636799. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Ahmed H. Tewfik.
Funding AgencyGrant Number
Subject Keywords:Profile-csHMM; pseudoknot; RNA homology search; RNA structural alignment; SCA algorithm
Issue or Number:3
Record Number:CaltechAUTHORS:20090916-153335340
Persistent URL:
Official Citation:Byung-Jun Yoon; Vaidyanathan, P.P., "Fast Structural Alignment of RNAs by Optimizing the Adjoining Order of Profile-csHMMs," Selected Topics in Signal Processing, IEEE Journal of , vol.2, no.3, pp.400-411, June 2008 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:15890
Deposited By: George Porter
Deposited On:23 Sep 2009 19:44
Last Modified:08 Nov 2021 23:23

Repository Staff Only: item control page