title: DNA motif elucidation using belief propagation.
abstract: Protein-binding microarray (PBM) is a high-throughout platform that can measure the DNA-binding preference of a protein in a comprehensive and unbiased manner. A typical PBM experiment can measure binding signal intensities of a protein to all the possible DNA k-mers (k=8∼10); such comprehensive binding affinity data usually need to be reduced and represented as motif models before they can be further analyzed and applied. Since proteins can often bind to DNA in multiple modes, one of the major challenges is to decompose the comprehensive affinity data into multimodal motif representations. Here, we describe a new algorithm that uses Hidden Markov Models (HMMs) and can derive precise and multimodal motifs using belief propagations. We describe an HMM-based approach using belief propagations (kmerHMM), which accepts and preprocesses PBM probe raw data into median-binding intensities of individual k-mers. The k-mers are ranked and aligned for training an HMM as the underlying motif representation. Multiple motifs are then extracted from the HMM using belief propagations. Comparisons of kmerHMM with other leading methods on several data sets demonstrated its effectiveness and uniqueness. Especially, it achieved the best performance on more than half of the data sets. In addition, the multiple binding modes derived by kmerHMM are biologically meaningful and will be useful in interpreting other genome-wide data such as those generated from ChIP-seq. The executables and source codes are available at the authors' websites: e.g. http://www.cs.toronto.edu/∼wkc/kmerHMM.
authors.affiliation: Department of Computer Science, University of Toronto, Toronto, Ontario, Canada, Terrence Donnelly Centre for Cellular and Biomolecular Research, University of Toronto, Toronto, Ontario, Canada, Department of Integrative Biology and Physiology, University of California Los Angeles, Los Angeles, CA, USA, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal, Jeddah, KSA, Banting and Best Department of Medical Research, University of Toronto, Toronto, Ontario, Canada and Department of Molecular Genetics, University of Toronto, Toronto, Ontario, Canada.
authors.forename: Ka-Chun
authors.initials: KC
authors.lastname: Wong
authors.forename: Tak-Ming
authors.initials: TM
authors.lastname: Chan
authors.forename: Chengbin
authors.initials: C
authors.lastname: Peng
authors.forename: Yue
authors.initials: Y
authors.lastname: Li
authors.forename: Zhaolei
authors.initials: Z
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D000818:Animals; D001665:Binding Sites; D004247:DNA / Q000737:chemistry* / Q000378:metabolism; D004268:DNA-Binding Proteins / Q000378:metabolism*; D008390:Markov Chains; D051379:Mice; D059372:Nucleotide Motifs; D040081:Protein Array Analysis; D017422:Sequence Analysis, DNA / Q000379:methods*; D014157:Transcription Factors / Q000378:metabolism*
chemical_list: D004268:DNA-Binding Proteins; D014157:Transcription Factors; D004247:DNA