I will present a novel approach for discovering consensus secondary structure motifs in a set of unaligned RNA sequences. The secondary structure motifs combine sequence and structure information. State-of-the-art data structures, including suffix arrays, are used to enumerate exhaustively the space of possible motifs. Suffix arrays (SAs) are used for two purposes. First, SAs ares used to efficiently enumerate stem structures, including internal loops. Second, SAs are used to solve the secondary expression matching problem. The algorithms has been implemented in a software system called Seed.

Applications of the method on test cases shows that i) complex search spaces can be exhaustively explored and that ii) the search spaces contains biologically relevant candidates.