Portal de Periódicos da CAPES

RISOTTO: Fast Extraction of Motifs with Mismatches

2006; Springer Science+Business Media; Linguagem: Inglês

10.1007/11682462_69

1611-3349

Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan, Marie-France Sagot,

Genomics and Phylogenetic Studies

We present in this paper an exact algorithm for motif extraction. Efficiency is achieved by means of an improvement in the algorithm and data structures that applies to the whole class of motif inference algorithms based on suffix trees. An average case complexity analysis shows a gain over the best known exact algorithm for motif extraction. A full implementation was developed and made available online. Experimental results show that the proposed algorithm is more than two times faster than the best known exact algorithm for motif extraction.