{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:16:24Z","timestamp":1773274584795,"version":"3.50.1"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Non-coding RNAs (ncRNAs) show a unique evolutionary process in which the substitutions of distant bases are correlated in order to conserve the secondary structure of the ncRNA molecule. Therefore, the multiple alignment method for the detection of ncRNAs should take into account both the primary sequence and the secondary structure. Recently, there has been intense focus on multiple alignment investigations for the detection of ncRNAs; however, most of the proposed methods are designed for global multiple alignments. For this reason, these methods are not appropriate to identify locally conserved ncRNAs among genomic sequences. A more efficient local multiple alignment method for the detection of ncRNAs is required.<\/jats:p><jats:p>Results: We propose a new local multiple alignment method for the detection of ncRNAs. This method uses a local multiple alignment construction procedure inspired by ProDA, which is a local multiple aligner program for protein sequences with repeated and shuffled elements. To align sequences based on secondary structure information, we propose a new alignment model which incorporates secondary structure features. We define the conditional probability of an alignment via a conditional random field and use a \u03b3-centroid estimator to align sequences. The locally aligned subsequences are clustered into blocks of approximately globally alignable subsequences between pairwise alignments. Finally, these blocks are multiply aligned via MXSCARNA. In benchmark experiments, we demonstrate the high ability of the implemented software, SCARNA_LM, for local multiple alignment for the detection of ncRNAs.<\/jats:p><jats:p>Availability: The C++ source code for SCARNA_LM and its experimental datasets are available at http:\/\/www.ncrna.org\/software\/scarna_lm\/download.<\/jats:p><jats:p>Contact: \u00a0scarna@m.aist.go.jp<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp261","type":"journal-article","created":{"date-parts":[[2009,4,18]],"date-time":"2009-04-18T00:34:24Z","timestamp":1240014864000},"page":"1498-1505","source":"Crossref","is-referenced-by-count":14,"title":["A local multiple alignment method for detection of non-coding RNA sequences"],"prefix":"10.1093","volume":"25","author":[{"given":"Yasuo","family":"Tabei","sequence":"first","affiliation":[{"name":"1 Department of Computational biology, Graduate School of Frontier Sciences, University of Tokyo, CB04 Kiban-tou 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan and 2Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, Japan"},{"name":"1 Department of Computational biology, Graduate School of Frontier Sciences, University of Tokyo, CB04 Kiban-tou 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan and 2Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"1 Department of Computational biology, Graduate School of Frontier Sciences, University of Tokyo, CB04 Kiban-tou 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan and 2Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, Japan"},{"name":"1 Department of Computational biology, Graduate School of Frontier Sciences, University of Tokyo, CB04 Kiban-tou 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan and 2Computational Biology Research Center (CBRC), National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo 135-0064, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"2023013111591241900_B1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1186\/1471-2105-8-271","article-title":"Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization","volume":"8","author":"Bauer","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023013111591241900_B2","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":"2023013111591241900_B3","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":"2023013111591241900_B4","doi-asserted-by":"crossref","first-page":"3209","DOI":"10.1073\/pnas.0712329105","article-title":"Centroid estimation in discrete high-dimensional spaces with applications in biology","volume":"105","author":"Carvalho","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013111591241900_B5","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1093\/bioinformatics\/btl142","article-title":"StrAl: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time","volume":"22","author":"Dalli","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B6","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":"2023013111591241900_B7","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":"2023013111591241900_B8","first-page":"160","article-title":"CONTRAlign: discriminative training for protein sequence alignment","author":"Do","year":"2006","journal-title":"RECOMB"},{"key":"2023013111591241900_B9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/bioinformatics\/btn177","article-title":"A max-margin model for efficient simultaneous alignment and folding of RNA sequences","volume":"24","author":"Do","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B10","volume-title":"Biological Sequence Analysis Probabilistic Models of Proteins and Nucleic Acids.","author":"Durbin","year":"1999"},{"key":"2023013111591241900_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":"2023013111591241900_B12","doi-asserted-by":"crossref","first-page":"D121","DOI":"10.1093\/nar\/gki081","article-title":"Rfam: annotating non-coding RNAs in complete genomes","volume":"33","author":"Griffiths-Jones","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013111591241900_B13","doi-asserted-by":"crossref","first-page":"R269","DOI":"10.1186\/gb-2007-8-12-r269","article-title":"CONTRAST: a discriminative, phylogeny-free approach to multiple informant de novo gene prediction","volume":"8","author":"Gross","year":"2007","journal-title":"Genome Biol."},{"key":"2023013111591241900_B14","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1093\/bioinformatics\/btn601","article-title":"Prediction of RNA secondary structure using generalized centroid estimators","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013111591241900_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":"2023013111591241900_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":"2023013111591241900_B17","doi-asserted-by":"crossref","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":"2023013111591241900_B18","first-page":"163","article-title":"Pairwise RNA structure comparison with stochastic context-free grammars","author":"Holmes","year":"2002","journal-title":"Pac. Symp. Biocomput."},{"key":"2023013111591241900_B19","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1186\/1471-2105-9-212","article-title":"Improved accuracy of multiple ncRNA alignment by incorporating structural information into a MAFFT-based framework","volume":"9","author":"Katoh","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013111591241900_B20","doi-asserted-by":"crossref","first-page":"D145","DOI":"10.1093\/nar\/gkl837","article-title":"fRNAdb: a platform for mining\/annotating functional RNA candidates from non-coding RNA sequences","volume":"35","author":"Kin","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023013111591241900_B21","doi-asserted-by":"crossref","first-page":"1588","DOI":"10.1093\/bioinformatics\/btm146","article-title":"Murlet: a practical multiple alignment tool for structural RNA sequences","volume":"23","author":"Kiryu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B22","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1093\/bioinformatics\/btm591","article-title":"Rfold: an exact algorithm for computing local base pairing probabilities","volume":"24","author":"Kiryu","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B23","first-page":"282","article-title":"Conditional random fields: probabilistic models for segmenting and labeling sequence data","author":"Lafferty","year":"2001","journal-title":"ICML"},{"key":"2023013111591241900_B24","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01589116","article-title":"On the limited memory BFGS method for large scale optimization","volume":"45","author":"Liu","year":"1989","journal-title":"Math. Program."},{"key":"2023013111591241900_B25","doi-asserted-by":"crossref","DOI":"10.1186\/1748-7188-1-6","article-title":"Multiple sequence alignment with user-defined anchor points","volume":"1","author":"Morgenstern","year":"2006","journal-title":"Algorithm Mol. Biol."},{"key":"2023013111591241900_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":"2023013111591241900_B27","doi-asserted-by":"crossref","first-page":"5932","DOI":"10.1093\/nar\/gkl511","article-title":"Multiple alignment of protein sequences with repeats and rearrangements","volume":"34","author":"Phuong","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023013111591241900_B28","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment, and proto-sequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"issue":"Suppl. 2","key":"2023013111591241900_B29","doi-asserted-by":"crossref","first-page":"i237","DOI":"10.1093\/bioinformatics\/bti1139","article-title":"RNA secondary structural alignment with conditional random fields","volume":"21","author":"Sato","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B30","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":"2023013111591241900_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":"2023013111591241900_B32","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1186\/1471-2105-9-33","article-title":"A fast structural multiple alignment method for long RNA sequences","volume":"9","author":"Tabei","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013111591241900_B33","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","article-title":"Multiple structural alignment and clustering of RNA sequences","volume":"23","author":"Torarinsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B34","doi-asserted-by":"crossref","first-page":"3289","DOI":"10.1093\/bioinformatics\/btm485","article-title":"Biclustering as a method for RNA local multiple sequence alignment","volume":"23","author":"Wang","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B35","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. USA"},{"key":"2023013111591241900_B36","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLoS Comput. Biol"},{"key":"2023013111591241900_B37","doi-asserted-by":"crossref","first-page":"e52","DOI":"10.1093\/nar\/gkn174","article-title":"R-Coffee: a method for multiple alignment of non-coding RNA","volume":"36","author":"Wilm","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013111591241900_B38","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1093\/bioinformatics\/btm272","article-title":"RNASmpler: a new sampling based algorithm for common RNA secondary structure prediction and structure alignment","volume":"23","author":"Xu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013111591241900_B39","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1093\/bioinformatics\/btk008","article-title":"CMfinder-a covariance model based RNA motif finding algorithm","volume":"22","author":"Yao","year":"2006","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/1498\/48994983\/bioinformatics_25_12_1498.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/1498\/48994983\/bioinformatics_25_12_1498.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:30:52Z","timestamp":1710268252000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/12\/1498\/193963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,17]]},"references-count":39,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2009,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp261","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,6,15]]},"published":{"date-parts":[[2009,4,17]]}}}