{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T12:12:11Z","timestamp":1768133531447,"version":"3.49.0"},"reference-count":53,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Alignment of RNA has a wide range of applications, for example in phylogeny inference, consensus structure prediction and homology searches. Yet aligning structural or non-coding RNAs (ncRNAs) correctly is notoriously difficult as these RNA sequences may evolve by compensatory mutations, which maintain base pairing but destroy sequence homology. Ideally, alignment programs would take RNA structure into account. The Sankoff algorithm for the simultaneous solution of RNA structure prediction and RNA sequence alignment was proposed 20 years ago but suffers from its exponential complexity. A number of programs implement lightweight versions of the Sankoff algorithm by restricting its application to a limited type of structure and\/or only pairwise alignment. Thus, despite recent advances, the proper alignment of multiple structural RNA sequences remains a problem.<\/jats:p>\n               <jats:p>Results: Here we present StrAl, a heuristic method for alignment of ncRNA that reduces sequence\u2013structure alignment to a two-dimensional problem similar to standard multiple sequence alignment. The scoring function takes into account sequence similarity as well as up- and downstream pairing probability. To test the robustness of the algorithm and the performance of the program, we scored alignments produced by StrAl against a large set of published reference alignments. The quality of alignments predicted by StrAl is far better than that obtained by standard sequence alignment programs, especially when sequence homologies drop below \u223c65%; nevertheless StrAl\u2019s runtime is comparable to that of ClustalW.<\/jats:p>\n               <jats:p>Availability: StrAl is implemented in C. Source code (under GNU public license) as well as a precompiled Debian package can be downloaded at<\/jats:p>\n               <jats:p>Contact: \u00a0stral@biophys.uni-duesseldorf.de<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl142","type":"journal-article","created":{"date-parts":[[2006,4,14]],"date-time":"2006-04-14T00:35:23Z","timestamp":1144974923000},"page":"1593-1599","source":"Crossref","is-referenced-by-count":56,"title":["S<scp>tr<\/scp>A<scp>l<\/scp>: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time"],"prefix":"10.1093","volume":"22","author":[{"given":"Deniz","family":"Dalli","sequence":"first","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, Institut f\u00fcr Physikalische Biologie \u00a0 D-40225 D\u00fcsseldorf, Germany"}]},{"given":"Andreas","family":"Wilm","sequence":"additional","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, Institut f\u00fcr Physikalische Biologie \u00a0 D-40225 D\u00fcsseldorf, Germany"}]},{"given":"Indra","family":"Mainz","sequence":"additional","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, Institut f\u00fcr Physikalische Biologie \u00a0 D-40225 D\u00fcsseldorf, Germany"}]},{"given":"Gerhard","family":"Steger","sequence":"additional","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, Institut f\u00fcr Physikalische Biologie \u00a0 D-40225 D\u00fcsseldorf, Germany"}]}],"member":"286","published-online":{"date-parts":[[2006,4,13]]},"reference":[{"key":"2023012408330383200_b1","first-page":"13","article-title":"RNA multi-structure landscapes. A study based on temperature dependent partition functions","volume":"22","author":"Bonhoeffer","year":"1993","journal-title":"Eur. Biophys. J."},{"key":"2023012408330383200_b2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1093\/oxfordjournals.molbev.a026231","article-title":"Weighted neighbor joining: A likelihood-based approach to distance-based phylogeny reconstruction","volume":"17","author":"Bruno","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"2023012408330383200_b3","first-page":"347","article-title":"Inferring consensus structure from nucleic acid sequences","volume":"7","author":"Chiu","year":"1991","journal-title":"Comput. Appl. Biosci."},{"key":"2023012408330383200_b4","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1038\/35103511","article-title":"Noncoding RNA genes and the modern RNA world","volume":"2","author":"Eddy","year":"2001","journal-title":"Nat. Rev. Genet."},{"key":"2023012408330383200_b5","article-title":"SQUID\u2014C function library for sequence analysis.","author":"Eddy","year":"2005"},{"key":"2023012408330383200_b6","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/1471-2105-3-18","article-title":"A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure","volume":"3","author":"Eddy","year":"2002","journal-title":"BMC Bioinformatics"},{"key":"2023012408330383200_b7","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1038\/nrm1647","article-title":"The catalytic diversity of RNAs","volume":"6","author":"Fedor","year":"2005","journal-title":"Nat. Rev. Mol. Cell. Biol."},{"key":"2023012408330383200_b8","first-page":"164","article-title":"PHYLIP\u2014Phylogeny Inference Package (Version 3.2)","volume":"5","author":"Felsenstein","year":"1989","journal-title":"Cladistics"},{"key":"2023012408330383200_b9","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1093\/sysbio\/46.1.101","article-title":"An alternating least squares approach to inferring phylogenies from pairwise distances","volume":"46","author":"Felsenstein","year":"1997","journal-title":"Syst. Biol."},{"key":"2023012408330383200_b10","article-title":"A gentle guide to multiple alignment","volume":"4","author":"Fuellen","year":"1997","journal-title":"Complexity International"},{"key":"2023012408330383200_b11","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b12","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1093\/oxfordjournals.molbev.a025808","article-title":"BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data","volume":"14","author":"Gascuel","year":"1997","journal-title":"Mol. Biol. Evol."},{"key":"2023012408330383200_b13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1006\/jmbi.1995.0200","article-title":"Identification of base-triples in RNA using comparative sequence analysis","volume":"248","author":"Gautheret","year":"1995","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b14","first-page":"361","article-title":"Optimal alignment between groups of sequences and its application to multiple sequence alignment","volume":"9","author":"Gotoh","year":"1993","journal-title":"Comput. Appl. Biosci."},{"key":"2023012408330383200_b15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0065-227X(99)80007-0","article-title":"Multiple sequence alignment: algorithms and applications","volume":"36","author":"Gotoh","year":"1999","journal-title":"Adv. Biophys."},{"key":"2023012408330383200_b16","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.tig.2005.05.008","article-title":"Micros for microbes: non-coding regulatory RNAs in bacteria","volume":"21","author":"Gottesmann","year":"2005","journal-title":"Trends Genet."},{"key":"2023012408330383200_b17","first-page":"57","article-title":"A computational approach to search for non-coding RNAs in large genomic data","volume-title":"Small RNAs: Analysis and Regulatory Functions, volume 17 of Nucleic Acids and Molecular Biology","author":"Gr\u00e4f","year":"2006"},{"key":"2023012408330383200_b18","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0076-6879(90)83011-W","article-title":"Profile analysis","volume":"183","author":"Gribskov","year":"1990","journal-title":"Methods Enzymol."},{"key":"2023012408330383200_b19","volume-title":"Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology","author":"Gusfield","year":"1999"},{"key":"2023012408330383200_b20","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","article-title":"Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%","volume":"21","author":"Havgaard","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b21","doi-asserted-by":"crossref","first-page":"W650","DOI":"10.1093\/nar\/gki473","article-title":"The FOLDALIGN web server for pairwise structural RNA alignment and mutual motif search","volume":"33","author":"Havgaard","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparsion of RNA structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem."},{"key":"2023012408330383200_b23","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","article-title":"Secondary structure prediction for aligned RNA sequences","volume":"319","author":"Hofacker","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b24","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","article-title":"Alignment of RNA base pairing probability matrices","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b25","doi-asserted-by":"crossref","first-page":"3429","DOI":"10.1093\/nar\/gkg599","article-title":"Vienna RNA secondary structure server","volume":"31","author":"Hofacker","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b26","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1471-2105-6-73","article-title":"Accelerated probabilistic inference of RNA structure evolution","volume":"6","author":"Holmes","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012408330383200_b27","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S1055-7903(03)00061-7","article-title":"RNA-based phylogenetic methods: application to mammalian mitochondrial RNA sequences","volume":"28","author":"Hudelot","year":"2003","journal-title":"Mol. Phylogenet. Evol."},{"key":"2023012408330383200_b28","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1093\/nar\/gki198","article-title":"MAFFT version 5: improvement in accuracy of multiple sequence alignment","volume":"33","author":"Katoh","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b29","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1186\/1471-2105-4-44","article-title":"RSEARCH: finding homologs of single structured RNA sequences","volume":"4","author":"Klein","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023012408330383200_b30","doi-asserted-by":"crossref","first-page":"3423","DOI":"10.1093\/nar\/gkg614","article-title":"Pfold: RNA secondary structure prediction using stochastic context-free grammars","volume":"31","author":"Knudsen","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b31","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1038\/sj.embor.7400126","article-title":"The prokaryotic selenoproteome","volume":"5","author":"Kryukov","year":"2004","journal-title":"EMBO Rep."},{"key":"2023012408330383200_b32","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/nar\/gki535","article-title":"Recurrent structural RNA motifs, isostericity matrices and sequence alignments","volume":"33","author":"Lescoute","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b33","doi-asserted-by":"crossref","first-page":"1505","DOI":"10.1093\/bioinformatics\/btg193","article-title":"A hidden Markov model for progressive multiple alignment","volume":"19","author":"L\u00f6ytynoja","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b34","doi-asserted-by":"crossref","first-page":"4208","DOI":"10.1093\/nar\/27.21.4208","article-title":"ConStruct: a tool for thermodynamic controlled prediction of conserved secondary structure","volume":"27","author":"L\u00fcck","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b35","doi-asserted-by":"crossref","first-page":"4116","DOI":"10.1093\/bioinformatics\/bti671","article-title":"Using information theory to search for co-evolving residues in proteins","volume":"21","author":"Martin","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","article-title":"Dynalign: an algorithm for finding the secondary structure common to two RNA sequences","volume":"317","author":"Mathews","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b37","doi-asserted-by":"crossref","first-page":"2246","DOI":"10.1093\/bioinformatics\/bti349","article-title":"Predicting a set of minimal free energy RNA secondary structures common to two sequences","volume":"21","author":"Mathews","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b38","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b39","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithm for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b40","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"2023012408330383200_b41","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"2023012408330383200_b42","doi-asserted-by":"crossref","first-page":"3352","DOI":"10.1093\/bioinformatics\/bti550","article-title":"MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons","volume":"21","author":"Siebert","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012408330383200_b43","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023012408330383200_b44","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"The University of Kansas Scientific Bulletin"},{"key":"2023012408330383200_b45","doi-asserted-by":"crossref","first-page":"1260","DOI":"10.1126\/science.1072249","article-title":"An expanding universe of noncoding RNAs","volume":"296","author":"Storz","year":"2002","journal-title":"Science"},{"key":"2023012408330383200_b46","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b47","first-page":"19","article-title":"Improved sensitivity of profile searches through the use of sequence weights and gap excision","volume":"10","author":"Thompson","year":"1994","journal-title":"Comput. Appl. Biosci."},{"key":"2023012408330383200_b48","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023012408330383200_b49","doi-asserted-by":"crossref","first-page":"2454","DOI":"10.1073\/pnas.0409169102","article-title":"Fast and reliable prediction of noncoding RNAs","volume":"102","author":"Washietl","year":"2005","journal-title":"Proc. Natl Acad. Sci. U.S.A."},{"key":"2023012408330383200_b50","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1146\/annurev.micro.59.030804.121336","article-title":"Regulation of bacterial gene expression by riboswitches","volume":"59","author":"Winkler","year":"2005","journal-title":"Ann. Rev. Microbiol."},{"key":"2023012408330383200_b51","first-page":"102","article-title":"StructMiner: a tool for alignment and detection of conserved secondary structure","volume":"15","author":"Yang","year":"2004","journal-title":"Genome Inform Ser Workshop Genome Inform."},{"key":"2023012408330383200_b52","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0959-440X(00)00088-9","article-title":"Calculating nucleic acid secondary structure","volume":"10","author":"Zuker","year":"2000","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012408330383200_b53","doi-asserted-by":"crossref","first-page":"3406","DOI":"10.1093\/nar\/gkg595","article-title":"Mfold web server for nucleic acid folding and hybridization prediction","volume":"31","author":"Zuker","year":"2003","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/13\/1593\/48838476\/bioinformatics_22_13_1593.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/13\/1593\/48838476\/bioinformatics_22_13_1593.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T08:51:47Z","timestamp":1674550307000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/13\/1593\/193786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4,13]]},"references-count":53,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2006,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl142","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,7,1]]},"published":{"date-parts":[[2006,4,13]]}}}