{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:23:53Z","timestamp":1773278633589,"version":"3.50.1"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Structural RNA genes exhibit unique evolutionary patterns that are designed to conserve their secondary structures; these patterns should be taken into account while constructing accurate multiple alignments of RNA genes. The Sankoff algorithm is a natural alignment algorithm that includes the effect of base-pair covariation in the alignment model. However, the extremely high computational cost of the Sankoff algorithm precludes its application to most RNA sequences.<\/jats:p>\n               <jats:p>Results: We propose an efficient algorithm for the multiple alignment of structural RNA sequences. Our algorithm is a variant of the Sankoff algorithm, and it uses an efficient scoring system that reduces the time and space requirements considerably without compromising on the alignment quality. First, our algorithm computes the match probability matrix that measures the alignability of each position pair between sequences as well as the base pairing probability matrix for each sequence. These probabilities are then combined to score the alignment using the Sankoff algorithm. By itself, our algorithm does not predict the consensus secondary structure of the alignment but uses external programs for the prediction. We demonstrate that both the alignment quality and the accuracy of the consensus secondary structure prediction from our alignment are the highest among the other programs examined. We also demonstrate that our algorithm can align relatively long RNA sequences such as the eukaryotic-type signal recognition particle RNA that is \u223c300 nt in length; multiple alignment of such sequences has not been possible by using other Sankoff-based algorithms. The algorithm is implemented in the software named \u2018Murlet\u2019.<\/jats:p>\n               <jats:p>Availability: The C++ source code of the Murlet software and the test dataset used in this study are available at http:\/\/www.ncrna.org\/papers\/Murlet\/<\/jats:p>\n               <jats:p>Contact: kiryu-h@aist.go.jp<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm146","type":"journal-article","created":{"date-parts":[[2007,4,26]],"date-time":"2007-04-26T05:51:25Z","timestamp":1177566685000},"page":"1588-1598","source":"Crossref","is-referenced-by-count":64,"title":["Murlet: a practical multiple alignment tool for structural RNA sequences"],"prefix":"10.1093","volume":"23","author":[{"given":"Hisanori","family":"Kiryu","sequence":"first","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"},{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuo","family":"Tabei","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taishin","family":"Kin","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"},{"name":"1 Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, 2Graduate School of Information Sciences, Nara Institute of Science and Technology, 8916-5 Takayama-cho, Ikoma, Nara 630-0192 and 3Department of Computational Biology, Faculty of Frontier Science, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,4,25]]},"reference":[{"key":"2023062708444501300_B1","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","article-title":"The multiple sequence alignment problem in biology","volume":"48","author":"Carillo","year":"1988","journal-title":"SIAM J. Appl. Math"},{"key":"2023062708444501300_B2","doi-asserted-by":"crossref","first-page":"1559","DOI":"10.1126\/science.1112014","article-title":"The transcriptional landscape of the mammalian genome","volume":"309","author":"Carninci","year":"2005","journal-title":"Science"},{"key":"2023062708444501300_B3","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"ProbCons: probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res"},{"key":"2023062708444501300_B4","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","article-title":"CONTRAfold: RNA secondary structure prediction without physics-based models","volume":"22","author":"Do","year":"2006","journal-title":"Bioinformatics"},{"key":"2023062708444501300_B5","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1186\/1471-2105-7-400","article-title":"Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints","volume":"7","author":"Dowell","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023062708444501300_B6","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1038\/nature02379","article-title":"The DNA sequence and analysis of human chromosome 13","volume":"428","author":"Dunham","year":"2004","journal-title":"Nature"},{"key":"2023062708444501300_B7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023062708444501300_B8","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs (Evaluation Studies)","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023062708444501300_B9","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","article-title":"Finding the most significant common sequence and structure motifs in a set of RNA sequences","volume":"25","author":"Gorodkin","year":"1997","journal-title":"Nucleic Acids Res"},{"key":"2023062708444501300_B10","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/nar\/gkg006","article-title":"Rfam: an RNA family database","volume":"31","author":"Griffiths-Jones","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023062708444501300_B11","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btl431","article-title":"Mining frequent stem patterns from unaligned RNA sequences","author":"Hamada","year":"2006","journal-title":"Bioinformatics"},{"key":"2023062708444501300_B12","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":"2023062708444501300_B13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/TCBB.2004.11","article-title":"Pure multiple RNA secondary structure alignments: a progressive profile approach","volume":"1","author":"Hochsmann","year":"2004","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023062708444501300_B14","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":"2023062708444501300_B15","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":"2023062708444501300_B16","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":"2023062708444501300_B17","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":"2023062708444501300_B18","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","article-title":"Dynamic programming alignment accuracy","volume":"5","author":"Holmes","year":"1998","journal-title":"J. Comput. Biol"},{"key":"2023062708444501300_B19","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":"2023062708444501300_B20","doi-asserted-by":"crossref","first-page":"3019","DOI":"10.1093\/nar\/21.13.3019","article-title":"The signal recognition particle database (SRPDB)","volume":"21","author":"Larsen","year":"1993","journal-title":"Nucleic Acids Res"},{"key":"2023062708444501300_B21","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/0005-2795(75)90109-9","article-title":"Comparison of predicted and observed secondary structure of t4 phage lysozyme","volume":"405","author":"Matthews","year":"1975","journal-title":"Biochim. Biophys. Acta"},{"key":"2023062708444501300_B22","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":"2023062708444501300_B23","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol"},{"key":"2023062708444501300_B24","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023062708444501300_B25","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1093\/protein\/8.10.999","article-title":"A reliable sequence alignment method based on probabilities of residue correspondences","volume":"8","author":"Miyazawa","year":"1995","journal-title":"Protein Eng"},{"key":"2023062708444501300_B26","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1038\/nature01266","article-title":"Analysis of the mouse transcriptome based on functional annotation of 60,770 full-length cDNAs","volume":"420","author":"Okazaki","year":"2002","journal-title":"Nature"},{"key":"2023062708444501300_B27","doi-asserted-by":"crossref","first-page":"e33","DOI":"10.1371\/journal.pcbi.0020033","article-title":"Identification and classification of conserved RNA secondary structures in the human genome","volume":"2","author":"Pedersen","year":"2006","journal-title":"PLoS Comput. Biol"},{"key":"2023062708444501300_B28","doi-asserted-by":"crossref","first-page":"3516","DOI":"10.1093\/bioinformatics\/bti577","article-title":"Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction (Evaluation Studies)","volume":"21","author":"Reeder","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062708444501300_B29","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1471-2105-2-8","article-title":"Noncoding RNA gene detection using comparative sequence analysis","volume":"2","author":"Rivas","year":"2001","journal-title":"BMC Bioinformatics"},{"key":"2023062708444501300_B30","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":"2023062708444501300_B31","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1093\/bioinformatics\/btl177","article-title":"SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments","volume":"22","author":"Tabei","year":"2006","journal-title":"Bioinformatics"},{"key":"2023062708444501300_B32","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":"2023062708444501300_B33","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1186\/1471-2105-7-173","article-title":"Detection of non-coding RNAs on the basis of predicted secondary structure formation free energy change","volume":"7","author":"Uzilov","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023062708444501300_B34","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/0022-2836(87)90478-5","article-title":"A new algorithm for best subsequence alignments with application to tRNA-rRNA comparisons","volume":"197","author":"Waterman","year":"1987","journal-title":"J. Mol. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/1588\/50716849\/bioinformatics_23_13_1588.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/13\/1588\/50716849\/bioinformatics_23_13_1588.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T08:46:57Z","timestamp":1687855617000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/13\/1588\/221758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,25]]},"references-count":34,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2007,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm146","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,7]]},"published":{"date-parts":[[2007,4,25]]}}}