Research interests | Publications | Software | Teaching | Short CV
RISOTTO: Fast extraction of motifs with mismatches
Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan and Marie-France Sagot
Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN'06)
Volume 3887 of Lecture Notes in Computer Science (LNCS), pages 757-768
Chile, Valdivia, 2006
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, when applied to extract long motifs. 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, confirming in this way the theoretical results obtained.
Keywords: Bioinformatics, Motif extraction algorithm, Complexity, Maximal extensibility.
Availability: http://kdbio.inesc-id.pt/~asmc/software/riso.html
Get a preprint:
[ps]
[pdf]
Get a bibentry:
[bib]
[bbl]
Research interests | Publications | Software | System administration | Short CV | Personal