Unknown

Dataset Information

0

R-PASS: A Fast Structure-based RNA Sequence Alignment Algorithm.


ABSTRACT: We present a fast pairwise RNA sequence alignment method using structural information, named R-PASS (RNA Pairwise Alignment of Structure and Sequence), which shows good accuracy on sequences with low sequence identity and significantly faster than alternative methods. The method begins by representing RNA secondary structure as a set of structure motifs. The motifs from two RNAs are then used as input into a bipartite graph-matching algorithm, which determines the structure matches. The matches are then used as constraints in a constrained dynamic programming sequence alignment procedure. The R-PASS method has an O(nm) complexity. We compare our method with two other structure-based alignment methods, LARA and ExpaLoc, and with a sequence-based alignment method, MAFFT, across three benchmarks and obtain favorable results in accuracy and orders of magnitude faster in speed.

SUBMITTER: Jiang Y 

PROVIDER: S-EPMC3999979 | biostudies-literature | 2011 Dec

REPOSITORIES: biostudies-literature

altmetric image

Publications

R-PASS: A Fast Structure-based RNA Sequence Alignment Algorithm.

Jiang Yanan Y   Xu Weijia W   Thompson Lee Parnell LP   Gutell Robin R RR   Miranker Daniel P DP  

Proceedings. IEEE International Conference on Bioinformatics and Biomedicine 20111201


We present a fast pairwise RNA sequence alignment method using structural information, named R-PASS (RNA Pairwise Alignment of Structure and Sequence), which shows good accuracy on sequences with low sequence identity and significantly faster than alternative methods. The method begins by representing RNA secondary structure as a set of structure motifs. The motifs from two RNAs are then used as input into a bipartite graph-matching algorithm, which determines the structure matches. The matches  ...[more]

Similar Datasets

| S-EPMC3638164 | biostudies-other
| S-EPMC147093 | biostudies-other
| S-EPMC3934876 | biostudies-literature
| S-EPMC5946935 | biostudies-literature
| S-EPMC3154205 | biostudies-literature
| S-EPMC2677745 | biostudies-literature
| S-EPMC1579236 | biostudies-literature
| S-EPMC4395267 | biostudies-literature
| S-EPMC6007556 | biostudies-literature
| S-EPMC8355039 | biostudies-literature