An Efficient Exact Algorithm for the Motif Stem Search Problem over Large Alphabets

In recent years, there has been an increasing interest in planted (l, d) motif search (PMS) with applications to discovering significant segments in biological sequences. However, there has been little discussion about PMS over large alphabets. This paper focuses on motif stem search (MSS), which is...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on computational biology and bioinformatics 2015-03, Vol.12 (2), p.384-397
Main Authors: Qiang Yu, Hongwei Huo, Vitter, Jeffrey Scott, Jun Huan, Nekrich, Yakov
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Alphabets
Amino Acid Motifs
Bioinformatics
Biology
Computational biology
Computational Biology - methods
Computer Simulation
Construction
Hamming distance
Motif stem search
pattern driven
Pattern Recognition, Automated - methods
Proteins - chemistry
Radiation detectors
regular expressions
Searching
Segments
Sequence Analysis, Protein - methods
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years, there has been an increasing interest in planted (l, d) motif search (PMS) with applications to discovering significant segments in biological sequences. However, there has been little discussion about PMS over large alphabets. This paper focuses on motif stem search (MSS), which is recently introduced to search motifs on large-alphabet inputs. A motif stem is an l-length string with some wildcards. The goal of the MSS problem is to find a set of stems that represents a superset of all (l , d) motifs present in the input sequences, and the superset is expected to be as small as possible. The three main contributions of this paper are as follows: (1) We build motif stem representation more precisely by using regular expressions. (2) We give a method for generating all possible motif stems without redundant wildcards. (3) We propose an efficient exact algorithm, called StemFinder, for solving the MSS problem. Compared with the previous MSS algorithms, StemFinder runs much faster and reports fewer stems which represent a smaller superset of all (l, d) motifs. StemFinder is freely available at http://sites.google.com/site/feqond/stemfinder.
ISSN:1545-5963
1557-9964
DOI:10.1109/TCBB.2014.2361668