{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T02:31:47Z","timestamp":1791081107344,"version":"4.1.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T00:00:00Z","timestamp":1111622400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T00:00:00Z","timestamp":1111622400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>Pairwise stochastic context-free grammars (Pair SCFGs) are powerful tools for evolutionary analysis of RNA, including simultaneous RNA sequence alignment and secondary structure prediction, but the associated algorithms are intensive in both CPU and memory usage. The same problem is faced by other RNA alignment-and-folding algorithms based on Sankoff's 1985 algorithm. It is therefore desirable to constrain such algorithms, by pre-processing the sequences and using this first pass to limit the range of structures and\/or alignments that can be considered.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We demonstrate how flexible classes of constraint can be imposed, greatly reducing the computational costs while maintaining a high quality of structural homology prediction. Any score-attributed context-free grammar (e.g. energy-based scoring schemes, or conditionally normalized Pair SCFGs) is amenable to this treatment. It is now possible to combine independent structural and alignment constraints of unprecedented general flexibility in Pair SCFG alignment algorithms. We outline several applications to the bioinformatics of RNA sequence and structure, including Waterman-Eggert N-best alignments and progressive multiple alignment. We evaluate the performance of the algorithm on test examples from the RFAM database.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>A program, Stemloc, that implements these algorithms for efficient RNA sequence alignment and structure prediction is available under the GNU General Public License.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-73","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T07:16:08Z","timestamp":1111734968000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":95,"title":["Accelerated probabilistic inference of RNA structure evolution"],"prefix":"10.1186","volume":"6","author":[{"given":"Ian","family":"Holmes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,3,24]]},"reference":[{"issue":"6","key":"398_CR1","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0959-437X(99)00022-2","volume":"9","author":"SR Eddy","year":"1999","unstructured":"Eddy SR: Noncoding RNA genes. Current Opinion in Genetics and Development 1999, 9(6):695\u2013699. 10.1016\/S0959-437X(99)00022-2","journal-title":"Current Opinion in Genetics and Development"},{"key":"398_CR2","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/S0092-8674(03)00391-X","volume":"113","author":"M Mandal","year":"2003","unstructured":"Mandal M, Boese B, Barrick JE, Winkler WC, Breaker RR: Riboswitches Control Fundamental Biochemical Pathways in Bacillus subtilis and Other Bacteria. Cell 2003, 113: 577\u2013586. 10.1016\/S0092-8674(03)00391-X","journal-title":"Cell"},{"issue":"6964","key":"398_CR3","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1038\/nature02107","volume":"426","author":"T Sijen","year":"2003","unstructured":"Sijen T, Plasterk RH: Transposon silencing in the Caenorhabditis elegans germ line by natural RNAi. Nature 2003, 426(6964):310\u2013314. 10.1038\/nature02107","journal-title":"Nature"},{"issue":"7006","key":"398_CR4","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1038\/nature02871","volume":"431","author":"V Ambros","year":"2004","unstructured":"Ambros V: The functions of animal microRNAs. Nature 2004, 431(7006):350\u2013355. 10.1038\/nature02871","journal-title":"Nature"},{"issue":"7006","key":"398_CR5","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1038\/nature02874","volume":"431","author":"D Baulcombe","year":"2004","unstructured":"Baulcombe D: RNA silencing in plants. Nature 2004, 431(7006):356\u2013363. 10.1038\/nature02874","journal-title":"Nature"},{"issue":"7","key":"398_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1093\/bioinformatics\/16.7.583","volume":"16","author":"E Rivas","year":"2000","unstructured":"Rivas E, Eddy SR: Secondary structure alone is generally not statistically significant for the detection of noncoding RNAs. Bioinformatics 2000, 16(7):583\u2013605. 10.1093\/bioinformatics\/16.7.583","journal-title":"Bioinformatics"},{"key":"398_CR7","doi-asserted-by":"publisher","first-page":"12102","DOI":"10.1073\/pnas.0404193101","volume":"101","author":"A Coventry","year":"2004","unstructured":"Coventry A, Kleitman DJ, Berger B: MSARI: Multiple sequence alignments for statistical detection of RNA secondary structure. Proceedings of the National Academy of Sciences of the USA 2004, 101: 12102\u201312107. 10.1073\/pnas.0404193101","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"issue":"6","key":"398_CR8","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1093\/bioinformatics\/15.6.446","volume":"15","author":"B Knudsen","year":"1999","unstructured":"Knudsen B, Hein J: RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics 1999, 15(6):446\u2013454. 10.1093\/bioinformatics\/15.6.446","journal-title":"Bioinformatics"},{"key":"398_CR9","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/1471-2105-2-8","volume":"2","author":"E Rivas","year":"2001","unstructured":"Rivas E, Eddy SR: Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2001, 2: 8. 10.1186\/1471-2105-2-8","journal-title":"BMC Bioinformatics"},{"issue":"18","key":"398_CR10","doi-asserted-by":"publisher","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","volume":"25","author":"J Gorodkin","year":"1997","unstructured":"Gorodkin J, Heyer LJ, Stormo GD: Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucleic Acids Research 1997, 25(18):3724\u20133732. 10.1093\/nar\/25.18.3724","journal-title":"Nucleic Acids Research"},{"issue":"2","key":"398_CR11","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","volume":"317","author":"DH Mathews","year":"2002","unstructured":"Mathews DH, Turner DH: Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. Journal of Molecular Biology 2002, 317(2):191\u2013203. 10.1006\/jmbi.2001.5351","journal-title":"Journal of Molecular Biology"},{"key":"398_CR12","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1093\/bioinformatics\/19.1.108","volume":"19","author":"O Perriquet","year":"2003","unstructured":"Perriquet O, Touzet H, Dauchet M: Finding the common structure shared by two homologous RNAs. Bioinformatics 2003, 19: 108\u2013116. 10.1093\/bioinformatics\/19.1.108","journal-title":"Bioinformatics"},{"key":"398_CR13","first-page":"163","volume-title":"Pac Symp Biocomput","author":"I Holmes","year":"2002","unstructured":"Holmes I, Rubin GM: Pairwise RNA structure comparison using stochastic context-free grammars. Pac Symp Biocomput 2002, 163\u2013174."},{"key":"398_CR14","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D: Simultaneous solution of the RNA folding, alignment, and protosequence problems. SIAM Journal of Applied Mathematics 1985, 45: 810\u2013825. 10.1137\/0145048","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"398_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P: Optimal Computer Folding of Large RNA Sequences Using Thermodynamics and Auxiliary Information. Nucleic Acids Research 1981, 9: 133\u2013148.","journal-title":"Nucleic Acids Research"},{"key":"398_CR16","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","volume":"22","author":"SR Eddy","year":"1994","unstructured":"Eddy SR, Durbin R: RNA Sequence Analysis Using Covariance Models. Nucleic Acids Research 1994, 22: 2079\u20132088.","journal-title":"Nucleic Acids Research"},{"key":"398_CR17","doi-asserted-by":"publisher","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","volume":"22","author":"Y Sakakibara","year":"1994","unstructured":"Sakakibara Y, Brown M, Hughey R, Mian IS, Sj\u00f6lander K, Underwood RC, Haussler D: Stochastic Context-Free Grammars for tRNA Modeling. Nucleic Acids Research 1994, 22: 5112\u20135120.","journal-title":"Nucleic Acids Research"},{"key":"398_CR18","volume-title":"RNA Pseudoknot Modeling Using Intersections of Stochastic Context-Free Grammars with Applications to Database Search","author":"M Brown","year":"1995","unstructured":"Brown M, Wilson C: RNA Pseudoknot Modeling Using Intersections of Stochastic Context-Free Grammars with Applications to Database Search.1995. [http:\/\/www.cse.ucsc.edu\/research\/compbio\/pseudoknot.html]"},{"key":"398_CR19","first-page":"143","volume-title":"Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology","author":"F Lefebvre","year":"1996","unstructured":"Lefebvre F: A Grammar-Based Unification of Several Alignment and Folding Algorithms. In Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology. Edited by: States DJ, Agarwal P, Gaasterland T, Hunter L, Smith RF, Menlo Park. CA: AAAI Press; 1996:143\u2013154."},{"key":"398_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge, UK: Cambridge University Press; 1998."},{"issue":"14","key":"398_CR21","doi-asserted-by":"publisher","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","volume":"20","author":"IL Hofacker","year":"2004","unstructured":"Hofacker IL, Bernhart SH, Stadler PF: Alignment of RNA base pairing probability matrices. Bioinformatics 2004, 20(14):2222\u20132227. 10.1093\/bioinformatics\/bth229","journal-title":"Bioinformatics"},{"key":"398_CR22","volume-title":"Generic Programming and the STL: Using and Extending the C++ Standard Template Library","author":"MH Austern","year":"1999","unstructured":"Austern MH: Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley; 1999."},{"key":"398_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS: Identification of Common Molecular Subsequences. Journal of Molecular Biology 1981, 147: 195\u2013197. 10.1016\/0022-2836(81)90087-5","journal-title":"Journal of Molecular Biology"},{"key":"398_CR24","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","volume":"197","author":"MS Waterman","year":"1987","unstructured":"Waterman MS, Eggert M: A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons. Journal of Molecular Biology 1987, 197: 723\u2013725. 10.1016\/0022-2836(87)90478-5","journal-title":"Journal of Molecular Biology"},{"key":"398_CR25","first-page":"151","volume":"5","author":"DG Higgins","year":"1989","unstructured":"Higgins DG, Sharp PM: Fast and Sensitive Multiple Sequence Alignments on a Microcomputer. Computer Applications in the Biosciences 1989, 5: 151\u2013153.","journal-title":"Computer Applications in the Biosciences"},{"key":"398_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0885-2308(90)90022-X","volume":"4","author":"K Lari","year":"1990","unstructured":"Lari K, Young SJ: The Estimation of Stochastic Context-Free Grammars Using the Inside-Outside Algorithm. Computer Speech and Language 1990, 4: 35\u201356. 10.1016\/0885-2308(90)90022-X","journal-title":"Computer Speech and Language"},{"key":"398_CR27","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS: The Equilibrium Partition Function and Base Pair Binding Probabilities for RNA Secondary Structure. Biopolymers 1990, 29: 1105\u20131119. 10.1002\/bip.360290621","journal-title":"Biopolymers"},{"key":"398_CR28","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/0022-2836(91)90193-A","volume":"219","author":"SF Altschul","year":"1991","unstructured":"Altschul SF: Amino Acid Substitution Matrices from an Information Theoretic Perspective. Journal of Molecular Biology 1991, 219: 555\u2013565. 10.1016\/0022-2836(91)90193-A","journal-title":"Journal of Molecular Biology"},{"key":"398_CR29","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N Chomsky","year":"1956","unstructured":"Chomsky N: Three Models for the Description of Language. IRE Transactions Information Theory 1956, 2: 113\u2013124. 10.1109\/TIT.1956.1056813","journal-title":"IRE Transactions Information Theory"},{"key":"398_CR30","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N Chomsky","year":"1959","unstructured":"Chomsky N: On Certain Formal Properties of Grammars. Information and Control 1959, 2: 137\u2013167. 10.1016\/S0019-9958(59)90362-6","journal-title":"Information and Control"},{"key":"398_CR31","volume-title":"PhD thesis","author":"I Holmes","year":"1998","unstructured":"Holmes I: Studies in probabilistic sequence alignment and evolution. PhD thesis. The Sanger Centre; 1998."},{"issue":"4","key":"398_CR32","first-page":"309","volume":"6","author":"BA Shapiro","year":"1990","unstructured":"Shapiro BA, Zhang KZ: Comparing multiple RNA secondary structures using tree comparisons. Computer Applications in the Biosciences 1990, 6(4):309\u2013318.","journal-title":"Computer Applications in the Biosciences"},{"key":"398_CR33","doi-asserted-by":"crossref","unstructured":"Klein R, Eddy SR: Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2003., 4(44):","DOI":"10.1186\/1471-2105-4-44"},{"key":"398_CR34","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-45123-4_6","volume-title":"Combinatorial Pattern Matching: 11th Annual Symposium","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: Explaining and Controlling Ambiguity in Dynamic Programming. In Combinatorial Pattern Matching: 11th Annual Symposium. Volume 1848. Edited by: Giancarlo R, Sankoff D. Springer-Verlag Heidelberg; 2000:46\u201359."},{"key":"398_CR35","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"RD Dowell","year":"2004","unstructured":"Dowell RD, Eddy SR: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics 2004, 5: 71. 10.1186\/1471-2105-5-71","journal-title":"BMC Bioinformatics"},{"key":"398_CR36","volume-title":"BMC Bioinformatics","author":"I Holmes","year":"2004","unstructured":"Holmes I: A probabilistic model for the evolution of RNA structure. BMC Bioinformatics 2004., 5(166):"},{"key":"398_CR37","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1093\/nar\/gkg006","volume":"31","author":"S Griffiths-Jones","year":"2003","unstructured":"Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR: Rfam: an RNA family database. Nucleic Acids Research 2003, 31: 439\u2013441. 10.1093\/nar\/gkg006","journal-title":"Nucleic Acids Research"},{"issue":"3","key":"398_CR38","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","volume":"5","author":"I Holmes","year":"1998","unstructured":"Holmes I, Durbin R: Dynamic programming alignment accuracy. Journal of Computational Biology 1998, 5(3):493\u2013504.","journal-title":"Journal of Computational Biology"},{"key":"398_CR39","unstructured":"Do CB, Brudno M, Batzoglou S: PROBCONS: Probabilistic Consistency-based Multiple Alignment of Amino Acid Sequences. , in press."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-73.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-73\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-73.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:09:11Z","timestamp":1728302951000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3,24]]},"references-count":39,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["398"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-73","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3,24]]},"assertion":[{"value":"30 April 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"73"}}