BACKGROUND
gene expression is controlled by the interaction of transcription factors  and their dna binding sites.
promoters often contain multiple binding sites for different tfs that work in tandem to control the regulation  of gene expression.
tfs bind to short  degenerate dna sequence patterns or motifs, which makes them relatively difficult to find.
understanding the regulation of gene expression in higher eukaryotes is still a major challenge and the current algorithms are not always able to clearly distinguish real transcription factor binding sites  from random look-alike sequences  <cit> .
position-weight matrices  are widely used to represent tfbs in promoter regions of genes  <cit> .
unfortunately, many of these pwms have low information content and match a huge number of sequences in the genome.
however, most of these matches are likely to be false positives  <cit> .
pwms are commonly used due to lack of better alternatives  <cit> .
pwms are calculated from position frequency matrices  that contain the observed nucleotide frequencies at each position in the profile alignment of binding sites for a tf of interest.
most of the known matrix models for tfbs can be obtained from the jaspar  <cit>  and transfac  <cit>  databases, together with the set of binding sites used to build them.
tfbs based on dnase i footprinting experiments can be found in the dnase i database for drosophila melanogaster  <cit> .
furthermore, the matrices are often derived from a limited number of experimentally verified sequences, which leads to inaccurate representations of tf-dna binding affinities.
today, wet-lab technologies such as chromatin immunoprecipitation   <cit>  are commonly used to identify in vivo tf binding locations.
chip-chip and chip-pet analyses provide large amounts of data and will therefore pave the way for the construction of more precise pwms.
in particular, these experiments provide an opportunity to computationally improve the accuracy of existing position-specific matrices.
it is this important problem that we address in the present study.
RESULTS
we have created dispare, a two-step algorithm that takes a known matrix as its input, performs an iterative and discriminative refinement using experimentally verified tfbs and background sequences.
after the discriminative optimization step, dispare returns an optimized matrix with improved information referred to as a dispare matrix.
using the width and phase optimization step, a width-optimized matrix is obtained with improved information and optimized width and phase .
in order to evaluate the performance of our algorithm, we applied it to several synthetic datasets.
we then tested dispare using mammalian transcription factor binding sites from experimental chip-pet data: human p <dig> motif from  <cit> , mouse nanog  <cit>  and human estrogen receptor α binding sites  <cit> .
synthetic data
we first applied dispare to synthetic data to evaluate its performance under known conditions.
a motif was artificially implanted in each of the randomly generated sequences at a random position.
the implanted pattern is described by a weight matrix wma of width  <dig>  and characterized by the consensus 'acgtca'.
we arbitrarily used the ma <dig> jaspar matrix as the initial matrix.
we generated a set of  <dig> random,  <dig> nucleotide-long sequences as a positive set using decodeanhmm  <cit> , a hmm-based random sequence generator.
the order of the markov model was chosen to be equal to  <dig> so that all nucleotides in the generated sequences were independent of each other.
these sequences were gc-rich, containing 30% g, 30% c, 20% a and 20% t. the generated sequence set was divided into a training set and a test set of equal sizes, i.e of  <dig> sequences each.
we copied and shuffled the  <dig> randomly generated sequences to obtain two corresponding background sets of  <dig> sequences each.
we ran dispare on the positive and background sequences, using the matrix wma as input .
the algorithm first performs an iterative matrix optimization by calculating cut-offs that discriminate best between the two datasets.
after running the dispare discriminative optimization step for  <dig> iterations, we obtained a dispare matrix .
after the first optimization step, the algorithm performs width and phase optimization on the dispare matrix in order to investigate whether a better width can be found for the input matrix.
this step can improve the accuracy of pwms because initial matrices often have sub-optimal length and phase.
the phase can be defined as position of the window, relatively to the actual pattern on the dna.
in this example, since the pwm was already in its optimal form, the length and phase remained unchanged.
the width-optimized matrix thus obtained was  <dig> nucleotides long .
we compared the performances of the initial matrix, dispare matrix and width-optimized matrix to four pwms obtained with four de novo motif discovery programs: bayesmd, meme, prego and weeder .
the roc curves of this assessment are illustrated in figure 1d.
we ran meme using the consensus 'acgtca' as prior information so that we could compare our program with another supervised approach.
dispare improved the initial matrix by increasing the auc from  <dig>  to  <dig>  and outperformed bayesmd .
however, meme achieved the same result as the dispare matrix under supervision with the consensus 'acgtca' as prior information .
k-mer based methods gave different results: prego was able to find the motif wma, achieving an auc of  <dig> , while weeder failed to recover the motif wma which is why an roc curve for this tool is omitted in figure 1d.
the width-optimized matrix  improved the performance of the dispare matrix due to the additional information enhancement step provided by the width optimization algorithm after the choice of the optimal frame .
test of robustness using two synthetic matrices
an important challenge in motif finding is to design methods that can accommodate datasets of various sizes and background compositions.
in order to evaluate the robustness of dispare in this context, we constructed five new datasets  using the initial synthetic matrix wma.
we increased the number of sequences to  <dig>  from  <dig>  while keeping the length of sequences constant at  <dig> nucleotides and the same composition of nucleotides  in set  <dig>  the difference between set  <dig> and set  <dig> is the increase in the length of the sequences to  <dig> nucleotides.
set  <dig> has the same size as the dataset used in figure  <dig>  but has a different background composition .
for sets  <dig> and  <dig>  we generated datasets with  <dig> sequences of  <dig> nucleotides with two different background compositions.
as described above, we divided each set of newly generated sequences into a test set and a training set of equal sizes i.e of  <dig> sequences each.
we ran dispare and the four selected motif discovery programs on these five datasets and obtained roc curves illustrated in additional file 2: figure s <dig>  as before, meme was run using a supervised mode with the consensus 'acgtca' as prior information.
running dispare on test set  <dig>  which contained a higher number of sequences , improved the initial matrix once again  by increasing the auc of both dispare matrix and width-optimized matrix to  <dig>  and performed better than prego .
meme  achieved a similar result by accurately capturing the motif wma.
we did not find any suitable motifs for this set using bayesmd and weeder despite several runs.
encouraged by this result, we increased the sequence length in set  <dig>  to check the impact of varying sequence lengths on the algorithm.
in this test, the dispare matrix  and the width-optimized matrix  improved the initial matrix .
they performed better than prego matrix .
however, meme with supervision achieved a better result .
again, bayesmd and weeder failed to recover the  <dig> nucleotide-long motif.
in the third test, , we investigated the effects of a change in the background composition on the results.
again, our algorithm recovered the motif wma in this test , showing that changing the background, in which the sites were implanted, had no impact on the accuracy of dispare.
finally, we compared the behaviour of each program using random sequences of length  <dig>  sets  <dig> and  <dig>  were designed to produce a strong pattern-drowning effect for motif wma, as such a short and 'random' pattern  was likely to occur in several locations by chance.
in test  <dig>  using a gc-rich background, we showed that dispare , meme and bayesmd  successfully recovered the motif wma, while prego  and weeder failed to capture the correct consensus.
finally, in test  <dig>  using a uniform background , we found that only dispare, meme and prego were able to capture the motif with a low sensitivity .
this low value can be interpreted as the 'baseline' prediction rate for the wma matrix for this dataset .
these last two tests showed that our discriminative approach is robust against noise, accurately returning a refined matrix from large datasets.
in these five tests, we showed that dispare consistently improved the initial matrix and achieved one of the two best roc performances each time.
the width optimization step did not yield further improvements since the initial matrix  was already in its most compact form.
interestingly, we found that for sets larger than  <dig> sequences, bayesmd and weeder failed the test, despite several runs to find a matrix.
this can be explained by the 'randomness' of the matrix wma consensus or by the statistical background models used in these two approaches which do not recapitulate the background sequences accurately.
prego, which uses the actual background sequences as input, was able to recover the planted motif.
similarly, meme uses a 0th order background in its default settings which seemed to work better in this assessment than bayesmd and weeder which use higher order backgrounds by default.
after evaluating dispare using five different datasets for the matrix wma, we re-tested it against a new synthetic matrix.
we used the matrix wm to generate five new positive and background datasets  and changed parameters such as the number of sequences, the background composition and the length of the sequences.
the synthetic wm motif is  <dig> nucleotides long and contains the central pattern 'acgtgc'.
as described above, we divided each set into a training set and a test set, on which the assessments were performed.
we generated a corresponding set of background sequences by shuffling each set of positive sequences.
the roc curves of these five tests are shown in additional file 3: figure s <dig>  we ran the de novo motif finding program meme using the consensus 'tacgtgcg' as prior information so that we could compare dispare with another program running in supervised mode.
in test a, we ran dispare on a set of  <dig> sequences, each being  <dig> nucleotides long, with a gc-rich background.
the initial matrix, the dispare matrix and the width-optimized matrix obtained similar results  and did better than the four motif discovery methods .
in test b, we increased the sequence length to  <dig> nucleotides and compared it with the set a. again, the initial matrix, the dispare matrix and the width-optimized matrix obtained the best auc .
more interestingly, we found that three tested motif discovery tools could not find the matrix wm accurately .
meme, however, which used a 0th order background and prior information was able to find the motif wm in this configuration .
this test demonstrates that dispare is robust against pattern drowning and performs accurately with increasing sequence length and the number of sequences.
we then wondered whether background sequence composition could affect the performance of our matrix refinement algorithm.
in test c, we constructed a dataset of  <dig> sequences spanning  <dig> nucleotides and containing equal proportion  of each nucleotide.
the dispare matrix , the width-optimized matrix  and the initial matrix  obtained similar results and performed better than other approaches .
this test showed that background composition had no impact on the accuracy of dispare.
finally, in tests d and e  we evaluated dispare and the four selected programs under the extreme situation of looking for the motif wm in  <dig> kb long input sequences.
the sequence sets contain  <dig> sequences but the background composition is gc-rich  and uniform .
in test d, the roc curves show a global decrease of accuracy compared to the test with shorter sequences.
however, the dispare matrix  and the width-optimized matrix  recovered the initial model .
dispare performed better than other programs in test d , meme  and bayesmd.
we repeated the test with a different background .
the initial matrix, dispare matrix and width-optimized matrix obtained consistently similar outcomes .
we observed that other methods performed better than in test d .
increasing the number of sequences  or using longer sequences  had no impact on the performance of dispare, unlike motif discovery methods which can sometimes suffer from pattern drowning, i.e.
lose the ability to capture the motif signal when the latter is embedded in large amounts of random sequences.
furthermore, we also obtained similar results while running dispare on background sequences with a different composition .
the performance gain in these tests was expected to be small since the input matrix was the same as the one that we used to build the five datasets.
the purpose of this assessment was to evaluate the robustness of dispare under various operating conditions.
the tests on synthetic data showed that dispare was able to improve the width and information of an initial matrix using sequences containing sites described by the same matrix.
in the next test, to assess the performance of dispare under more realistic conditions, we distorted the initial synthetic matrix wm and ran the assessment again on the same datasets.
data distortion
we tested the ability of dispare to improve a matrix with distorted information using high quality transcription factor binding sites provided by a positive set.
using the initial synthetic data matrix wm  we generated two distorted matrices,  and  , with the same width as the initial matrix wm.
this initial synthetic matrix is  <dig> nucleotides long and consists of the core motif 'acgtgc' in the center.
uniformly distributed  noise was added to the matrix m to create the elements of m'.
the elements of the noise matrix u are uniformly distributed random numbers between  <dig> and  <dig>  a constant k was used to set the amplitude of noise.
we used a constant  to obtain the first matrix  and used a larger constant  to obtain a second matrix  with more distortion.
m' can therefore be expressed as m' = m+ku.
the distorted matrices are normalized in a column-wise manner before being returned in order to obtain correct position frequency matrices.
we calculated the degree of data distortion from  to m and from  to m. first, we measured the signal attenuation after distorting the matrices with noise.
the signal attenuation or loss of information content  is defined here by the log-ratio of the information content of the original to the distorted matrix, expressed in decibels :
for matrix , the information content was attenuated by  <dig>  db  and for matrix , the attenuation was equal to  <dig>  db , implying that  signal strength is twice as less as .
we then evaluated the data distortion by calculating the difference of frobenius norm.
the frobenius norm is defined as
it is often used in linear algebra to measure the distortion of a matrix as it is proportional to the mean squares of the errors .
the relative value difference  of the frobenius norm represents the relative error between the elements of the original and distorted matrices:
where v d is the difference of the frobenius norm from m' to m divided by the frobenius norm of m. v d values for  and  were respectively v d <dig> =  <dig>  and v d <dig> =  <dig> .
is lightly attenuated and distorted, and therefore mimics the case when the count matrix was built with good quality sites .
mimics the case when sites come from either computational prediction or from low quality experimental sequences .
in order to determine if dispare could improve low quality matrices using sequences containing high quality binding sites, we ran our algorithm on the datasets with the distorted matrices.
the program converged after  <dig> iterations using  and  <dig> iterations using .
the dispare matrix and the width-optimized matrix recovered the motif core 'acgtgc' for  and  .
to measure the performance again after refinement of the distorted matrices, we generated the roc curves of  and  before and after the discriminative optimization step .
we did not increase the auc in both cases.
the performance of the initial matrix , the dispare matrix  and the width-optimized matrix  did not change for .
however, as we used a more distorted matrix , we got different results.
the increase of the auc from the initial matrix  to the dispare matrix  and to the width-optimized matrix  for  shows a gain in the sensitivity and specificity in the whole roc space from the initial matrix to the dispare and the width-optimized matrices.
furthermore, we saw no improvement in our test using  as input since this matrix was slightly distorted compared to the reference sites contained in the datasets.
we demonstrated that dispare improved the model significantly in the case of a strongly distorted matrix like .
we also measured the gain in information content after width optimization step.
before optimization, the values of the information content of the initial matrices  and  were respectively equal to  <dig>  and  <dig> .
after running dispare, we improved these values to  <dig>  and  <dig> .
regardless of the degree of distortion, dispare was able to improve the matrices using the information from high quality sequence data, providing width-optimized matrices with stronger information content.
the test on distorted data demonstrated that our algorithm was able to recover and refine matrices with low information content using good quality reference binding sites.
in the following test, we perform a similar assessment by refining known matrix models using three different chip-pet datasets.
chip-pet data
human p53
p <dig> is a tumor suppressor protein encoded by p <dig> gene and binds to dna in the cells.
due to its role in normal cells as the 'guardian of the genome', it is believed that p <dig> is inactivated in more than half of known human cancers  <cit> .
in order to fully understand the role of p <dig>  it will be crucial to determine its complete set of target genes.
the initial p <dig> matrix  comes from jaspar and was characterized by selex  <cit> .
the dna binding site of p <dig> consensus is a palindrome 'ggacatgcccgggcatgtcc' of  <dig> nucleotides .
the p <dig> pwm has asymmetrical information content, showing a stronger left half-site.
the cytosine at position  <dig> and the adenine at position  <dig> are indeed essential for high-affinity dna binding activity and transactivation  <cit> .
<dig> human p <dig> chip-pet sequences  <cit>  were used as positive sequences, and  <dig> sequences from non-coding regions in the human genome hg <dig> assembly as background sequences to optimize the initial p <dig> matrix from jaspar.
we ran the dispare discriminative optimization step and after  <dig> iterations, the algorithm converged and returned an optimized matrix, referred to as dispare matrix  corresponding to an improved form of the initial pwm refined with the sequence data.
the dispare matrix has the same length  and phase as the initial matrix from jaspar.
the dispare matrix recovered the two half sites of p <dig> and improved the strength of the right half-site.
after optimizing the matrix with dispare, the width of the matrix was considered for improvement.
the width optimization feature of dispare enables the exploration of different lengths  and phase shifts for the input matrix .
in this example, we searched all the possibilities of enlarging the input matrix by  <dig> to  <dig> nucleotides and performed phase adjustment by trying all possible shifts in  <dig> nucleotide increment,  <dig> nucleotides around the matrix position.
after running the dispare width optimization algorithm, we obtained a new matrix referred to as width-optimized matrix.
this matrix has the same length as the initial matrix and the dispare matrix, but the phase has been shifted on the right by one column .
this width-optimized matrix improved the initial jaspar matrix in two aspects.
first, the nucleotide strengths at each position have been refined with regards to the knowledge about p <dig> binding sites provided by the chip-pet data.
this is shown by the region between the two half-sites which now look very similar to the matrix derived from the chip-pet data in  <cit> .
furthermore, we gained additional knowledge from the chip-pet sequences, particularly the identification of an extra cytosine on the right side of the pwm after the phase optimization, and therefore obtained a matrix with better specificity.
the roc performances of the dispare matrix and the width-optimized matrix are compared to the ones of jaspar and four selected motif discovery programs: bayesmd, meme, prego and weeder .
the motifs returned by these tools were obtained using their default parameters and the search lengths were set according to each program's limitations .
meme was used with the -cons option using the consensus 'ccggacatgcccgggcatgt' as prior information.
the pwms from bayesmd, meme, prego and weeder were respectively  <dig>   <dig>   <dig> and  <dig> nucleotides long.
the overall roc performance of the dispare matrix  and the width-optimized matrix  were similar to the ones obtained using jaspar , bayesmd  and meme , and outperformed the prego and weeder matrices which only captured the left half-site.
these two k-mer based methods were indeed limited to finding motifs of length shorter or equal to  <dig>  although the auc of these four matrices are very similar , the optimized matrix achieved higher sensitivity than the initial matrix in the  false positive rate interval.
the performance increase was small here since the initial matrix had strong information content.
mouse nanog
nanog is one of the key tfs that regulates self-renewal and pluripotency in embryonic stem cells.
the initial matrix  comes from transfac.
the motif was identified by nestedmica  <cit>  in the nanog chip-pet dataset  <cit>  and it is  <dig> nucleotides long .
we used  <dig> mouse nanog chip-pet sequences  <cit>  as positive sequences, and  <dig> sequences from non-coding regions in the mouse genome mm <dig> assembly as background sequences.
after running the discriminative refinement algorithm on the chip-pet dataset for  <dig> iterations, the algorithm converged and we obtained the dispare matrix shown in figure 5b.
the information of the nanog motif was refined using the chip-pet sequences from  <cit> .
after the dispare discriminative refinement step, we attempted to obtain a better motif width for the dispare matrix.
the width optimization step returned a width-optimized matrix of the same length  but centered the matrix around the motif core 'catttcc'.
the information of the width-optimized matrix was changed according to this new width .
we then compared the roc performances of the dispare matrix and the width-optimized matrix with the ones of the initial transfac matrix, and matrices obtained with bayesmd, meme, prego and weeder .
we ran meme in supervised mode using the consensus 'ccatttcc' as prior information.
the initial matrix has a poor roc performance, shown by an area under curve of  <dig> .
this can be explained by the lack of information in the initial matrix.
the low complexity of the nanog motif can be confused with random background, yielding a high rate of false positives.
we observed a significant improvement in the roc performance for the dispare matrix .
furthermore, our algorithm outperformed both k-mer based methods: prego  and weeder , and probabilistic methods: bayesmd  and meme .
statistical approaches such as meme, bayesmd and nestedmica  tend to produce noisier pwms than k-mer constrained approaches, weakening the roc performance.
in this case, the width-optimized matrix  did not improve the performance of the dispare matrix.
the width optimization algorithm tends to center the matrix around the strongest signal in a motif.
however, the nanog motif consists of two parts, with a weak left side.
the proposed new width missed this left side of the motif and was therefore suboptimal compared to the dispare matrix.
the results of this test demonstrate that the dispare algorithm can significantly improve pwm with low information content and represents a good alternative to classical de novo motif discovery methods.
human estrogen receptor α
the estrogen receptor  is a ligand-dependent tf that binds to conserved estrogen response elements , 5'-ggtcannntgacc-3', where n is any nucleotide.
there are two er subtypes, erα and erβ that belong to the nuclear receptor family.
erα whose gene name is esr <dig> is over-expressed in >70% of breast cancer cases and is likely to be involved in tumorigenesis, although the mechanism underlying this involvement is still unclear  <cit> .
we used  <dig> human estrogen receptor α binding sites chip-pet sequences  <cit>  as positive sequences, and  <dig> sequences from non-coding regions in the human genome hg <dig> assembly as background sequences.
running the discriminative optimization algorithm with the jaspar esr <dig> matrix  as input , we obtained a dispare matrix after  <dig> iterations .
the width and phase optimization algorithm returned a width-optimized matrix of the same length and phase as the initial motif as shown in figure 6c.
both matrices recovered the functional ere consensus  and clearly showed the canonical ere consensus with a gap of  <dig> random nucleotides between the two half-sites.
we then compared the roc performances of the dispare matrix and the width-optimized matrix with the ones of the initial jaspar matrix and matrices obtained with bayesmd, meme, prego and weeder .
meme was used with the -cons option using the consensus 'ccaggtcaccgt-gacccc' as prior information.
the dispare matrix obtained the same results as the bayesmd  and performed performed better than all other methods in the high specificity range .
as the discriminative step of our algorithm returned a dispare matrix consisting of high quality matching sites, the ere element has been over-selected, while flanking  and spacing columns  containing low information have been cleaned.
therefore, as shown on the roc curve, the dispare matrix improved the sensitivity of the motif in the high specificity range .
however, the information that had been removed contributed to the sensitivity when more false positives  were allowed, explaining the improved behaviour of the initial matrix in that interval.
the width and phase optimization step returned a width-optimized matrix with the same width as the dispare matrix and therefore showed a similar performance .
in this test, we showed that dispare enabled us to obtain a better matrix with stronger information in both functional ere half-sites.
we also observed a performance increase in the high specificity range, meaning that the optimized matrices would perform better than the others, using high thresholds.
CONCLUSIONS
computational characterization of the binding specificity of transcription factors  is a challenge to the analysis of transcriptional regulation.
pwms are widely used to identify tfbs although they result in a large number of false positives.
the general concept of tfbs prediction is to find a set of over-represented sites in a set of sequences of interest compared to a tfbs depleted background set.
many strategies have been proposed, falling into two large categories.
probabilistic approaches are the most widely used methodologies to solve motif discovery problems.
the general concept consists of performing a local multiple alignment on the input sequences to build a pwm.
programs such as the gibbs sampler  <cit> , nestedmica  <cit>  or bayesmd  <cit>  use gibbs sampling to achieve this goal while meme  <cit>  and a number of other tools use expectation maximization.
k-mer based methods infer pwms from sets of statistically significant words that do not differ by more than a certain number of mismatches.
these programs include weeder  <cit> , prego  <cit>  or scanseq  <cit> .
however, presently available motif discovery algorithms suffer from a lack of sensitivity and specificity, resulting in noisy and incorrectly framed pwms.
a number of studies have used computational methods to improve pwms.
bucher   <cit>  proposed an iterative approach to maximize the over-representation of sites in a window inside a set of aligned promoter sequences enriched with the tfbss of interest.
however, this method assumes that all the subsequences within the preferred window contain functional sites, omitting the problem of false positives.
tsunoda et al.
<cit>  improved the original algorithm by introducing an estimate of the background frequency of sites.
gershenzon et al.
<cit>  proposed a novel approach to improve the sensitivity and specificity of pwms by maximizing the correlation coefficient instead of the over-representation of sites.
in this paper, we have investigated the refinement of existing matrix models and have focused on the optimization of their width and information content.
dispare requires a set of positive sequences, a set of background sequences and an initial pwm as input.
our iterative algorithm used a variable threshold for each iteration, so that dispare selected subsequences in the original set that scored above the current threshold to build a new matrix.
the algorithm stopped after a fixed number of iterations or when the dissimilarity between two consecutive pwms was smaller than a certain threshold.
in the present study, we considered only the maximum scoring occurrence per sequence.
in addition, we proposed the optional width and phase optimization step to search a better width for the dispare matrix.
it returns the best candidate with optimal length and phase.
although changing the phase of the dispare matrix can slightly affect the auc, the width optimization step can also improve the 'biological value' of the matrix as described in the p <dig> study.
in figure  <dig>  we showed that although the width-optimized matrix and the dispare matrix have the same auc , the width-optimized matrix is the most biologically interesting solution as it returns a pwm with additional binding information on the column farthest to the right, i.e the extra cytosine that is absent from the original jaspar model.
the dispare algorithm was evaluated on artificial and real datasets in order to measure its performance in both controlled and practical conditions.
the simulations on distorted synthetic data demonstrated that the algorithm was able to recover and enhance the matrix of a known tfbs if the matrix was strongly distorted.
the test on distorted matrices showed that our algorithm improves the information content of weak motifs, even though the information content is not directly optimized.
we used the original and distorted matrices as input in order to evaluate the robustness against noise.
since known matrices often differ from models that are derived from real datasets, it would have been interesting to repeat the simulation using the original matrix as input to derive the models from the two distorted datasets.
instead, we performed this test on real data.
using chip-pet data, we demonstrated that our algorithm optimized the initial matrices, thereby improving the sensitivity and specificity of the initial matrix.
width optimization step can significantly improve the performance of the initial and dispare matrices, especially in cases of symmetrical motifs that do not contain strong information on the flanking columns.
the choice of an optimal window is not trivial and several solutions can exist.
therefore, the width optimization algorithm can be used in a semi-automated way, by selecting which window to return.
furthermore, the comparison with four motif discovery tools bayesmd, meme, prego and weeder showed, in most cases, that our refined matrices performed better than those derived from these tools.
probabilistic methods were, in general, better than k-mer based approaches on real data, achieving performances that were comparable to dispare.
k-mer based approaches were penalized by their motif length limitations since the motifs in the chip-pet datasets consisted of  <dig> or more nucleotides.
therefore, when the tf is known, the use of a discriminative matrix refinement approach, starting with a known matrix, seems to be more appropriate and offers a good alternative to presently available de novo motif discovery methods.
in addition, combining motif discovery with matrix refinement into an integrated analysis framework in order to enhance the signal of computationally discovered matrices can significantly improve the results, making matrix annotation and identification easier.
in this study, we presented dispare, an algorithm to refine a motif that best discriminates between a positive set of sequences and a background one.
refined matrices are centered, their widths are optimized and they show an improvement in their information content.
the algorithm was applied to several sets of synthetic data, distorted data and three sets of chip-pet data.
the results showed that the dispare algorithm improves the sensitivity and specificity of matrix models for tfbss.
this can be used as a good alternative to classical motif scanning methods or combined with de novo motif discovery programs.
in this version, we only kept one occurrence of a motif, corresponding to the maximum score per sequence and the algorithm returned the most centered and informative refined matrix only.
however, because the same transcription factor binding site  often occurs in many instances, it would be interesting to compare the final matrices, obtained with several scores per sequence, with those obtained with the maximum score per sequence.
in the future, the program can be extended to support multiple motif occurrences and allow the optimization of several windows.

 gene expression is controlled by the interaction of transcription factors and their dna binding sites. promoters often contain multiple binding sites for different tfs that work in tandem to control the regulation of gene expression. tfs bind to short degenerate dna sequence patterns or motifs, which makes them relatively difficult to find. understanding the regulation of gene expression in higher eukaryotes is still a major challenge and the current algorithms are not always able to clearly distinguish real transcription factor binding sites from random look-alike sequences. position-weight matrices are widely used to represent tfbs in promoter regions of genes. unfortunately, many of these pwms have low information content and match a huge number of sequences in the genome. however, most of these matches are likely to be false positives. pwms are commonly used due to lack of better alternatives. pwms are calculated from position frequency matrices that contain the observed nucleotide frequencies at each position in the profile alignment of binding sites for a tf of interest. most of the known matrix models for tfbs can be obtained from the jaspar and transfac databases, together with the set of binding sites used to build them. tfbs based on dnase i footprinting experiments can be found in the dnase i database for drosophila melanogaster. furthermore, the matrices are often derived from a limited number of experimentally verified sequences, which leads to inaccurate representations of tf-dna binding affinities. today, wet-lab technologies such as chromatin immunoprecipitation are commonly used to identify in vivo tf binding locations. chip-chip and chip-pet analyses provide large amounts of data and will therefore pave the way for the construction of more precise pwms. in particular, these experiments provide an opportunity to computationally improve the accuracy of existing position-specific matrices. it is this important problem that we address in the present study.  we have created dispare, a two-step algorithm that takes a known matrix as its input, performs an iterative and discriminative refinement using experimentally verified tfbs and background sequences. after the discriminative optimization step, dispare returns an optimized matrix with improved information referred to as a dispare matrix. using the width and phase optimization step, a width-optimized matrix is obtained with improved information and optimized width and phase. in order to evaluate the performance of our algorithm, we applied it to several synthetic datasets. we then tested dispare using mammalian transcription factor binding sites from experimental chip-pet data: human p motif from, mouse nanog and human estrogen receptor α binding sites. synthetic data we first applied dispare to synthetic data to evaluate its performance under known conditions. a motif was artificially implanted in each of the randomly generated sequences at a random position. the implanted pattern is described by a weight matrix wma of width and characterized by the consensus'acgtca'. we arbitrarily used the ma jaspar matrix as the initial matrix. we generated a set of random, nucleotide-long sequences as a positive set using decodeanhmm, a hmm-based random sequence generator. the order of the markov model was chosen to be equal to so that all nucleotides in the generated sequences were independent of each other. these sequences were gc-rich, containing 30% g, 30% c, 20% a and 20% t. the generated sequence set was divided into a training set and a test set of equal sizes, i.e of sequences each. we copied and shuffled the randomly generated sequences to obtain two corresponding background sets of sequences each. we ran dispare on the positive and background sequences, using the matrix wma as input. the algorithm first performs an iterative matrix optimization by calculating cut-offs that discriminate best between the two datasets. after running the dispare discriminative optimization step for iterations, we obtained a dispare matrix. after the first optimization step, the algorithm performs width and phase optimization on the dispare matrix in order to investigate whether a better width can be found for the input matrix. this step can improve the accuracy of pwms because initial matrices often have sub-optimal length and phase. the phase can be defined as position of the window, relatively to the actual pattern on the dna. in this example, since the pwm was already in its optimal form, the length and phase remained unchanged. the width-optimized matrix thus obtained was nucleotides long. we compared the performances of the initial matrix, dispare matrix and width-optimized matrix to four pwms obtained with four de novo motif discovery programs: bayesmd, meme, prego and weeder. the roc curves of this assessment are illustrated in figure 1d. we ran meme using the consensus'acgtca' as prior information so that we could compare our program with another supervised approach. dispare improved the initial matrix by increasing the auc from to and outperformed bayesmd. however, meme achieved the same result as the dispare matrix under supervision with the consensus'acgtca' as prior information. k-mer based methods gave different results: prego was able to find the motif wma, achieving an auc of, while weeder failed to recover the motif wma which is why an roc curve for this tool is omitted in figure 1d. the width-optimized matrix improved the performance of the dispare matrix due to the additional information enhancement step provided by the width optimization algorithm after the choice of the optimal frame. test of robustness using two synthetic matrices an important challenge in motif finding is to design methods that can accommodate datasets of various sizes and background compositions. in order to evaluate the robustness of dispare in this context, we constructed five new datasets using the initial synthetic matrix wma. we increased the number of sequences to from while keeping the length of sequences constant at nucleotides and the same composition of nucleotides in set the difference between set and set is the increase in the length of the sequences to nucleotides. set has the same size as the dataset used in figure but has a different background composition. for sets and we generated datasets with sequences of nucleotides with two different background compositions. as described above, we divided each set of newly generated sequences into a test set and a training set of equal sizes i.e of sequences each. we ran dispare and the four selected motif discovery programs on these five datasets and obtained roc curves illustrated in additional file 2: figure s as before, meme was run using a supervised mode with the consensus'acgtca' as prior information. running dispare on test set which contained a higher number of sequences, improved the initial matrix once again by increasing the auc of both dispare matrix and width-optimized matrix to and performed better than prego. meme achieved a similar result by accurately capturing the motif wma. we did not find any suitable motifs for this set using bayesmd and weeder despite several runs. encouraged by this result, we increased the sequence length in set to check the impact of varying sequence lengths on the algorithm. in this test, the dispare matrix and the width-optimized matrix improved the initial matrix. they performed better than prego matrix. however, meme with supervision achieved a better result. again, bayesmd and weeder failed to recover the nucleotide-long motif. in the third test,, we investigated the effects of a change in the background composition on the results. again, our algorithm recovered the motif wma in this test, showing that changing the background, in which the sites were implanted, had no impact on the accuracy of dispare. finally, we compared the behaviour of each program using random sequences of length sets and were designed to produce a strong pattern-drowning effect for motif wma, as such a short and'random' pattern was likely to occur in several locations by chance. in test using a gc-rich background, we showed that dispare, meme and bayesmd successfully recovered the motif wma, while prego and weeder failed to capture the correct consensus. finally, in test using a uniform background, we found that only dispare, meme and prego were able to capture the motif with a low sensitivity. this low value can be interpreted as the'baseline' prediction rate for the wma matrix for this dataset. these last two tests showed that our discriminative approach is robust against noise, accurately returning a refined matrix from large datasets. in these five tests, we showed that dispare consistently improved the initial matrix and achieved one of the two best roc performances each time. the width optimization step did not yield further improvements since the initial matrix was already in its most compact form. interestingly, we found that for sets larger than sequences, bayesmd and weeder failed the test, despite several runs to find a matrix. this can be explained by the'randomness' of the matrix wma consensus or by the statistical background models used in these two approaches which do not recapitulate the background sequences accurately. prego, which uses the actual background sequences as input, was able to recover the planted motif. similarly, meme uses a 0th order background in its default settings which seemed to work better in this assessment than bayesmd and weeder which use higher order backgrounds by default. after evaluating dispare using five different datasets for the matrix wma, we re-tested it against a new synthetic matrix. we used the matrix wm to generate five new positive and background datasets and changed parameters such as the number of sequences, the background composition and the length of the sequences. the synthetic wm motif is nucleotides long and contains the central pattern'acgtgc'. as described above, we divided each set into a training set and a test set, on which the assessments were performed. we generated a corresponding set of background sequences by shuffling each set of positive sequences. the roc curves of these five tests are shown in additional file 3: figure s we ran the de novo motif finding program meme using the consensus'tacgtgcg' as prior information so that we could compare dispare with another program running in supervised mode. in test a, we ran dispare on a set of sequences, each being nucleotides long, with a gc-rich background. the initial matrix, the dispare matrix and the width-optimized matrix obtained similar results and did better than the four motif discovery methods. in test b, we increased the sequence length to nucleotides and compared it with the set a. again, the initial matrix, the dispare matrix and the width-optimized matrix obtained the best auc. more interestingly, we found that three tested motif discovery tools could not find the matrix wm accurately. meme, however, which used a 0th order background and prior information was able to find the motif wm in this configuration. this test demonstrates that dispare is robust against pattern drowning and performs accurately with increasing sequence length and the number of sequences. we then wondered whether background sequence composition could affect the performance of our matrix refinement algorithm. in test c, we constructed a dataset of sequences spanning nucleotides and containing equal proportion of each nucleotide. the dispare matrix, the width-optimized matrix and the initial matrix obtained similar results and performed better than other approaches. this test showed that background composition had no impact on the accuracy of dispare. finally, in tests d and e we evaluated dispare and the four selected programs under the extreme situation of looking for the motif wm in kb long input sequences. the sequence sets contain sequences but the background composition is gc-rich and uniform. in test d, the roc curves show a global decrease of accuracy compared to the test with shorter sequences. however, the dispare matrix and the width-optimized matrix recovered the initial model. dispare performed better than other programs in test d, meme and bayesmd. we repeated the test with a different background. the initial matrix, dispare matrix and width-optimized matrix obtained consistently similar outcomes. we observed that other methods performed better than in test d. increasing the number of sequences or using longer sequences had no impact on the performance of dispare, unlike motif discovery methods which can sometimes suffer from pattern drowning, i.e. lose the ability to capture the motif signal when the latter is embedded in large amounts of random sequences. furthermore, we also obtained similar results while running dispare on background sequences with a different composition. the performance gain in these tests was expected to be small since the input matrix was the same as the one that we used to build the five datasets. the purpose of this assessment was to evaluate the robustness of dispare under various operating conditions. the tests on synthetic data showed that dispare was able to improve the width and information of an initial matrix using sequences containing sites described by the same matrix. in the next test, to assess the performance of dispare under more realistic conditions, we distorted the initial synthetic matrix wm and ran the assessment again on the same datasets. data distortion we tested the ability of dispare to improve a matrix with distorted information using high quality transcription factor binding sites provided by a positive set. using the initial synthetic data matrix wm we generated two distorted matrices, and, with the same width as the initial matrix wm. this initial synthetic matrix is nucleotides long and consists of the core motif'acgtgc' in the center. uniformly distributed noise was added to the matrix m to create the elements of m'. the elements of the noise matrix u are uniformly distributed random numbers between and a constant k was used to set the amplitude of noise. we used a constant to obtain the first matrix and used a larger constant to obtain a second matrix with more distortion. m' can therefore be expressed as m' = m+ku. the distorted matrices are normalized in a column-wise manner before being returned in order to obtain correct position frequency matrices. we calculated the degree of data distortion from to m and from to m. first, we measured the signal attenuation after distorting the matrices with noise. the signal attenuation or loss of information content is defined here by the log-ratio of the information content of the original to the distorted matrix, expressed in decibels: for matrix, the information content was attenuated by db and for matrix, the attenuation was equal to db, implying that signal strength is twice as less as. we then evaluated the data distortion by calculating the difference of frobenius norm. the frobenius norm is defined as it is often used in linear algebra to measure the distortion of a matrix as it is proportional to the mean squares of the errors. the relative value difference of the frobenius norm represents the relative error between the elements of the original and distorted matrices: where v d is the difference of the frobenius norm from m' to m divided by the frobenius norm of m. v d values for and were respectively v d = and v d =. is lightly attenuated and distorted, and therefore mimics the case when the count matrix was built with good quality sites. mimics the case when sites come from either computational prediction or from low quality experimental sequences. in order to determine if dispare could improve low quality matrices using sequences containing high quality binding sites, we ran our algorithm on the datasets with the distorted matrices. the program converged after iterations using and iterations using. the dispare matrix and the width-optimized matrix recovered the motif core'acgtgc' for and. to measure the performance again after refinement of the distorted matrices, we generated the roc curves of and before and after the discriminative optimization step. we did not increase the auc in both cases. the performance of the initial matrix, the dispare matrix and the width-optimized matrix did not change for. however, as we used a more distorted matrix, we got different results. the increase of the auc from the initial matrix to the dispare matrix and to the width-optimized matrix for shows a gain in the sensitivity and specificity in the whole roc space from the initial matrix to the dispare and the width-optimized matrices. furthermore, we saw no improvement in our test using as input since this matrix was slightly distorted compared to the reference sites contained in the datasets. we demonstrated that dispare improved the model significantly in the case of a strongly distorted matrix like. we also measured the gain in information content after width optimization step. before optimization, the values of the information content of the initial matrices and were respectively equal to and. after running dispare, we improved these values to and. regardless of the degree of distortion, dispare was able to improve the matrices using the information from high quality sequence data, providing width-optimized matrices with stronger information content. the test on distorted data demonstrated that our algorithm was able to recover and refine matrices with low information content using good quality reference binding sites. in the following test, we perform a similar assessment by refining known matrix models using three different chip-pet datasets. chip-pet data human p53 p is a tumor suppressor protein encoded by p gene and binds to dna in the cells. due to its role in normal cells as the'guardian of the genome', it is believed that p is inactivated in more than half of known human cancers. in order to fully understand the role of p it will be crucial to determine its complete set of target genes. the initial p matrix comes from jaspar and was characterized by selex. the dna binding site of p consensus is a palindrome'ggacatgcccgggcatgtcc' of nucleotides. the p pwm has asymmetrical information content, showing a stronger left half-site. the cytosine at position and the adenine at position are indeed essential for high-affinity dna binding activity and transactivation. human p chip-pet sequences were used as positive sequences, and sequences from non-coding regions in the human genome hg assembly as background sequences to optimize the initial p matrix from jaspar. we ran the dispare discriminative optimization step and after iterations, the algorithm converged and returned an optimized matrix, referred to as dispare matrix corresponding to an improved form of the initial pwm refined with the sequence data. the dispare matrix has the same length and phase as the initial matrix from jaspar. the dispare matrix recovered the two half sites of p and improved the strength of the right half-site. after optimizing the matrix with dispare, the width of the matrix was considered for improvement. the width optimization feature of dispare enables the exploration of different lengths and phase shifts for the input matrix. in this example, we searched all the possibilities of enlarging the input matrix by to nucleotides and performed phase adjustment by trying all possible shifts in nucleotide increment, nucleotides around the matrix position. after running the dispare width optimization algorithm, we obtained a new matrix referred to as width-optimized matrix. this matrix has the same length as the initial matrix and the dispare matrix, but the phase has been shifted on the right by one column. this width-optimized matrix improved the initial jaspar matrix in two aspects. first, the nucleotide strengths at each position have been refined with regards to the knowledge about p binding sites provided by the chip-pet data. this is shown by the region between the two half-sites which now look very similar to the matrix derived from the chip-pet data in. furthermore, we gained additional knowledge from the chip-pet sequences, particularly the identification of an extra cytosine on the right side of the pwm after the phase optimization, and therefore obtained a matrix with better specificity. the roc performances of the dispare matrix and the width-optimized matrix are compared to the ones of jaspar and four selected motif discovery programs: bayesmd, meme, prego and weeder. the motifs returned by these tools were obtained using their default parameters and the search lengths were set according to each program's limitations. meme was used with the -cons option using the consensus'ccggacatgcccgggcatgt' as prior information. the pwms from bayesmd, meme, prego and weeder were respectively and nucleotides long. the overall roc performance of the dispare matrix and the width-optimized matrix were similar to the ones obtained using jaspar, bayesmd and meme, and outperformed the prego and weeder matrices which only captured the left half-site. these two k-mer based methods were indeed limited to finding motifs of length shorter or equal to although the auc of these four matrices are very similar, the optimized matrix achieved higher sensitivity than the initial matrix in the false positive rate interval. the performance increase was small here since the initial matrix had strong information content. mouse nanog nanog is one of the key tfs that regulates self-renewal and pluripotency in embryonic stem cells. the initial matrix comes from transfac. the motif was identified by nestedmica in the nanog chip-pet dataset and it is nucleotides long. we used mouse nanog chip-pet sequences as positive sequences, and sequences from non-coding regions in the mouse genome mm assembly as background sequences. after running the discriminative refinement algorithm on the chip-pet dataset for iterations, the algorithm converged and we obtained the dispare matrix shown in figure 5b. the information of the nanog motif was refined using the chip-pet sequences from. after the dispare discriminative refinement step, we attempted to obtain a better motif width for the dispare matrix. the width optimization step returned a width-optimized matrix of the same length but centered the matrix around the motif core'catttcc'. the information of the width-optimized matrix was changed according to this new width. we then compared the roc performances of the dispare matrix and the width-optimized matrix with the ones of the initial transfac matrix, and matrices obtained with bayesmd, meme, prego and weeder. we ran meme in supervised mode using the consensus'ccatttcc' as prior information. the initial matrix has a poor roc performance, shown by an area under curve of. this can be explained by the lack of information in the initial matrix. the low complexity of the nanog motif can be confused with random background, yielding a high rate of false positives. we observed a significant improvement in the roc performance for the dispare matrix. furthermore, our algorithm outperformed both k-mer based methods: prego and weeder, and probabilistic methods: bayesmd and meme. statistical approaches such as meme, bayesmd and nestedmica tend to produce noisier pwms than k-mer constrained approaches, weakening the roc performance. in this case, the width-optimized matrix did not improve the performance of the dispare matrix. the width optimization algorithm tends to center the matrix around the strongest signal in a motif. however, the nanog motif consists of two parts, with a weak left side. the proposed new width missed this left side of the motif and was therefore suboptimal compared to the dispare matrix. the results of this test demonstrate that the dispare algorithm can significantly improve pwm with low information content and represents a good alternative to classical de novo motif discovery methods. human estrogen receptor α the estrogen receptor is a ligand-dependent tf that binds to conserved estrogen response elements, 5'-ggtcannntgacc-3', where n is any nucleotide. there are two er subtypes, erα and erβ that belong to the nuclear receptor family. erα whose gene name is esr is over-expressed in >70% of breast cancer cases and is likely to be involved in tumorigenesis, although the mechanism underlying this involvement is still unclear. we used human estrogen receptor α binding sites chip-pet sequences as positive sequences, and sequences from non-coding regions in the human genome hg assembly as background sequences. running the discriminative optimization algorithm with the jaspar esr matrix as input, we obtained a dispare matrix after iterations. the width and phase optimization algorithm returned a width-optimized matrix of the same length and phase as the initial motif as shown in figure 6c. both matrices recovered the functional ere consensus and clearly showed the canonical ere consensus with a gap of random nucleotides between the two half-sites. we then compared the roc performances of the dispare matrix and the width-optimized matrix with the ones of the initial jaspar matrix and matrices obtained with bayesmd, meme, prego and weeder. meme was used with the -cons option using the consensus'ccaggtcaccgt-gacccc' as prior information. the dispare matrix obtained the same results as the bayesmd and performed performed better than all other methods in the high specificity range. as the discriminative step of our algorithm returned a dispare matrix consisting of high quality matching sites, the ere element has been over-selected, while flanking and spacing columns containing low information have been cleaned. therefore, as shown on the roc curve, the dispare matrix improved the sensitivity of the motif in the high specificity range. however, the information that had been removed contributed to the sensitivity when more false positives were allowed, explaining the improved behaviour of the initial matrix in that interval. the width and phase optimization step returned a width-optimized matrix with the same width as the dispare matrix and therefore showed a similar performance. in this test, we showed that dispare enabled us to obtain a better matrix with stronger information in both functional ere half-sites. we also observed a performance increase in the high specificity range, meaning that the optimized matrices would perform better than the others, using high thresholds.  computational characterization of the binding specificity of transcription factors is a challenge to the analysis of transcriptional regulation. pwms are widely used to identify tfbs although they result in a large number of false positives. the general concept of tfbs prediction is to find a set of over-represented sites in a set of sequences of interest compared to a tfbs depleted background set. many strategies have been proposed, falling into two large categories. probabilistic approaches are the most widely used methodologies to solve motif discovery problems. the general concept consists of performing a local multiple alignment on the input sequences to build a pwm. programs such as the gibbs sampler, nestedmica or bayesmd use gibbs sampling to achieve this goal while meme and a number of other tools use expectation maximization. k-mer based methods infer pwms from sets of statistically significant words that do not differ by more than a certain number of mismatches. these programs include weeder, prego or scanseq. however, presently available motif discovery algorithms suffer from a lack of sensitivity and specificity, resulting in noisy and incorrectly framed pwms. a number of studies have used computational methods to improve pwms. bucher proposed an iterative approach to maximize the over-representation of sites in a window inside a set of aligned promoter sequences enriched with the tfbss of interest. however, this method assumes that all the subsequences within the preferred window contain functional sites, omitting the problem of false positives. tsunoda et al. improved the original algorithm by introducing an estimate of the background frequency of sites. gershenzon et al. proposed a novel approach to improve the sensitivity and specificity of pwms by maximizing the correlation coefficient instead of the over-representation of sites. in this paper, we have investigated the refinement of existing matrix models and have focused on the optimization of their width and information content. dispare requires a set of positive sequences, a set of background sequences and an initial pwm as input. our iterative algorithm used a variable threshold for each iteration, so that dispare selected subsequences in the original set that scored above the current threshold to build a new matrix. the algorithm stopped after a fixed number of iterations or when the dissimilarity between two consecutive pwms was smaller than a certain threshold. in the present study, we considered only the maximum scoring occurrence per sequence. in addition, we proposed the optional width and phase optimization step to search a better width for the dispare matrix. it returns the best candidate with optimal length and phase. although changing the phase of the dispare matrix can slightly affect the auc, the width optimization step can also improve the'biological value' of the matrix as described in the p study. in figure we showed that although the width-optimized matrix and the dispare matrix have the same auc, the width-optimized matrix is the most biologically interesting solution as it returns a pwm with additional binding information on the column farthest to the right, i.e the extra cytosine that is absent from the original jaspar model. the dispare algorithm was evaluated on artificial and real datasets in order to measure its performance in both controlled and practical conditions. the simulations on distorted synthetic data demonstrated that the algorithm was able to recover and enhance the matrix of a known tfbs if the matrix was strongly distorted. the test on distorted matrices showed that our algorithm improves the information content of weak motifs, even though the information content is not directly optimized. we used the original and distorted matrices as input in order to evaluate the robustness against noise. since known matrices often differ from models that are derived from real datasets, it would have been interesting to repeat the simulation using the original matrix as input to derive the models from the two distorted datasets. instead, we performed this test on real data. using chip-pet data, we demonstrated that our algorithm optimized the initial matrices, thereby improving the sensitivity and specificity of the initial matrix. width optimization step can significantly improve the performance of the initial and dispare matrices, especially in cases of symmetrical motifs that do not contain strong information on the flanking columns. the choice of an optimal window is not trivial and several solutions can exist. therefore, the width optimization algorithm can be used in a semi-automated way, by selecting which window to return. furthermore, the comparison with four motif discovery tools bayesmd, meme, prego and weeder showed, in most cases, that our refined matrices performed better than those derived from these tools. probabilistic methods were, in general, better than k-mer based approaches on real data, achieving performances that were comparable to dispare. k-mer based approaches were penalized by their motif length limitations since the motifs in the chip-pet datasets consisted of or more nucleotides. therefore, when the tf is known, the use of a discriminative matrix refinement approach, starting with a known matrix, seems to be more appropriate and offers a good alternative to presently available de novo motif discovery methods. in addition, combining motif discovery with matrix refinement into an integrated analysis framework in order to enhance the signal of computationally discovered matrices can significantly improve the results, making matrix annotation and identification easier. in this study, we presented dispare, an algorithm to refine a motif that best discriminates between a positive set of sequences and a background one. refined matrices are centered, their widths are optimized and they show an improvement in their information content. the algorithm was applied to several sets of synthetic data, distorted data and three sets of chip-pet data. the results showed that the dispare algorithm improves the sensitivity and specificity of matrix models for tfbss. this can be used as a good alternative to classical motif scanning methods or combined with de novo motif discovery programs. in this version, we only kept one occurrence of a motif, corresponding to the maximum score per sequence and the algorithm returned the most centered and informative refined matrix only. however, because the same transcription factor binding site often occurs in many instances, it would be interesting to compare the final matrices, obtained with several scores per sequence, with those obtained with the maximum score per sequence. in the future, the program can be extended to support multiple motif occurrences and allow the optimization of several windows. 
the accurate determination of transcription factor binding affinities is an important problem in biology and key to understanding the gene regulation process. position weight matrices are commonly used to represent the binding properties of transcription factor binding sites but suffer from low information content and a large number of false matches in the genome. we describe a novel algorithm for the refinement of position weight matrices representing transcription factor binding sites based on experimental data, including chip-chip analyses. we present an iterative weight matrix optimization method that is more accurate in distinguishing true transcription factor binding sites from a negative control set. the algorithm was applied to the increasing collection of known transcription factor binding sites obtained from chip-chip experiments. the results show that our algorithm significantly improves the sensitivity and specificity of matrix models for identifying transcription factor binding sites. when the transcription factor is known, it is more appropriate to use a discriminative approach such as the one presented here to derive its transcription factor-dna binding properties starting with a matrix, as opposed to performing de novo motif discovery.
 the accurate determination of transcription factor binding affinities is an important problem in biology and key to understanding the gene regulation process. position weight matrices are commonly used to represent the binding properties of transcription factor binding sites but suffer from low information content and a large number of false matches in the genome. we describe a novel algorithm for the refinement of position weight matrices representing transcription factor binding sites based on experimental data, including chip-chip analyses. we present an iterative weight matrix optimization method that is more accurate in distinguishing true transcription factor binding sites from a negative control set. the initial position weight matrix comes from jaspar, transfac or other sources. the main new features are the discriminative nature of the method and matrix width and length optimization.  the algorithm was applied to the increasing collection of known transcription factor binding sites obtained from chip-chip experiments. the results show that our algorithm significantly improves the sensitivity and specificity of matrix models for identifying transcription factor binding sites.  when the transcription factor is known, it is more appropriate to use a discriminative approach such as the one presented here to derive its transcription factor-dna binding properties starting with a matrix, as opposed to performing de novo motif discovery. generating more accurate position weight matrices will ultimately contribute to a better understanding of eukaryotic transcriptional regulation, and could potentially offer a better alternative to ab initio motif discovery. 