M. Ishikawa (email@example.com)
T. Toya (firstname.lastname@example.org)
Y. Totoki (email@example.com)
R. Tanaka (firstname.lastname@example.org)
 Institute for New Generation Computer Technology (ICOT)
1-4-28-21F Mita, Minato-ku, Tokyo 108 JAPAN
 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.