Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%
Open Access
- 18 January 2005
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 21 (9) , 1815-1824
- https://doi.org/10.1093/bioinformatics/bti279
Abstract
Motivation: Searching for non-coding RNA (ncRNA) genes and structural RNA elements (eleRNA) are major challenges in gene finding today as these often are conserved in structure rather than in sequence. Even though the number of available methods is growing, it is still of interest to pairwise detect two genes with low sequence similarity, where the genes are part of a larger genomic region. Results: Here we present such an approach for pairwise local alignment which is based on foldalign and the Sankoff algorithm for simultaneous structural alignment of multiple sequences. We include the ability to conduct mutual scans of two sequences of arbitrary length while searching for common local structural motifs of some maximum length. This drastically reduces the complexity of the algorithm. The scoring scheme includes structural parameters corresponding to those available for free energy as well as for substitution matrices similar to RIBOSUM. The new foldalign implementation is tested on a dataset where the ncRNAs and eleRNAs have sequence similarity Availability: The program is available online at http://foldalign.kvl.dk/ Contact:gorodkin@bioinf.kvl.dkKeywords
This publication has 47 references indexed in Scilit:
- Alignment of RNA base pairing probability matricesBioinformatics, 2004
- Rfam: an RNA family databaseNucleic Acids Research, 2003
- A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structureBMC Bioinformatics, 2002
- Secondary Structure Prediction for Aligned RNA SequencesJournal of Molecular Biology, 2002
- Computational Genomics of Noncoding RNA GenesCell, 2002
- Semi-automated update and cleanup of structural RNA alignment databasesBioinformatics, 2001
- Discovering common stem-loop motifs in unaligned RNA sequencesNucleic Acids Research, 2001
- The estimation of statistical parameters for local alignment score distributionsNucleic Acids Research, 2001
- Finding the most significant common sequence and structure motifs in a set of RNA sequencesNucleic Acids Research, 1997
- Amino acid substitution matrices from protein blocks.Proceedings of the National Academy of Sciences, 1992