An Improved Heuristic Algorithm for Finding Motif Signals in DNA Sequences

Author

Huang, Chao-Wen ; Lee, Wun-Shiun ; Hsieh, Sun-Yuan

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Cheng Kung Univ., Tainan, Taiwan

Volume

8

Issue

4

fYear

2011

Firstpage

959

Lastpage

975

Abstract

The planted (l, d)-motif search problem is a mathematical abstraction of the DNA functional site discovery task. In this paper, we propose a heuristic algorithm that can find planted (l, d)-signals in a given set of DNA sequences. Evaluations on simulated data sets demonstrate that the proposed algorithm outperforms current widely used motif finding algorithms. We also report the results of experiments on real biological data sets.

Keywords

DNA; bioinformatics; molecular biophysics; search problems; DNA functional site discovery task; DNA sequences; heuristic algorithm; motif finding algorithm; planted (l,d)-motif search problem; real biological data set; Approximation algorithms; Bioinformatics; Computational biology; DNA; Heuristic algorithms; Search problems; (l; Planted motif search problem; d)-signals.; heuristic algorithms; Algorithms; Animals; Base Sequence; Binding Sites; Cattle; Chickens; Computational Biology; Computer Simulation; Consensus Sequence; DNA; Humans; Mice; Molecular Sequence Data; Nucleic Acid Conformation; Pattern Recognition, Automated; Sequence Analysis, DNA; Swine; Tetraodontiformes;

fLanguage

English

Journal_Title

Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1545-5963

Type

jour

DOI

10.1109/TCBB.2010.92

Filename

5582077