A profile-based deterministic sequential Monte Carlo algorithm for motif discovery.
BACKGROUND
Conserved motifs often represent biological significance, providing insight on biological aspects such as gene transcription regulation, biomolecular secondary structure, presence of non-coding RNAs and evolution history. With the increasing number of sequenced genomic data, faster and more accurate tools are needed to automate the process of motif discovery.


RESULTS
We propose a deterministic sequential Monte Carlo (DSMC) motif discovery technique based on the position weight matrix (PWM) model to locate conserved motifs in a given set of nucleotide sequences, and extend our model to search for instances of the motif with insertions/deletions. We show that the proposed method can be used to align the motif where there are insertions and deletions found in different instances of the motif, which cannot be satisfactorily done using other multiple alignment and motif discovery algorithms.


BACKGROUND
MATLAB code is available at http://www.ee.columbia.edu/~kcliang
Liang
Kuo-Ching
KC
Columbia University, Department of Electrical Engineering, New York, NY 10025, USA.
Wang
Xiaodong
X
Anastassiou
Dimitris
D
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D004247:DNA / Q000235:genetics*; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009010:Monte Carlo Method; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D004247:DNA