title: Murlet: a practical multiple alignment tool for structural RNA sequences.
abstract: BACKGROUND
  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.
  
  
  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 approximately 300 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 'Murlet'.
  
  
  BACKGROUND
  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/.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors: Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology, 2-42 Aomi, Koto-ku, Tokyo 135-0064, Japan. kiryu-h@aist.go.jp
authors: Hisanori
authors: H
authors: Kiryu
authors: Yasuo
authors: Y
authors: Tabei
authors: Taishin
authors: T
authors: Kin
authors: Kiyoshi
authors: K
authors: Asai
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D008969:Molecular Sequence Data; D012313:RNA / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
chemical_list: D012313:RNA