{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T19:23:45Z","timestamp":1770233025203,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Aligning multiple RNA sequences is essential for analyzing non-coding RNAs. Although many alignment methods for non-coding RNAs, including Sankoff's algorithm for strict structural alignments, have been proposed, they are either inaccurate or computationally too expensive. Faster methods with reasonable accuracies are required for genome-scale analyses.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We propose a fast algorithm for multiple structural alignments of RNA sequences that is an extension of our pairwise structural alignment method (implemented in SCARNA). The accuracies of the implemented software, MXSCARNA, are at least as favorable as those of state-of-art algorithms that are computationally much more expensive in time and memory.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>The proposed method for structural alignment of multiple RNA sequences is fast enough for large-scale analyses with accuracies at least comparable to those of existing algorithms. The source code of MXSCARNA and its web server are available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/mxscarna.ncrna.org\" ext-link-type=\"uri\">http:\/\/mxscarna.ncrna.org<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-33","type":"journal-article","created":{"date-parts":[[2008,1,25]],"date-time":"2008-01-25T19:13:24Z","timestamp":1201288404000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":97,"title":["A fast structural multiple alignment method for long RNA sequences"],"prefix":"10.1186","volume":"9","author":[{"given":"Yasuo","family":"Tabei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hisanori","family":"Kiryu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taishin","family":"Kin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,23]]},"reference":[{"issue":"5","key":"2018_CR1","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"DH Mathews","year":"1999","unstructured":"Mathews DH, Sabina J, Zuker M, Turner DH: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol 1999, 288(5):911\u2013940. 10.1006\/jmbi.1999.2700","journal-title":"J Mol Biol"},{"key":"2018_CR2","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs JR, Kleitman DJ: Algorithms for loop matchings. SIAM J App Math 1978, 35: 68\u201382. 10.1137\/0135006","journal-title":"SIAM J App Math"},{"key":"2018_CR3","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. Nucl Acids Research 1981, 9: 133\u2013148. 10.1093\/nar\/9.1.133","journal-title":"Nucl Acids Research"},{"key":"2018_CR4","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","volume":"319","author":"I Hofacker","year":"2002","unstructured":"Hofacker I, Fekete M, Stadler P: Secondary structure prediction for aligned RNA sequences. J Mol Biol 2002, 319: 1059\u20131066. 10.1016\/S0022-2836(02)00308-X","journal-title":"J Mol Biol"},{"key":"2018_CR5","doi-asserted-by":"publisher","first-page":"3423","DOI":"10.1093\/nar\/gkg614","volume":"31","author":"B Knudsen","year":"2003","unstructured":"Knudsen B, Hein J: Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucl Acids Res 2003, 31: 3423\u20133428. 10.1093\/nar\/gkg614","journal-title":"Nucl Acids Res"},{"key":"2018_CR6","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1093\/bioinformatics\/btl636","volume":"23","author":"H Kiryu","year":"2006","unstructured":"Kiryu H, Kin T, Asai K: Robust prediction of consensus secondary structures using averaged base pairing probability matrices. Bioinformatics 2006, 23: 434\u2013441. 10.1093\/bioinformatics\/btl636","journal-title":"Bioinformatics"},{"key":"2018_CR7","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","volume":"27","author":"J Thompson","year":"1999","unstructured":"Thompson J: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res 1999, 27: 2682\u20132690. 10.1093\/nar\/27.13.2682","journal-title":"Nucleic Acids Res"},{"key":"2018_CR8","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1093\/bioinformatics\/14.3.290","volume":"14","author":"B Morgenstern","year":"1998","unstructured":"Morgenstern B: DIALIGN: finding local similarities by multiple sequence alignment. Bioinformatics 1998, 14: 290\u2013294. 10.1093\/bioinformatics\/14.3.290","journal-title":"Bioinformatics"},{"key":"2018_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins DG, Heringa J: T-Coffee: A Novel Method for Fast and Accurate Multiple Sequence Alignment. Journal of Molecular Biology 2000, 302: 205\u2013217. 10.1006\/jmbi.2000.4042","journal-title":"Journal of Molecular Biology"},{"key":"2018_CR10","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 proto-sequence problems. SIAM J App Math 1985, 45: 810\u2013825. 10.1137\/0145048","journal-title":"SIAM J App Math"},{"issue":"9","key":"2018_CR11","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","volume":"21","author":"JH Havgaard","year":"2005","unstructured":"Havgaard JH, Lyngs\u00f8 RB, Stormo GD, Gorodkin J: Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics 2005, 21(9):1815\u20131824. 10.1093\/bioinformatics\/bti279","journal-title":"Bioinformatics"},{"key":"2018_CR12","doi-asserted-by":"publisher","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","volume":"20","author":"I Hofacker","year":"2004","unstructured":"Hofacker I, Bernhart S, Stadler P: Alignment of RNA base pairing probability matrices. Bioinformatics 2004, 20: 2222\u20132227. 10.1093\/bioinformatics\/bth229","journal-title":"Bioinformatics"},{"key":"2018_CR13","doi-asserted-by":"crossref","unstructured":"Holmes I: A probabilistic model for the evolution of RNA structure. BMC Bioinformatics 2004., 5(166):","DOI":"10.1186\/1471-2105-5-166"},{"key":"2018_CR14","first-page":"163","volume-title":"Pacific Symposium on Biocomputing","author":"I Holmes","year":"2002","unstructured":"Holmes I, Rubin GM: Pairwise RNA structure comparison with stochastic context-free grammars. Pacific Symposium on Biocomputing 2002, 163\u2013174."},{"key":"2018_CR15","doi-asserted-by":"crossref","unstructured":"Torarinsson E, Havgaard JH, Gorodkin J: Multiple structural alignment and clustering of RNA sequences. Bioinformatics 23: 926\u2013932(7). 15 April 2007 10.1093\/bioinformatics\/btm049","DOI":"10.1093\/bioinformatics\/btm049"},{"issue":"4","key":"2018_CR16","doi-asserted-by":"publisher","first-page":"e65+","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S Will","year":"2007","unstructured":"Will S, Reiche K, Hofacker I, Stadler P, Backofen R: Inferring Noncoding RNA Families and Classes by Means of Genome-Scale Structure-Based Clustering. PLoS Computational Biology 2007, 3(4):e65+. 10.1371\/journal.pcbi.0030065","journal-title":"PLoS Computational Biology"},{"key":"2018_CR17","doi-asserted-by":"publisher","first-page":"3352","DOI":"10.1093\/bioinformatics\/bti550","volume":"21","author":"S Siebert","year":"2005","unstructured":"Siebert S, Backofen R: MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence strcture comparisons. Bioinformatics 2005, 21: 3352\u20133359. 10.1093\/bioinformatics\/bti550","journal-title":"Bioinformatics"},{"issue":"13","key":"2018_CR18","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1093\/bioinformatics\/btl142","volume":"22","author":"D Dalli","year":"2006","unstructured":"Dalli D, Wilm A, Mains I, Steger G: STRAL:Progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time. Bioinformatics 2006, 22(13):1593\u20131599. 10.1093\/bioinformatics\/btl142","journal-title":"Bioinformatics"},{"key":"2018_CR19","doi-asserted-by":"publisher","first-page":"1883","DOI":"10.1093\/bioinformatics\/btm272","volume":"23","author":"X Xu","year":"2007","unstructured":"Xu X, Ji Y, Stormo GD: RNASmpler: a new sampling based algorithm for common RNA secondary structure prediction and structure alignment. Bioinformaitcs 2007, 23: 1883\u20131891(15). 10.1093\/bioinformatics\/btm272","journal-title":"Bioinformaitcs"},{"key":"2018_CR20","volume-title":"BMC Bioinformatics","author":"M Bauer","year":"2007","unstructured":"Bauer M, Klau GW, Reinert K: Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics 2007., 8:"},{"key":"2018_CR21","doi-asserted-by":"publisher","first-page":"1588","DOI":"10.1093\/bioinformatics\/btm146","volume":"23","author":"H Kiryu","year":"2007","unstructured":"Kiryu H, Tabei Y, Taishin K, Asai K: Murlet: a practical multiple alignment tool for structural RNA sequences. Bioinformatics 2007, 23: 1588\u20131598. 10.1093\/bioinformatics\/btm146","journal-title":"Bioinformatics"},{"key":"2018_CR22","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1186\/1471-2105-7-498","volume":"7","author":"PN Seibel","year":"2006","unstructured":"Seibel PN, M\u00fcller T, Dandekar T, Schultz J, Wolf M: 4SALE \u2013 A tool for synchronous RNA sequence and secondary structure alignment and editing. BMC Bioinformaitcs 2006, 7: 498. 10.1186\/1471-2105-7-498","journal-title":"BMC Bioinformaitcs"},{"key":"2018_CR23","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1093\/bioinformatics\/btk008","volume":"22","author":"Z Yao","year":"2006","unstructured":"Yao Z, Weinberg Z, Ruzzo W: CMfinder \u2013 a covariance model besed RNA motif finding algorithm. Bioinformaitcs 2006, 22: 445\u2013452. 10.1093\/bioinformatics\/btk008","journal-title":"Bioinformaitcs"},{"key":"2018_CR24","doi-asserted-by":"publisher","first-page":"2480","DOI":"10.1093\/bioinformatics\/btl431","volume":"22","author":"M Hamada","year":"2006","unstructured":"Hamada M, Tsuda K, Kudo T, Kin T, Asai K: Mining frequent stem patterns from unaligned RNA sequences. Bioinformaitcs 2006, 22: 2480\u20132487. 10.1093\/bioinformatics\/btl431","journal-title":"Bioinformaitcs"},{"key":"2018_CR25","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1093\/bioinformatics\/btl177","volume":"22","author":"Y Tabei","year":"2006","unstructured":"Tabei Y, Tsuda K, Taishin K, Asai K: SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments. Bioinformatics 2006, 22: 1723\u20131729. 10.1093\/bioinformatics\/btl177","journal-title":"Bioinformatics"},{"key":"2018_CR26","first-page":"1409","volume":"28","author":"RR Sokal","year":"1958","unstructured":"Sokal RR, Michener CD: A statistical method for evaluating systematic relationships. University of Kansas Scientific Bulletin 1958, 28: 1409\u20131438.","journal-title":"University of Kansas Scientific Bulletin"},{"key":"2018_CR27","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"J McCaskill","year":"1990","unstructured":"McCaskill J: 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":"2018_CR28","doi-asserted-by":"crossref","unstructured":"Klein R, Eddy S: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics 2003., 4(44):","DOI":"10.1186\/1471-2105-4-44"},{"key":"2018_CR29","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1093\/protein\/8.10.999","volume":"8","author":"S Miyazawa","year":"1995","unstructured":"Miyazawa S: A reliable sequence alignment method based on probabilities of residue correspondences. Protein Engineering 1995, 8: 999\u20131009. 10.1093\/protein\/8.10.999","journal-title":"Protein Engineering"},{"key":"2018_CR30","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. J Comput Biol 1998, 5: 493\u2013504.","journal-title":"J Comput Biol"},{"key":"2018_CR31","volume-title":"Biological Sequence Analysis","author":"R Durbin AKSR Eddy","year":"1998","unstructured":"Eddy R DurbinAKSR, Mitchison G: Biological Sequence Analysis. Chambridge, UK: Chambridge University Press; 1998."},{"issue":"2","key":"2018_CR32","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1101\/gr.2821705","volume":"15","author":"CB Do","year":"2005","unstructured":"Do CB, Mahabhashyam MS, Brudno M, Batzoglou S: ProbCons: Probabilistic consistency-based multiple sequence alignment. Genome Res 2005, 15(2):330\u2013340. 10.1101\/gr.2821705","journal-title":"Genome Res"},{"issue":"8","key":"2018_CR33","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1093\/nar\/gki541","volume":"33","author":"P Gardner","year":"2005","unstructured":"Gardner P, Wilm A, Washietl S: A benchmark of multiple sequence alignment programs upon structural RNAs. Nucl Acids Res 2005, 33(8):2433\u20132439. 10.1093\/nar\/gki541","journal-title":"Nucl Acids Res"},{"key":"2018_CR34","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 S: Rfam: an RNA family database. Nucl Acids Res 2003, 31: 439\u2013441. 10.1093\/nar\/gkg006","journal-title":"Nucl Acids Res"},{"key":"2018_CR35","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1093\/nar\/gkg107","volume":"31","author":"MA Rosenblad","year":"2003","unstructured":"Rosenblad MA, Gorodkin J, Knudsen B, Zwieb C, Samuelsson T: SRPDB: Signal Recognition Particle Database. Nucleic Acids Res 2003, 31: 363\u2013364. 10.1093\/nar\/gkg107","journal-title":"Nucleic Acids Res"},{"key":"2018_CR36","first-page":"442","volume":"405","author":"B Matthews","year":"1975","unstructured":"Matthews B: Comparison of the predicted and observed secondary structure of T4 phage lysozyme. Biochem Biophys Acta 1975, 405: 442\u2013451.","journal-title":"Biochem Biophys Acta"},{"key":"2018_CR37","doi-asserted-by":"crossref","unstructured":"Gardner PP, Giegerich R: A comprehensive comparison of comparative RNA structure prediction approaches. BMC Bioinformatics 2004., 5(140):","DOI":"10.1186\/1471-2105-5-140"},{"key":"2018_CR38","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1093\/nar\/gkf436","volume":"30","author":"K Katoh","year":"2002","unstructured":"Katoh K, Misawa K, Kuma K, Miyata T: MAFFT:a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Res 2002, 30: 3059\u20133066. 10.1093\/nar\/gkf436","journal-title":"Nucleic Acids Res"},{"key":"2018_CR39","volume-title":"BMC Bioinformatics","author":"RD Dowell","year":"2007","unstructured":"Dowell RD, Eddy SR: Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign. BMC Bioinformatics 2007., 8:"},{"key":"2018_CR40","volume-title":"Bioinformatics Advance Access","author":"H Kiryu","year":"2007","unstructured":"Kiryu H, Kin T, Asai K: Rfold: An exact algorithm for computing local base pairing probabilities. Bioinformatics Advance Access 2007, in press. 10.1093\/bioinformatics\/btm591"},{"key":"2018_CR41","unstructured":"MXSCARNA[http:\/\/mxscarna.ncrna.org\/]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-33.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T03:15:12Z","timestamp":1630466112000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,23]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2018"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-33","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,23]]},"assertion":[{"value":"14 September 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"33"}}