smotif efficient structured pattern and profile motif search主题搜索smotif高效的结构化模式和概要文件.pdf

Algorithms for Molecular Biology BioMed Central Research Open Access SMOTIF: efficient structured pattern and profile motif search Yongqiang Zhang and Mohammed J Zaki* Address: Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180, USA Email: Yongqiang Zhang - zhangy0@; Mohammed J Zaki* - zaki@ * Corresponding author Published: 21 November 2006 Received: 21 May 2006 Accepted: 21 November 2006 Algorithms for Molecular Biology 2006, 1:22 doi:10.1186/1748-7188-1-22 This article is available from: /content/1/1/22 © 2006 Zhang and Zaki; licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract Background: A structured motif allows variable length gaps between several components, where each component is a simple motif, which allows either no gaps or only fixed length gaps. The motif can either be represented as a pattern or a profile (also called positional weight matrix). We propose an efficient algorithm, called SMOTIF, to solve the structured motif search problem, i.e., given one or more sequences and a structured motif, SMOTIF searches the sequences for all occurrences of the motif. Potential applications include searching for long terminal repeat (LTR) retrotransposons and composite regulatory binding sites in DNA sequences. Results: SMOTIF can search for both pattern and profile motifs, and i