RNAv: Non-Coding RNA Secondary Structure Variation Search via Graph Homomorphism

Zhibin Huang*, Russell L. Malmberg, Mohammad Mohebbi, Liming Cai

Department of Computer Science, University of Georgia Athens, GA 30602, U.S.A.. zbhuang@uga.edu

Proc LSS Comput Syst Bioinform Conf. August, 2010. Vol. 9, p. 56-69. Full-Text PDF

*To whom correspondence should be addressed.

Non-coding RNA (ncRNA) secondary structural homologs can be detected effectively in genomes with profile-based search methods. However, due to the lack of appropriate ncRNA structural evolution models, it is difficult to accurately detect distant structural homologs, i.e., ncRNA structures with variations caused by evolutionary changes such as the insertion or deletion of a substantial portion in the structure. This paper presents results of an investigation toward developing a new framework for distant ncRNA structural homolog search. In this work, secondary structure conformations are modeled as graphs with small tree width and sequence-structure alignment for homolog detection is formulated as graph homomorphism. The technique of NULL stem is used to resolve the issue of optional stems that may be deleted from the structure profile or may be a misalignment. Test results on 51 benchmark data sets of Infernal (9 of them containing pseudoknots) show that a program based on these methods, RNAv, with the capability of detecting pseudoknots, has a comparable performance to the latest version of Infernal, and is better in detection of some distant homologs.