Biochemistry Publications


Bipartite Pattern Discovery by Entropy Minimization-based Multiple Local Alignment

Document Type


Publication Date



Nucleic Acids Research





First Page


Last Page



Many multimeric transcription factors recognize DNA sequence patterns by cooperatively binding to bipartite elements composed of half sites separated by a flexible spacer. We developed a novel bipartite algorithm, bipartite pattern discovery (Bipad), which produces a mathematical model based on information maximization or Shannon's entropy minimization principle, for discovery of bipartite sequence patterns. Bipad is a C++ program that applies greedy methods to search the bipartite alignment space and examines the upstream or downstream regions of co-regulated genes, looking for cis-regulatory bipartite patterns. An input sequence file with zero or one site per locus is required, and the left and right motif widths and a range of possible gap lengths must be specified. Bipad can run in either single-block or bipartite pattern search modes, and it is capable of comprehensively searching all four orientations of half-site patterns. Simulation studies showed that the accuracy of this motif discovery algorithm depends on sample size and motif conservation level, but results were independent of background composition. Bipad performed equivalent with or better than other pattern search algorithms in correctly identifying Escherichia coli cyclic AMP receptor protein and Bacillus subtilis sigma factor binding site sequences based on experimentally defined benchmarks. Finally, a new bipartite information weight matrix for vitamin D3 receptor/retinoid X receptor {alpha} (VDR/RXR{alpha}) binding sites was derived that comprehensively models the natural variability inherent in these sequence elements.


Published in: Nucleic Acids Research 2004 32(17):4979-4991; doi:10.1093/nar/gkh825. Dr. Peter K. Rogan is currently a faculty member at the University of Western Ontario. Bipad can be accessed through a webserver at

Find in your library