Structural alignment of pseudoknotted RNA

    Authors

    B. Han; B. Dost; V. Bafna;S. J. Zhang

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Comput. Biol.

    Keywords

    dynamic programming; pseudoknotted RNA; RNA alignment; RNA secondary; structure; SECONDARY STRUCTURE; INCLUDING PSEUDOKNOTS; STRUCTURE PREDICTION; NONCODING RNAS; ALGORITHM; GENES; Biochemical Research Methods; Biotechnology & Applied Microbiology; Computer Science, Interdisciplinary Applications; Mathematical &; Computational Biology; Statistics & Probability

    Abstract

    In this paper, we address the problem of discovering novel non-coding RNA (ncRNA) using primary sequence, and secondary structure conservation, focusing on ncRNA families with pseudoknotted structures. Our main technical result is an efficient algorithm for computing an optimum structural alignment of an RNA sequence against a genomic substring. This algorithm has two applications. First, by scanning a genome, we can identify novel (homologous) pseudoknotted ncRNA, and second, we can infer the secondary structure of the target aligned sequence. We test an implementation of our algorithm (PAL) and show that it has near-perfect behavior for predicting the structure of many known pseudoknots. Additionally, it can detect the true homologs with high sensitivity and specificity in controlled tests. We also use PAL to search entire viral genome and mouse genome for novel homologs of some viral and eukaryotic pseudoknots, respectively. In each case, we have found strong support for novel homologs.

    Journal Title

    Journal of Computational Biology

    Volume

    15

    Issue/Number

    5

    Publication Date

    1-1-2008

    Document Type

    Article

    Language

    English

    First Page

    489

    Last Page

    504

    WOS Identifier

    WOS:000257115500002

    ISSN

    1066-5277

    Share

    COinS