title: CentroidAlign: fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score.
abstract: BACKGROUND
  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.
  
  
  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(L(3)+c(2)dL(2)) 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.
  
  
  BACKGROUND
  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/.
  
  
  BACKGROUND
  hamada-michiaki@aist.go.jp
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Mizuho Information & Research Institute, Inc, 2-3 Kanda-Nishikicho, Chiyoda-ku, Tokyo 101-8443, Japan. hamada-michiaki@aist.go.jp
authors.forename: Michiaki
authors.initials: M
authors.lastname: Hamada
authors.forename: Kengo
authors.initials: K
authors.lastname: Sato
authors.forename: Hisanori
authors.initials: H
authors.lastname: Kiryu
authors.forename: Toutai
authors.initials: T
authors.lastname: Mituyama
authors.forename: Kiyoshi
authors.initials: K
authors.lastname: Asai
mesh_terms: D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D012313:RNA / Q000737:chemistry* / Q000378:metabolism; D022661:RNA, Untranslated / Q000737:chemistry / Q000378:metabolism; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
chemical_list: D022661:RNA, Untranslated; D012313:RNA