SMOTER, A Structured Motif Finder Based on an Exhaustive Tree-Based Algorithm

Author(s): Siavash Sheikhizadeh, Samin Hosseini

Journal Name: Current Bioinformatics

Volume 9 , Issue 1 , 2014

Become EABM
Become Reviewer


In this paper, an exhaustive algorithm for extracting structured motifs has been presented. Structured motif is defined as an ordered set of highly-conserved over-presented patterns which occur near each other in a set of DNA sequences .The presented algorithm is based on an innovative data structure called l-mer trie. As opposed to other existing motif finders, this algorithm offers more flexibility in terms of the possibility of determining a range for length of the single patterns, their substitution rates and the spacing between them. The possibility of defining a minimum bound for substitution rates saves considerable time and space in the case of searching for weak motifs occurring with many mutations.

Efficiency of the algorithm has been verified on some artificial sequences as well as real DNA sequences of some plant viruses. The results have been compared with those achieved by RISO, another tree-based algorithm, which is claimed to have notable time and space gains over the best known exact algorithms.

Keywords: Exhaustive algorithm, e-mutated set, geminivirideae, l-mer trie, structured motif, tymovirius.

Rights & PermissionsPrintExport Cite as

Article Details

Year: 2014
Page: [34 - 43]
Pages: 10
DOI: 10.2174/1574893608999140109122231

Article Metrics

PDF: 21