Fast and accurate search for non-coding RNA pseudoknot structures in genomes.

ABSTRACT:

Motivation

Searching genomes for non-coding RNAs (ncRNAs) by their secondary structure has become an important goal for bioinformatics. For pseudoknot-free structures, ncRNA search can be effective based on the covariance model and CYK-type dynamic programming. However, the computational difficulty in aligning an RNA sequence to a pseudoknot has prohibited fast and accurate search of arbitrary RNA structures. Our previous work introduced a graph model for RNA pseudoknots and proposed to solve the structure-sequence alignment by graph optimization. Given k candidate regions in the target sequence for each of the n stems in the structure, we could compute a best alignment in time O(k(t)n) based upon a tree width t decomposition of the structure graph. However, to implement this metho

SUBMITTER: Huang Z 

PROVIDER: S-EPMC2562014 | biostudies-literature | 2008 Oct

REPOSITORIES: biostudies-literature