## 2 Binding site representation  
Assuming a list of DNA binding sites for some TF is available, one of the very first questions is how to best represent and characterize the information contained in these sites for further analysis. The goal is to find a representation that matches as closely as possible all the binding sites in the collection and is clearly distinguished from the background. From the point of view of string processing, a simple and widely-used concept is the consensus sequence in which the most frequent character at each position is chosen to represent in the binding motif at that position. However, some positions might consist of characters of equivalent frequencies and thus a more complex pattern, the IUPAC sequence [33, 34] was used to characterize the diversity of those binding sites (**Figure 1a**). Although this representation works well for highly conserved and short binding motifs, it is defined somewhat arbitrarily and removes much of the information in the original set of binding sites. In a case for yeast TF ABF1, for instance, two IUPAC sequences (RTCRYYNNNNNACG or RTCRYNNNNNACG) have been published and used as a relatively precise description of ABF1 binding sites [35]. However, these representations failed to recognize the binding site SCPK01 on PYK1 promoter from position -610 to -598 which was showed to be bound by TF ABF1 experimentally [36]. Consequently, a more precise representation was proposed to utilize almost all binding site information, known as the nucleotide distribution matrix or position weight matrix (PWM) [35, 37, 38], which has been proven very successful in various problems in DNA and protein sequence analysis [35, 39]. The PWM is a matrix of scores (e.g. occurrences, frequencies) with four rows corresponding to four DNA bases and m columns, each of which is a position in the binding motif. The basic assumption of the PWM is that the base-pairs at different positions are statistically independent and thus the fitness score of a matched oligonucleotide 'p' with this profile is the sum of the fitness at each position. This representation reflects the extent to which a position is conserved within the binding motifs and thus the higher the similarity, the higher the fitness is. The main weakness of the PWM approach stems from the assumption is that the positions contribute independently and additively to the total activity of the binding site. However, position dependence may exist on the binding sites and has been experimentally and/or statistically verified in some cases [40]. For example, using a new quantitative multiple fluorescence relative affinity assay [PERSON] et al. [41] showed that position 16 and 17 on the operator DNA were not independent in the interactions with its TF, _Salmonella_ bacteriophage repressor Mnt; or in another case, when [PERSON] et al. [42] applied \(\chi^{2}\) test on the 71 binding sites of TF _hepatocyte nuclear factor 4\(\alpha\)_ HNF4\(\alpha\), a significant dependence was found between several pairs of positions e.g. position 4 and 8, 4 and 11. Therefore, more comprehensive representations were introduced to capture the potential dependence between positions in binding sites, such as maximal dependence decomposition [43], hidden Markov model [44, 45], Markov chain optimization [42], as well as a more flexible approach based on variable-order Bayesian network which combines PWM, Markov models and Bayesian network model to fit with each particular subset of binding sites of a TF [46]. However, despite the limitations of the basic PWM approach, it is still the leading model in the search for discovering potential TFBSs. In fact, besides its intuitive representation and fast computation, it has been shown to be comparable at least, and in some case outperforms, other more complicated models e.g. fixed-order Markov models that are usually over-fitted due to a limited  
**Figure 1**. Binding site representation. **(a)** Illustration of several motif models for human factor ETS1.