DNA motif representation with nucleotide dependency.
The problem of discovering novel motifs of binding sites is important to the understanding of gene regulatory networks. Motifs are generally represented by matrices (position weight matrix (PWM) or position specific scoring matrix (PSSM) or strings. However, these representations cannot model biological binding sites well because they fail to capture nucleotide interdependence. It has been pointed out by many researchers that the nucleotides of the DNA binding site cannot be treated independently, e.g. the binding sites of zinc finger in proteins. In this paper, a new representation called Scored Position Specific Pattern (SPSP), which is a generalization of the matrix and string representations, is introduced which takes into consideration the dependent occurrences of neighboring nucleotides. Even though the problem of discovering the optimal motif in SPSP representation is proved to be NP-hard, we introduce a heuristic algorithm called SPSP-Finder, which can effectively find optimal motifs in most simulated cases and some real cases for which existing popular motif finding software, such as Weeder, MEME and AlignACE, fail.
Chin
Francis
F
Department of Computer Science, The University of Hong Kong, Hong Kong. chin@cs.hku.hk
Leung
Henry C M
HC
D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D001665:Binding Sites / Q000235:genetics; D003198:Computer Simulation; D017124:Conserved Sequence / Q000235:genetics*; D004330:Drosophila / Q000235:genetics; D010363:Pattern Recognition, Automated / Q000379:methods*; D011401:Promoter Regions, Genetic; D012045:Regulatory Sequences, Nucleic Acid / Q000235:genetics*; D012441:Saccharomyces cerevisiae / Q000235:genetics; D017422:Sequence Analysis, DNA / Q000379:methods*