M. Ishikawa[1] (ishikawa@icot.or.jp)
T. Toya[1] (toya@icot.or.jp)
Y. Totoki[1] (totoki@icot.or.jp)
R. Tanaka[2] (ma-tanak@icot.or.jp)
[1] Institute for New Generation Computer Technology (ICOT)
1-4-28-21F Mita, Minato-ku, Tokyo 108 JAPAN
[2] Information and Mathematical Science Laboratory, Inc.
2-43-1 Ikebukuro, Toshima-ku, Tokyo 171 JAPAN
We have developed a multiple sequence alignment system which aligns RNA sequences while estimating their stem regions. The system consists of two parts: initial and stem aligners. The initial aligner roughly aligns given RNA sequences using a parallel iterative algorithm based on dynamic programming. The stem aligner refines the rough alignment using a parallel simulated annealing algorithm taking into account connected base pairs in stem regions. In testing with tRNA sequences, the system could generate alignments which identified well-known stem sets of clover shape. We have also developed a stem specifier which monitors such stem regions using a circular representation.