RAGA-RNA SEQUENCE ALIGNMENT BY GENETIC ALGORITHM

We describe a new approach for accurately aligning two homologous RNA sequences when the secondary structure of one of them is known, To do so we developed two software packages, called RAGA and PRAGA, which us e a genetic algorithm approach to optimize the alignments. RAGA is mai nly an extension of SAGA, an earlier package for multiple protein sequ ence alignment, In PRAGA several genetic algorithms run in parallel an d exchange individual solutions, This method allows us to optimize an objective function that describes the quality of a RNA pairwise alignm ent, taking into account both primary and secondary structure, includi ng pseudoknots. We report results obtained using PRAGA on nine test ca ses of pairs of eukaryotic small subunit rRNA sequence (nuclear and mi tochondrial).