{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T07:30:21Z","timestamp":1769239821611,"version":"3.49.0"},"reference-count":50,"publisher":"Oxford University Press (OUP)","issue":"24","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The importance of accurate and fast predictions of multiple alignments for RNA sequences has increased due to recent findings about functional non-coding RNAs. Recent studies suggest that maximizing the expected accuracy of predictions will be useful for many problems in bioinformatics.<\/jats:p>\n               <jats:p>Results: We designed a novel estimator for multiple alignments of structured RNAs, based on maximizing the expected accuracy of predictions. First, we define the maximum expected accuracy (MEA) estimator for pairwise alignment of RNA sequences. This maximizes the expected sum-of-pairs score (SPS) of a predicted alignment under a probability distribution of alignments given by marginalizing the Sankoff model. Then, by approximating the MEA estimator, we obtain an estimator whose time complexity is O(L3+c2dL2) where L is the length of input sequences and both c and d are constants independent of L. The proposed estimator can handle uncertainty of secondary structures and alignments that are obstacles in Bioinformatics because it considers all the secondary structures and all the pairwise alignments as input sequences. Moreover, we integrate the probabilistic consistency transformation (PCT) on alignments into the proposed estimator. Computational experiments using six benchmark datasets indicate that the proposed method achieved a favorable SPS and was the fastest of many state-of-the-art tools for multiple alignments of structured RNAs.<\/jats:p>\n               <jats:p>Availability: The software called CentroidAlign, which is an implementation of the algorithm in this article, is freely available on our website: http:\/\/www.ncrna.org\/software\/centroidalign\/.<\/jats:p>\n               <jats:p>Contact: \u00a0hamada-michiaki@aist.go.jp<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp580","type":"journal-article","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T03:44:47Z","timestamp":1254887087000},"page":"3236-3243","source":"Crossref","is-referenced-by-count":45,"title":["CentroidAlign: fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score"],"prefix":"10.1093","volume":"25","author":[{"given":"Michiaki","family":"Hamada","sequence":"first","affiliation":[{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"},{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"}]},{"given":"Kengo","family":"Sato","sequence":"additional","affiliation":[{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"},{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"}]},{"given":"Hisanori","family":"Kiryu","sequence":"additional","affiliation":[{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"}]},{"given":"Toutai","family":"Mituyama","sequence":"additional","affiliation":[{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"}]},{"given":"Kiyoshi","family":"Asai","sequence":"additional","affiliation":[{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"},{"name":"1 Mizuho Information & Research Institute, Inc, 2\u20133 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101\u20138443, 2Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2\u201341\u20136, Aomi, Koto-ku, Tokyo 135\u20130064, 3Japan Biological Informatics Consortium, 2\u201345 Aomi, Koto-ku, Tokyo 135\u20138073 and 4Graduate School of Frontier Sciences, University of Tokyo, 5\u20131\u20135 Kashiwanoha, Kashiwa 277\u20138562, Japan"}]}],"member":"286","published-online":{"date-parts":[[2009,10,6]]},"reference":[{"key":"2023013112150189300_B1","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1186\/1471-2105-7-244","article-title":"Identification of consensus RNA secondary structures using suffix arrays","volume":"7","author":"Anwar","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023013112150189300_B2","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":"2023013112150189300_B3","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1186\/1471-2105-9-474","article-title":"RNAalifold: improved consensus structure prediction for RNA alignments","volume":"9","author":"Bernhart","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023013112150189300_B4","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1093\/bioinformatics\/btk014","article-title":"Local RNA base pairing probabilities in large sequences","volume":"22","author":"Bernhart","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B5","doi-asserted-by":"crossref","first-page":"2677","DOI":"10.1093\/bioinformatics\/btn495","article-title":"Specific alignment of structured RNA: stochastic grammars and sequence annealing","volume":"24","author":"Bradley","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B6","doi-asserted-by":"crossref","first-page":"e1000392","DOI":"10.1371\/journal.pcbi.1000392","article-title":"Fast statistical alignment","volume":"5","author":"Bradley","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"2023013112150189300_B7","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":"2023013112150189300_B8","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":"2023013112150189300_B9","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1261\/rna.2500605","article-title":"RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble","volume":"11","author":"Ding","year":"2005","journal-title":"RNA"},{"key":"2023013112150189300_B10","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1016\/j.jmb.2006.01.056","article-title":"Clustering of RNA secondary structures with application to messenger RNAs","volume":"359","author":"Ding","year":"2006","journal-title":"J. Mol. Biol."},{"key":"2023013112150189300_B11","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":"2023013112150189300_B12","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":"2023013112150189300_B13","first-page":"160","article-title":"Contralign: discriminative training for protein sequence alignment","volume-title":"RECOMB","author":"Do","year":"2006"},{"key":"2023013112150189300_B14","doi-asserted-by":"crossref","first-page":"i68","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":"2023013112150189300_B15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1186\/1471-2105-5-71","article-title":"Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction","volume":"5","author":"Dowell","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023013112150189300_B16","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":"2023013112150189300_B17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"Durbin","year":"1998"},{"key":"2023013112150189300_B18","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":"2023013112150189300_B19","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":"2023013112150189300_B20","doi-asserted-by":"crossref","first-page":"i330","DOI":"10.1093\/bioinformatics\/btp228","article-title":"Predictions of RNA secondary structure by combining homologous sequence information","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B21","doi-asserted-by":"crossref","first-page":"2406","DOI":"10.1093\/nar\/gkn043","article-title":"PARTS: probabilistic alignment for RNA joinT secondary structure prediction","volume":"36","author":"Harmanci","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013112150189300_B22","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":"2023013112150189300_B23","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":"2023013112150189300_B24","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":"2023013112150189300_B25","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":"2023013112150189300_B26","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":"2023013112150189300_B27","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1093\/bioinformatics\/btl636","article-title":"Robust prediction of consensus secondary structures using averaged base pairing probability matrices","volume":"23","author":"Kiryu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B28","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":"2023013112150189300_B29","doi-asserted-by":"crossref","first-page":"3304","DOI":"10.1093\/bioinformatics\/btm525","article-title":"MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing","volume":"23","author":"Lindgreen","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B30","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1101\/gr.6725608","article-title":"Uncertainty in homology inferences: assessing and improving genomic sequence alignment","volume":"18","author":"Lunter","year":"2008","journal-title":"Genome Res."},{"key":"2023013112150189300_B31","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":"2023013112150189300_B32","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":"2023013112150189300_B33","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":"2023013112150189300_B34","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":"2023013112150189300_B35","doi-asserted-by":"crossref","first-page":"W10","DOI":"10.1093\/nar\/gkn278","article-title":"R-Coffee: a web server for accurately aligning noncoding RNA sequences","volume":"36","author":"Moretti","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013112150189300_B36","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023013112150189300_B37","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":"2023013112150189300_B38","doi-asserted-by":"crossref","first-page":"2715","DOI":"10.1093\/bioinformatics\/btl472","article-title":"Probalign: multiple sequence alignment using partition function posterior probabilities","volume":"22","author":"Roshan","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112150189300_B39","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding alignment and protosequence problems","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math"},{"key":"2023013112150189300_B40","doi-asserted-by":"crossref","first-page":"W277","DOI":"10.1093\/nar\/gkp367","article-title":"CENTROIDFOLD: a web server for RNA secondary structure prediction","volume":"37","author":"Sato","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023013112150189300_B41","author":"Schwartz","year":"2005","journal-title":"Alignment metric accuracy."},{"key":"2023013112150189300_B42","doi-asserted-by":"crossref","first-page":"6355","DOI":"10.1093\/nar\/gkn544","article-title":"Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments","volume":"36","author":"Seemann","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013112150189300_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":"2023013112150189300_B44","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":"2023013112150189300_B45","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":"2023013112150189300_B46","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":"2023013112150189300_B47","doi-asserted-by":"crossref","first-page":"e1000077","DOI":"10.1371\/journal.pcbi.1000077","article-title":"Measuring global credibility with application to local sequence alignment","volume":"4","author":"Webb-Robertson","year":"2008","journal-title":"PLoS Comput. Biol."},{"key":"2023013112150189300_B48","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1748-7188-1-19","article-title":"An enhanced RNA alignment benchmark for sequence alignment programs","volume":"1","author":"Wilm","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023013112150189300_B49","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":"2023013112150189300_B50","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1126\/science.1151532","article-title":"Alignment uncertainty and genomic analysis","volume":"319","author":"Wong","year":"2008","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/24\/3236\/48997901\/bioinformatics_25_24_3236.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/24\/3236\/48997901\/bioinformatics_25_24_3236.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:50:31Z","timestamp":1675201831000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/24\/3236\/235199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,6]]},"references-count":50,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2009,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp580","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,12,15]]},"published":{"date-parts":[[2009,10,6]]}}}