RISOTTO: Fast extraction of motifs with mismatches
RISOTTO: Fast extraction of motifs with mismatches
复制标题
DOI：
10.1007/11682462_69
复制
发表时间：
2006-01-01
期刊：
影响因子：
--
通讯作者：
Sagot, MR
中科院分区：
文献类型：
--
作者：
Pisanti, N;Carvalho, AM;Sagot, MR
本文提出了一种精确的模体提取算法。通过改进算法和数据结构来实现效率，该算法和数据结构适用于基于后缀树的整个类别的Motif推理算法。平均案例复杂性分析表明，与最著名的精确主题提取算法相比，该算法具有更大的优势。开发了一个完整的实施方案，并在网上提供。实验结果表明，该算法提取基元的速度比已知的精确算法快两倍以上。
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.