BACKGROUND
transcription of genes followed by translation of their transcripts into proteins determines the type and functions of a cell.
expression of certain genes even initiates or suppresses differentiation of stem cells.
it is therefore crucial to understand the mechanisms of transcriptional regulation.
among them, transcription factor  binding is the one that has been given considerable attention by computational biologists for the past decade and is still being actively researched.
a tf is a protein or protein complex that regulates transcription of one or more genes by binding to the double-stranded dna.
a first step in computational identification of target genes regulated by a tf is to pinpoint its binding sites in the genome.
once the binding sites are found, the putative target genes can be searched and located in flanking regions of the binding sites.
in general, there are two approaches to computational transcription factor binding site  identification, motif discovery and tfbs search.
the former assumes that a set of sequences is given and each of the sequences may or may not contain tfbss.
an algorithm then predicts the locations and lengths of tfbss.
the term motif refers to the pattern that are shared by the discovered tfbss.
these algorithms rely on no prior knowledge of the motif and hence are known as de novo motif discovery algorithms.
the latter assumes that, in addition to a set of sequences, the locations and lengths of tfbss are known.
an algorithm then learns from these examples and predicts tfbss in new sequences.
such algorithms are also called supervised learning algorithms since they are guided by the given sequences with known tfbss.
plenty of efforts have been devoted to the de novo motif discovery problem
<cit> .
comprehensive evaluation and comparison of the developed tools have been performed
<cit> .
in this study, we focus on the problem of tfbs search.
we refer readers interested in the motif discovery problem to the evaluation and review articles
<cit>  and references therein.
a typical tfbs search method searches for the binding sites of a particular transcription factor in the following manner.
it scans a target dna sequence and compare each length l sub-sequence  to the binding site profile of the tf, where l is the length of a binding site.
each of the l -mer is scored when comparing to the profile.
a cut-off score is then set by the method to select candidate tf binding sites.
the position-specific scoring matrix
<cit>  is a widely used profile representation, where the binding sites of a tf are encoded as a  <dig> × l matrix.
column i of the matrix stores the scores of matching the ith letter in an l -mer to nucleotides a, c, g and t, respectively.
depending on the method of choice, the score of a at position i can be the count of a at position i in the known tfbss, the log-transformed probability of observing a at position i , or any other reasonable number.
once computed, the scoring matrix of a tf can be stored in a database.
these matrices are used by tools
<cit>  to scan sequences for tfbss.
one assumption the pssm representation makes is that positions in a binding site are independent, which is often not the case.
osada et al.
<cit>  exploited dependence between positions by considering nucleotide pairs in scoring methods.
it was shown that incorporating nucleotide pairs significantly improved the performance of a method, meaning that most transcription factors studied demonstrated correlation between positions in a binding site.
this result was reinforced in a recent study
<cit> , in which the authors showed correlations between two nucleotides within a binding site by plotting the mutual information matrix.
a novel scoring method called the ungapped likelihood under positional background  method was proposed in this study.
the ulpb method models a tfbs by two first-order markov chains and scores a candidate binding site by likelihood ratio produced by the two markov chains.
leave-one-out cross-validation results on  <dig> tfs with  <dig> or more binding sites showed that ulpb is superior to the methods compared in their work.
in this work, we approach the tfbs search problem from a different perspective.
we propose to search for binding sites in vector spaces.
specifically, l -mers are placed in the euclidean space such that each l -mer corresponds to a vector in the space.
with known binding sites of a tf, we construct a profile vector for the tf.
this profile vector can then be used as a query vector to search for the unknown binding sites in the space given a similarity measure between two vectors.
the vector space model has long been used in information retrieval
<cit> .
under this model, each document in a collection is embedded in a t -dimensional space.
that is, each document is represented by a t -element vector, where t is the number of distinct terms present in the document collection or corpus.
to search for documents on a particular topic, a query composed of terms relevant to the topic is constructed.
the query can be similarly embedded in the t -dimensional space.
similarity between the query and a document can then be measured by measuring the similarity between the two corresponding vectors.
in the tfbs search problem, the entire genome or the collection of promoter region sequences corresponds to the corpus, whereas an l -mer is analogous to a document in ir.
on the other hand, a tf is analogous to a topic, while a tf representation is the analog of a query for the topic.
in this framework, we propose two novel approaches to constructing a query vector for a tf of interests.
we compare the proposed methods to a state-of-the-art method, the ulpb method, as well as the widely-used pssm method.
performance of a method is assessed by cross-validation experiments on two data sets collected from regulondb
<cit>  and jaspar
<cit> , respectively.
independent validation on human chip-seq data gives further insights into the proposed methods.
finally, we discuss the advantages of searching for tf binding sites in the proposed framework.
the paper is organized as follows.
in methods, we present the novel negative-to-positive vector and optimal discriminating vector methods, in addition to introducing the existing methods compared in this work.
cross-validation results on prokaryotic and eukaryotic transcription factors are presented and discussed in results and discussion.
finally, we give the concluding remarks in conclusions.
methods
data sets
to understand the compared methods in this work, we experimented on prokaryotic as well as eukaryotic transcription factors.
the known prokaryotic tf binding sites were collected from from regulondb
<cit>  release  <dig> .
considered in
<cit> , this data source contains binding sites of tfs in the e. coli k- <dig> genome.
we considered a data set of  <dig> tfs with  <dig> or more known binding sites.
the filtering criterion ensures that, for each tf, we have enough examples to learn from.
similar filtering criteria were used in
<cit> .
this data set is summarized in table
<dig>
the known eukaryotic tf binding sites were collected from jaspar core database
<cit> .
tfs of homo sapiens and mus musculus were filtered by two criteria.
a tf was kept only if it has at least  <dig> known binding sites and the length of its binding sites is at least  <dig> nucleotides.
the length criterion, arbitrarily chosen, ensures a tf under consideration is specific enough.
this data set is summarized in table
<dig>
notation
for clarity, we list and define functions and variables used throughout this paper.
please see additional file
<dig> for more details.
• fi denotes the probability of observing letter u at position i of a tfbs, where u ∈{a, c, g, t}.
• fi,j denotes the probability of observing letters u and v at positions i and j , respectively, where i <j and u,v ∈{a, c, g, t}.
• fi denotes the position-specific conditional probability of observing v at position i +  <dig> given u has been seen at position i , where u ,v ∈{a, c, g, t}.
• f  denotes the background conditional probability of observing v given u has been observed at the previous position, where u ,v ∈{a, c, g, t}.
•
iu is the indicator function given by
iu=1ifv=u,0otherwise,
where u ,v ∈{a, c, g, t}.
•
iu1u <dig> is similarly defined as follows:
iu1u2=1ifv1=u1andv2=u <dig> otherwise,
where u <dig> u <dig> v <dig> v2∈{a, c, g, t}.
• ici denotes the information content at position i of a binding site.
information content is closely related to entropy, a measure of uncertainty in information theory.
the entropy at position i is given by
ei=−∑u∈{a, c, g, t}filog2fi.
when
fi= <dig> for all u ∈{a, c, g, t}, ei attains the maximal entropy of  <dig> and we are most uncertain about the letter at position i .
ici is simply defined as
ici=2−ei=2+∑u∈{a, c, g, t}filog2fi.
• ici,j denotes the information content of the position pair  of a binding site.
similarly,
ici,j=4+∑u,v∈{a, c, g, t}fi,jlog2fi,j,
where the maximal entropy of  <dig> is attained when
fi,j= <dig> for all u ,v ∈{a, c, g, t}.
embedding short sequences in vector spaces
we describe how a short sequence of l nucleotides or an l -mer is placed in a vector space.
let s be an l -mer and si denote its ith nucleotide.
each nucleotide in s is converted to  <dig> variables, that is, si is converted to
wiia,wiic,wiigandwiit for i =  <dig> ,…,l .
hence, s is converted to 4l variables, placing s in
r4l.
figure
<dig> illustrates the conversion of each nucleotide in an l -mer to  <dig> variables when wi =  <dig> for i =  <dig> ,…,l .
we further consider nucleotide pair , where i < j .
only pairs in close proximity are considered in this study.
we consider  only if j −i =  <dig> or  <dig>  i.e., a pair of nucleotides is considered only if they are adjacent or separated by one nucleotide.
nucleotide pair  is similarly converted to  <dig> variables,
wi,jiaa,wi,jiac,…,wi,jitt, as there are  <dig> possible nucleotide pairs, {aa, ac,…,tt}.
we use 32l − <dig> additional variables to encode the pairs since there are l − <dig> adjacent pairs and l − <dig> pairs separated by one nucleotide.
consequently, considering individual nucleotides and nucleotide pairs, each l -mer is converted to a -element vector.
in this study, we consider two choices of wi’s and wi,j’s.
for the first choice, all the nucleotides and nucleotide pairs are given the same weight, i.e., wi =  <dig> and wi,j =  <dig> for all i and j .
the second one assigns weight to the ith nucleotide according to the information content at position i .
similarly, it assigns weight to pair i ,j) according to the information content at this pair of positions.
specifically,
wi=ici and
wi,j=ici,j for all i and j .
searching for tfbss in vector spaces
given a query vector t in space, we score an l -mer s as follows:
score=stt,
where s denote the corresponding vector of s .
in other words, the score of s is obtained by taking the dot-product between s and t. it can be seen that score measures the similarity between s and t. assuming that t corresponds to an l -mer t , score counts the number of nucleotides and nucleotide pairs shared between s and t when wi =  <dig> and wi,j =  <dig> for all i and j .
however, we note that t can be any vector in the space and does not necessarily correspond to an l -mer.
as described above, an l -mer is converted to a -element vector.
hence, we use t to search for binding sites in
r. our approach offers great flexibility in that it easily allows searching for binding sites in a lower dimensional subspace.
by setting all but the first 4l elements in t to zero, we are essentially searching for binding sites in
r4l.
in this work, we exploit this advantage and simultaneously search for transcription factor binding sites in three subspaces.
two of them are
r4l and
r. the third one is
r. this subspace is obtained from considering only the first nucleotide and the l − <dig> adjacent nucleotide pairs as in a first order markov chain.
the npv method
we first introduce a simple approach to constructing a query vector.
let p be the set of n+ binding sites and n be the set of n−non-binding sites of a particular transcription factor.
we embed all the l -mers in p and n in
r. we then find the mean binding site vector
μ+=1n+∑s∈ps
as well as the mean non-binding site vector
μ−=1n−∑s∈ns.
the query vector t is found by subtracting μ−from μ+, that is, t = μ+−μ−.
the query vector t can be seen as the vector pointing from the center of the non-binding site vectors to the center of the binding site vectors.
hence, we call it the negative-to-positive vector  method.
figure
<dig> illustrates the idea.
the score of an l -mer s given by the npv method is therefore
score=st=stμ+−stμ−.
we can see that it computes the similarity between s and the mean binding site vector as well as the similarity between s and the mean non-binding site vector.
it then scores s by the difference of the two similarity scores.
the more similar s is to the mean binding site vector, the higher the score.
the less similar s is to the mean non-binding site vector, the higher the score.
from the perspective of geometry, we note that score in  is proportional to score/||t|| , where ||t|| is the length of the query vector t. moreover, by virtue of the equality
stt=||s||||t||cosθ,
we know score/||t|| equals the orthogonal projection of s onto t, where θ is the angle formed by vectors s and t .
the computation of score is therefore equivalent to computation of the orthogonal projection of s onto t. similarly, the computation of score in  is equivalent to computation of the orthogonal projection of s onto μ+−μ−.
in figure
<dig>  we observe that vector μ+−μ−is pointing to the left and, projected onto this vector, most of the binding sites are on the left of the non-binding sites.
this implies that most of the binding sites have a higher score than the non-binding sites.
score/||t||∝score.
the odv method
we have described the npv method, which offers a heuristic way of constructing a query vector.
we now introduce a way of finding an optimal query vector
β∈r.
suppose that |p |=n+ and |n |=n−, that is, there are n+ binding sites and n− non-binding sites for a particular tf.
let p ={s,s,…,s} and
n={s,s,…,s} , where s denotes the ithl -mer in the union of the two sets and n =n+ + n−.
we find the optimal βby solving the following minimization problem:
minβ,b,ξ12||β||2+cn+∑i=1n+ξi+cn−∑i=n++1nξi
subject toscore)||β||≥b+1−ξi||β||fors∈p,
score)||β||≤b−1+ξi||β||fors∈n,
ξi≥0∀i.
the constraint in  ensures that the projection of a tfbs s onto the vector β,
score)||β||, exceeds the threshold
b+1||β||.
on the other hand, the constraint in  ensures that the projection of a non-tfbs s onto β stays below the threshold
b−1||β||.
flexibility is given to the thresholds by introducing ξi’s with cost captured by the last two terms in .
finally, to clearly distinguish tfbss from non-tfbss, the squared difference between the two thresholds  is made as large as possible.
this amounts to maximizing
2||β|| <dig> or, equivalently, minimizing
12||β|| <dig>  which is the first term in .
we call this approach the optimal discriminating vector  method.
the optimization problem in  is known as a quadratic programming problem with linear inequality constraints specified in ,  and .
there are p + n +  <dig> variables and 2n constraints, where p =36l − <dig> is the dimension of β. we can see that  and  specify n constraints whereas  imposes n constraints on the variables.
quadratic programming
<cit>  is well-studied and hence general solvers are available, e.g., the openopt framework
<cit> .
to solve this problem, the parameter c  is first arbitrarily chosen.
a solver then searches for values of
β=t, b and
ξ=t such that the objective function in  is minimized while the constraints in ,  and  are satisfied simultaneously.
it can be seen that an optimal solution to  always exists since the search space of {βbξ} is never empty.
to find a feasible solution, one can arbitrarily pick
β≠0∈rp and b ∈r .
for s∈p , one can pick ξi∈r such that the constraint in  is satisfied.
similarly, for s∈n , one can pick ξi∈r such that the constraint in  is met.
we can then compute the value of the objective function as the values of all the variables are known.
one way to choose the parameter c in  is to search for c in a range by cross-validation.
the parameter is tf-dependent in general, but experiments showed that a small c =2− <dig> will usually suffice and hence we set c =2−6for all the odv experiments in this study.
the pssm and ulpb methods
we briefly describe the ungapped likelihood under positional background  method proposed in
<cit>  and the position-specific scoring matrix  method compared therein.
we refer readers to section notation for functions and variables used here.
consider a specific tf with binding sites of length l .
the pssm method scores an l -mer s by
∑i=1llogfi,
where si denotes the ith letter in s .
we note that usually the ratio fi/f  is used in place of fi, where f  is the background probability of si.
the simpler form in  was compared in
<cit>  and hence it serves as a baseline method in this study.
the ulpb models a tfbs by a first-order markov chain and models the background by another first-order markov chain.
the background transition probabilities are estimated using the entire genome of a species and hence the ulpb method uses negative examples implicitly.
it scores an l -mer s by
logf1+∑i=1l−1logfif.
although ulpb does not consider background probability in the first term of , the score is approximately the log-likelihood ratio of the two markov chains.
the main difference between the pssm method and the npv, odv and ulpb methods is that the pssm method does not score nucleotide pairs nor does it utilize a background distribution.
the npv and odv methods explicitly take advantage of negative binding sites, while the ulpb method does it implicitly by using a background distribution.
the flexibility of the proposed framework allows the npv and odv methods to easily search in subspaces, further distinguishing the pssm and ulpb methods from the proposed ones.
RESULTS
performance assessment and evaluation metrics
the performance of a tfbs search method is evaluated by ν -fold cross-validation .
consider a tf with n+ tfbss of length l with flanking regions on both sides.
a set of negative examples, ntest, called the test negatives is constructed from the tfbss of the other tfs with filtering as in
<cit> .
another set of negative examples, ntrain, called the training negatives is collected from sequences embedding the n+binding sites.
it is comprised of all the l -mers except for the tfbss and two neighboring l -mers of each tfbs.
the n+ tfbss are first divided into ν sets, each of which contains
⌊n+ν⌋ or
⌊n+ν⌋ +  <dig> tfbss.
at each iteration of ν -fold cv, one of the ν tfbs sets called the test tfbs setptestis left out.
the rest of the tfbss are therefore called the training tfbss .
a scoring function is obtained using the training tfbss and non-tfbss randomly sampled from the training negatives, where the ratio of numbers of non-tfbss to tfbss is set to  <dig>  the test tfbss in ptest along with the non-tfbss in ntestare then scored by the scoring function.
to score a test sequence, both the forward and reverse strands are scored and, in case the test sequence is longer or shorter than l , the l -mer producing the highest score is used.
for each test tfbs t ∈ptest, we find its rank relative to all the non-tfbss in ntest.
formally, the rank of t equals  <dig> + |{s ∈ ntest|score ≥ score}|.
after the ν -fold cv, we end up with n+ ranks, each of which corresponds to a tfbs.
to allow comparison of methods, we use the area under the roc curve  to gauge the performance of a method on the tf.
the roc curve is a plot of true positive rate  against false positive rate , displaying the trade-off between tpr and fpr.
we refer readers to
<cit>  for an introduction to this metric.
in this study, ν = <dig> for all the cv experiments.
for the npv and odv methods, the best weight and subspace combination is obtained at each iteration of the ν -fold cv.
specifically, another -fold cv is performed on the ν − <dig> sets of tfbss to search for the best combination.
prokaryotic transcription factor binding sites
to understand the behavior of search methods on prokaryotic tf binding sites, we conducted 10-fold cross-validation experiments on the 26-tf regulondb data set.
the proposed npv and odv methods were compared to the ulpb method
<cit> .
the pssm method, considered in
<cit> , was also included for comparison since it served as a simple baseline method.
figure
4a shows the plot of area under the roc curve  across the  <dig> tfs for each method.
we can see that the odv method has the best auc on  <dig> out of  <dig> tfs and the npv method has the best auc on  <dig> out of  <dig> tfs whereas the ulpb and pssm methods have the best auc on  <dig> and  <dig> tfs, respectively.
to gauge the relative performance between two methods, statistical tests
<cit>  were performed on all the  <dig> pairs of methods.
figure
4b shows the p -values of the pair-wise comparisons.
we first notice that, consistent with the results in
<cit> , ulpb outperformed pssm with a slightly larger p -value of  <dig>  than the usual  <dig>  significance cut-off.
as seen in figure
4b, the npv and odv methods are significantly better than the pssm and ulpb methods.
we can see that the odv method benefited from optimization albeit minimizing the objective function in  does not guarantee maximization of the auc.
eukaryotic transcription factor binding sites
here we compare the proposed npv and odv methods to the ulpb and pssm methods on eukaryotic tf binding sites.
as in the previous section, we conducted 10-fold cross-validation experiments on the 28-tf jaspar data set.
figure
5a shows the plot of auc across the  <dig> tfs for each method.
we can see that both the odv and npv methods have the best auc on  <dig> out of  <dig> tfs while the ulpb and pssm methods have the best auc on  <dig> and  <dig> tfs, respectively.
all the methods have the best auc of  <dig> on ma <dig>  and ma <dig>  while the odv, npv and pssm methods have the best auc of  <dig>  on ma <dig> .
similarly, statistical tests
<cit>  were performed on all the  <dig> pairs of methods.
figure
5b shows that the npv and odv methods are significantly better than the pssm and ulpb methods.
ulpb is significantly better than pssm, which is again consistent with the results reported in
<cit> .
overall, performance of the four methods remain unchanged as we shift from prokaryotic transcription factors to eukaryotic ones.
this implies that a tfbs search method effective on prokaryotic transcription factors will perform equally well on eukaryotic transcription factors and vice versa.
motif subtype identification in vector spaces
it has been shown that the binding sites of a tf can be better represented by  <dig> motif subtypes than by a single motif
<cit> .
in search for new binding sites, two position-specific scoring matrices are used to score an l -mer and the higher score of the two is assigned to this l -mer.
searching with two pssms was shown to be superior to searching with a single pssm by cross-species conservation statistics in these studies.
we demonstrate that motif subtypes can be readily identified once we embed l -mers in a vector space.
the purpose here, however, is not to compare motif subtype identification algorithms.
we adopted a slightly different approach to motif subtype identification from those in previous work
<cit> , while the idea is similar.
as usual, all the l -mers were first embedded in a vector space.
the known binding sites of a tf were clustered into two subtypes by the k -means algorithm
<cit> .
immediately, we have a variant of the npv method called the k npv method, where k = <dig> denotes the number of motif subtypes.
the k npv method first computes the mean vectors of these two subtypes, μ+  <dig> and μ+  <dig>  and scores an l -mer s by
score=maxstμ+1−μ−,stμ+2−μ−,
where μ− is the mean vector of the non-binding sites.
figure
<dig> illustrates the k npv method.
similarly, the k odv method scores an l -mer s by
score=maxstβ+1/||β+1||,stβ+2/||β+2||,
where β+ i is obtained using tfbss in cluster i , i = <dig> .
unlike the k npv method, the lengths of β+ i’s may be very different and hence β+ i’s are scaled to unit vectors so as not to bias the scoring function.
we note that the choice of k = <dig> came from previous studies
<cit> .
generally, k can be greater than  <dig> or even automatically selected
<cit> .
this however is beyond the scope of this study and may be investigated in the future.
we assessed the k npv and k odv methods by 10-fold cross-validation on both the regulondb and jaspar data sets.
figure
<dig> shows the results in terms of auc.
we observe in figure
7a that overall introducing motif subtypes into the npv and odv methods improves the search performance .
results in figure
7b also support this observation .
the k npv and k odv are comparable on both the regulondb and jaspar data sets .
these results are consistent with those reported in
<cit> .
independent validation on chip-seq data
to evaluate the proposed npv and odv methods on the whole genome scale, we built tf models using tfbss in the jaspar database to scan all the human  1000-base promoter sequences obtained from the ucsc genome browser database
<cit> .
chip-seq peaks from the encode project were also retrieved
<cit> .
specifically, the wgencoderegtfbsclusteredv <dig> table of build hg <dig> was obtained.
we checked tfs in table
<dig> against the annotations and found  <dig> jaspar tfs, recognized by  <dig> antibodies present in the encode annotations.
the mapping is listed in the first  <dig> columns of table
<dig>
subspaces
r4l,
r and
r are denoted by  <dig>   <dig> and  <dig>  respectively.
for the npv and odv methods, the best weight and subspace combination was found by 5-fold cross-validation on the jaspar tfbss, while flanking genomic sequences of the tfbss were the sources of negative binding sites.
to assess the  <dig> compared methods, we considered the part of a roc curve where fpr is at most  <dig>  and calculated the auc scaled to between  <dig> and  <dig>  this is nearly equivalent to allowing at most  <dig> false positive hits per promoter on average.
as a peak spans about  <dig> bases, it is considered recalled when it fully contains a predicted binding site.
similarly, a predicted binding site must be fully covered by a peak to be a true positive hit.
in table
<dig>  we observe that odv, npv, ulpb and pssm produced the best auc on  <dig>   <dig>   <dig> and  <dig> out of  <dig> tests, respectively.
statistical tests showed that odv significantly outperformed the other  <dig> methods , npv significantly outperformed ulpb and pssm , and ulpb and pssm are comparable .
we notice that both npv and odv performed worse than the other two methods on mef2a.
as npv and odv both sample negative examples from flanking sequences of tfbss, we suspect that this is one example where the flanking sequences do not represent well the entire promoters.
odv performed consistently across tests corresponding to the same jaspar id such as the three for ctcf.
examining the best weight and subspace, we can see that the subspace agrees on  <dig> out of  <dig> tf models, while the weight agrees on only  <dig> of them.
the latter may be because odv optimizes the β vector and hence is less sensitive to the weight used to embed an l -mer.
CONCLUSIONS
in this work, we proposed to search for transcription factor binding sites in vector spaces.
the novel npv and odv methods were introduced to construct a query vector to search for binding sites of a tf.
we compared our methods to a state-of-the-art method, the ulpb method, and the widely-used pssm method.
cross-validation experiments revealed that the npv and odv methods significantly outperformed the ulpb and pssm methods on prokaryotic as well as eukaryotic tf binding sties.
independent validation on human chip-seq data further verified that the npv and odv methods are significantly better than the other compared methods.
one of the advantages of our framework is that it allows one to easily search for binding sites in various subspaces.
hence, one can search in the best subspace for each individual tf since one can hardly find an optimal subspace for all the tfs.
another advantage is that under the proposed framework one can readily identify motif subtypes for a tf.
hence, to exploit this advantage, we introduced the k npv and k odv methods, immediate variants of the npv and odv methods.
we demonstrated that, consistent with results in previous studies, k npv  significantly improved npv  on the two data sets.
our future work aims for extending our proposed methods to handling known binding sites of variable lengths.
we will seek to approach this problem without resorting to multiple sequence alignment, which is notoriously time-consuming.
in the meantime, we will also seek to identify additional promising subspaces to search for tf binding sites in.
competing interests
both authors declared that they have no competing interests.
author’s contributions
cl and ch conceived the study.
cl collected the data, carried out the experiments and drafted the manuscript.
ch guided the study and revised the manuscript.
both authors read and approved the final manuscript.
supplementary material
additional file 1
detailed notation.
click here for file
acknowledgements
this work was supported in part by national science foundation .

 transcription of genes followed by translation of their transcripts into proteins determines the type and functions of a cell. expression of certain genes even initiates or suppresses differentiation of stem cells. it is therefore crucial to understand the mechanisms of transcriptional regulation. among them, transcription factor binding is the one that has been given considerable attention by computational biologists for the past decade and is still being actively researched. a tf is a protein or protein complex that regulates transcription of one or more genes by binding to the double-stranded dna. a first step in computational identification of target genes regulated by a tf is to pinpoint its binding sites in the genome. once the binding sites are found, the putative target genes can be searched and located in flanking regions of the binding sites. in general, there are two approaches to computational transcription factor binding site identification, motif discovery and tfbs search. the former assumes that a set of sequences is given and each of the sequences may or may not contain tfbss. an algorithm then predicts the locations and lengths of tfbss. the term motif refers to the pattern that are shared by the discovered tfbss. these algorithms rely on no prior knowledge of the motif and hence are known as de novo motif discovery algorithms. the latter assumes that, in addition to a set of sequences, the locations and lengths of tfbss are known. an algorithm then learns from these examples and predicts tfbss in new sequences. such algorithms are also called supervised learning algorithms since they are guided by the given sequences with known tfbss. plenty of efforts have been devoted to the de novo motif discovery problem. comprehensive evaluation and comparison of the developed tools have been performed. in this study, we focus on the problem of tfbs search. we refer readers interested in the motif discovery problem to the evaluation and review articles and references therein. a typical tfbs search method searches for the binding sites of a particular transcription factor in the following manner. it scans a target dna sequence and compare each length l sub-sequence to the binding site profile of the tf, where l is the length of a binding site. each of the l -mer is scored when comparing to the profile. a cut-off score is then set by the method to select candidate tf binding sites. the position-specific scoring matrix is a widely used profile representation, where the binding sites of a tf are encoded as a × l matrix. column i of the matrix stores the scores of matching the ith letter in an l -mer to nucleotides a, c, g and t, respectively. depending on the method of choice, the score of a at position i can be the count of a at position i in the known tfbss, the log-transformed probability of observing a at position i, or any other reasonable number. once computed, the scoring matrix of a tf can be stored in a database. these matrices are used by tools to scan sequences for tfbss. one assumption the pssm representation makes is that positions in a binding site are independent, which is often not the case. osada et al. exploited dependence between positions by considering nucleotide pairs in scoring methods. it was shown that incorporating nucleotide pairs significantly improved the performance of a method, meaning that most transcription factors studied demonstrated correlation between positions in a binding site. this result was reinforced in a recent study, in which the authors showed correlations between two nucleotides within a binding site by plotting the mutual information matrix. a novel scoring method called the ungapped likelihood under positional background method was proposed in this study. the ulpb method models a tfbs by two first-order markov chains and scores a candidate binding site by likelihood ratio produced by the two markov chains. leave-one-out cross-validation results on tfs with or more binding sites showed that ulpb is superior to the methods compared in their work. in this work, we approach the tfbs search problem from a different perspective. we propose to search for binding sites in vector spaces. specifically, l -mers are placed in the euclidean space such that each l -mer corresponds to a vector in the space. with known binding sites of a tf, we construct a profile vector for the tf. this profile vector can then be used as a query vector to search for the unknown binding sites in the space given a similarity measure between two vectors. the vector space model has long been used in information retrieval. under this model, each document in a collection is embedded in a t -dimensional space. that is, each document is represented by a t -element vector, where t is the number of distinct terms present in the document collection or corpus. to search for documents on a particular topic, a query composed of terms relevant to the topic is constructed. the query can be similarly embedded in the t -dimensional space. similarity between the query and a document can then be measured by measuring the similarity between the two corresponding vectors. in the tfbs search problem, the entire genome or the collection of promoter region sequences corresponds to the corpus, whereas an l -mer is analogous to a document in ir. on the other hand, a tf is analogous to a topic, while a tf representation is the analog of a query for the topic. in this framework, we propose two novel approaches to constructing a query vector for a tf of interests. we compare the proposed methods to a state-of-the-art method, the ulpb method, as well as the widely-used pssm method. performance of a method is assessed by cross-validation experiments on two data sets collected from regulondb and jaspar, respectively. independent validation on human chip-seq data gives further insights into the proposed methods. finally, we discuss the advantages of searching for tf binding sites in the proposed framework. the paper is organized as follows. in methods, we present the novel negative-to-positive vector and optimal discriminating vector methods, in addition to introducing the existing methods compared in this work. cross-validation results on prokaryotic and eukaryotic transcription factors are presented and discussed in results and discussion. finally, we give the concluding remarks in conclusions. methods data sets to understand the compared methods in this work, we experimented on prokaryotic as well as eukaryotic transcription factors. the known prokaryotic tf binding sites were collected from from regulondb release. considered in, this data source contains binding sites of tfs in the e. coli k- genome. we considered a data set of tfs with or more known binding sites. the filtering criterion ensures that, for each tf, we have enough examples to learn from. similar filtering criteria were used in. this data set is summarized in table the known eukaryotic tf binding sites were collected from jaspar core database. tfs of homo sapiens and mus musculus were filtered by two criteria. a tf was kept only if it has at least known binding sites and the length of its binding sites is at least nucleotides. the length criterion, arbitrarily chosen, ensures a tf under consideration is specific enough. this data set is summarized in table notation for clarity, we list and define functions and variables used throughout this paper. please see additional file for more details. • fi denotes the probability of observing letter u at position i of a tfbs, where u ∈{a, c, g, t}. • fi,j denotes the probability of observing letters u and v at positions i and j, respectively, where i <j and u,v ∈{a, c, g, t}. • fi denotes the position-specific conditional probability of observing v at position i + given u has been seen at position i, where u,v ∈{a, c, g, t}. • f denotes the background conditional probability of observing v given u has been observed at the previous position, where u,v ∈{a, c, g, t}. • iu is the indicator function given by iu=1ifv=u,0otherwise, where u,v ∈{a, c, g, t}. • iu1u is similarly defined as follows: iu1u2=1ifv1=u1andv2=u otherwise, where u u v v2∈{a, c, g, t}. • ici denotes the information content at position i of a binding site. information content is closely related to entropy, a measure of uncertainty in information theory. the entropy at position i is given by ei=−∑u∈{a, c, g, t}filog2fi. when fi= for all u ∈{a, c, g, t}, ei attains the maximal entropy of and we are most uncertain about the letter at position i. ici is simply defined as ici=2−ei=2+∑u∈{a, c, g, t}filog2fi. • ici,j denotes the information content of the position pair of a binding site. similarly, ici,j=4+∑u,v∈{a, c, g, t}fi,jlog2fi,j, where the maximal entropy of is attained when fi,j= for all u,v ∈{a, c, g, t}. embedding short sequences in vector spaces we describe how a short sequence of l nucleotides or an l -mer is placed in a vector space. let s be an l -mer and si denote its ith nucleotide. each nucleotide in s is converted to variables, that is, si is converted to wiia,wiic,wiigandwiit for i =,…,l. hence, s is converted to 4l variables, placing s in r4l. figure illustrates the conversion of each nucleotide in an l -mer to variables when wi = for i =,…,l. we further consider nucleotide pair, where i < j. only pairs in close proximity are considered in this study. we consider only if j −i = or i.e., a pair of nucleotides is considered only if they are adjacent or separated by one nucleotide. nucleotide pair is similarly converted to variables, wi,jiaa,wi,jiac,…,wi,jitt, as there are possible nucleotide pairs, {aa, ac,…,tt}. we use 32l − additional variables to encode the pairs since there are l − adjacent pairs and l − pairs separated by one nucleotide. consequently, considering individual nucleotides and nucleotide pairs, each l -mer is converted to a -element vector. in this study, we consider two choices of wi’s and wi,j’s. for the first choice, all the nucleotides and nucleotide pairs are given the same weight, i.e., wi = and wi,j = for all i and j. the second one assigns weight to the ith nucleotide according to the information content at position i. similarly, it assigns weight to pair i,j) according to the information content at this pair of positions. specifically, wi=ici and wi,j=ici,j for all i and j. searching for tfbss in vector spaces given a query vector t in space, we score an l -mer s as follows: score=stt, where s denote the corresponding vector of s. in other words, the score of s is obtained by taking the dot-product between s and t. it can be seen that score measures the similarity between s and t. assuming that t corresponds to an l -mer t, score counts the number of nucleotides and nucleotide pairs shared between s and t when wi = and wi,j = for all i and j. however, we note that t can be any vector in the space and does not necessarily correspond to an l -mer. as described above, an l -mer is converted to a -element vector. hence, we use t to search for binding sites in r. our approach offers great flexibility in that it easily allows searching for binding sites in a lower dimensional subspace. by setting all but the first 4l elements in t to zero, we are essentially searching for binding sites in r4l. in this work, we exploit this advantage and simultaneously search for transcription factor binding sites in three subspaces. two of them are r4l and r. the third one is r. this subspace is obtained from considering only the first nucleotide and the l − adjacent nucleotide pairs as in a first order markov chain. the npv method we first introduce a simple approach to constructing a query vector. let p be the set of n+ binding sites and n be the set of n−non-binding sites of a particular transcription factor. we embed all the l -mers in p and n in r. we then find the mean binding site vector μ+=1n+∑s∈ps as well as the mean non-binding site vector μ−=1n−∑s∈ns. the query vector t is found by subtracting μ−from μ+, that is, t = μ+−μ−. the query vector t can be seen as the vector pointing from the center of the non-binding site vectors to the center of the binding site vectors. hence, we call it the negative-to-positive vector method. figure illustrates the idea. the score of an l -mer s given by the npv method is therefore score=st=stμ+−stμ−. we can see that it computes the similarity between s and the mean binding site vector as well as the similarity between s and the mean non-binding site vector. it then scores s by the difference of the two similarity scores. the more similar s is to the mean binding site vector, the higher the score. the less similar s is to the mean non-binding site vector, the higher the score. from the perspective of geometry, we note that score in is proportional to score/||t||, where ||t|| is the length of the query vector t. moreover, by virtue of the equality stt=||s||||t||cosθ, we know score/||t|| equals the orthogonal projection of s onto t, where θ is the angle formed by vectors s and t. the computation of score is therefore equivalent to computation of the orthogonal projection of s onto t. similarly, the computation of score in is equivalent to computation of the orthogonal projection of s onto μ+−μ−. in figure we observe that vector μ+−μ−is pointing to the left and, projected onto this vector, most of the binding sites are on the left of the non-binding sites. this implies that most of the binding sites have a higher score than the non-binding sites. score/||t||∝score. the odv method we have described the npv method, which offers a heuristic way of constructing a query vector. we now introduce a way of finding an optimal query vector β∈r. suppose that |p |=n+ and |n |=n−, that is, there are n+ binding sites and n− non-binding sites for a particular tf. let p ={s,s,…,s} and n={s,s,…,s}, where s denotes the ithl -mer in the union of the two sets and n =n+ + n−. we find the optimal βby solving the following minimization problem: minβ,b,ξ12||β||2+cn+∑i=1n+ξi+cn−∑i=n++1nξi subject toscore)||β||≥b+1−ξi||β||fors∈p, score)||β||≤b−1+ξi||β||fors∈n, ξi≥0∀i. the constraint in ensures that the projection of a tfbs s onto the vector β, score)||β||, exceeds the threshold b+1||β||. on the other hand, the constraint in ensures that the projection of a non-tfbs s onto β stays below the threshold b−1||β||. flexibility is given to the thresholds by introducing ξi’s with cost captured by the last two terms in. finally, to clearly distinguish tfbss from non-tfbss, the squared difference between the two thresholds is made as large as possible. this amounts to maximizing 2||β|| or, equivalently, minimizing 12||β|| which is the first term in. we call this approach the optimal discriminating vector method. the optimization problem in is known as a quadratic programming problem with linear inequality constraints specified in, and. there are p + n + variables and 2n constraints, where p =36l − is the dimension of β. we can see that and specify n constraints whereas imposes n constraints on the variables. quadratic programming is well-studied and hence general solvers are available, e.g., the openopt framework. to solve this problem, the parameter c is first arbitrarily chosen. a solver then searches for values of β=t, b and ξ=t such that the objective function in is minimized while the constraints in, and are satisfied simultaneously. it can be seen that an optimal solution to always exists since the search space of {βbξ} is never empty. to find a feasible solution, one can arbitrarily pick β≠0∈rp and b ∈r. for s∈p, one can pick ξi∈r such that the constraint in is satisfied. similarly, for s∈n, one can pick ξi∈r such that the constraint in is met. we can then compute the value of the objective function as the values of all the variables are known. one way to choose the parameter c in is to search for c in a range by cross-validation. the parameter is tf-dependent in general, but experiments showed that a small c =2− will usually suffice and hence we set c =2−6for all the odv experiments in this study. the pssm and ulpb methods we briefly describe the ungapped likelihood under positional background method proposed in and the position-specific scoring matrix method compared therein. we refer readers to section notation for functions and variables used here. consider a specific tf with binding sites of length l. the pssm method scores an l -mer s by ∑i=1llogfi, where si denotes the ith letter in s. we note that usually the ratio fi/f is used in place of fi, where f is the background probability of si. the simpler form in was compared in and hence it serves as a baseline method in this study. the ulpb models a tfbs by a first-order markov chain and models the background by another first-order markov chain. the background transition probabilities are estimated using the entire genome of a species and hence the ulpb method uses negative examples implicitly. it scores an l -mer s by logf1+∑i=1l−1logfif. although ulpb does not consider background probability in the first term of, the score is approximately the log-likelihood ratio of the two markov chains. the main difference between the pssm method and the npv, odv and ulpb methods is that the pssm method does not score nucleotide pairs nor does it utilize a background distribution. the npv and odv methods explicitly take advantage of negative binding sites, while the ulpb method does it implicitly by using a background distribution. the flexibility of the proposed framework allows the npv and odv methods to easily search in subspaces, further distinguishing the pssm and ulpb methods from the proposed ones.  performance assessment and evaluation metrics the performance of a tfbs search method is evaluated by ν -fold cross-validation. consider a tf with n+ tfbss of length l with flanking regions on both sides. a set of negative examples, ntest, called the test negatives is constructed from the tfbss of the other tfs with filtering as in. another set of negative examples, ntrain, called the training negatives is collected from sequences embedding the n+binding sites. it is comprised of all the l -mers except for the tfbss and two neighboring l -mers of each tfbs. the n+ tfbss are first divided into ν sets, each of which contains ⌊n+ν⌋ or ⌊n+ν⌋ + tfbss. at each iteration of ν -fold cv, one of the ν tfbs sets called the test tfbs setptestis left out. the rest of the tfbss are therefore called the training tfbss. a scoring function is obtained using the training tfbss and non-tfbss randomly sampled from the training negatives, where the ratio of numbers of non-tfbss to tfbss is set to the test tfbss in ptest along with the non-tfbss in ntestare then scored by the scoring function. to score a test sequence, both the forward and reverse strands are scored and, in case the test sequence is longer or shorter than l, the l -mer producing the highest score is used. for each test tfbs t ∈ptest, we find its rank relative to all the non-tfbss in ntest. formally, the rank of t equals + |{s ∈ ntest|score ≥ score}|. after the ν -fold cv, we end up with n+ ranks, each of which corresponds to a tfbs. to allow comparison of methods, we use the area under the roc curve to gauge the performance of a method on the tf. the roc curve is a plot of true positive rate against false positive rate, displaying the trade-off between tpr and fpr. we refer readers to for an introduction to this metric. in this study, ν = for all the cv experiments. for the npv and odv methods, the best weight and subspace combination is obtained at each iteration of the ν -fold cv. specifically, another -fold cv is performed on the ν − sets of tfbss to search for the best combination. prokaryotic transcription factor binding sites to understand the behavior of search methods on prokaryotic tf binding sites, we conducted 10-fold cross-validation experiments on the 26-tf regulondb data set. the proposed npv and odv methods were compared to the ulpb method. the pssm method, considered in, was also included for comparison since it served as a simple baseline method. figure 4a shows the plot of area under the roc curve across the tfs for each method. we can see that the odv method has the best auc on out of tfs and the npv method has the best auc on out of tfs whereas the ulpb and pssm methods have the best auc on and tfs, respectively. to gauge the relative performance between two methods, statistical tests were performed on all the pairs of methods. figure 4b shows the p -values of the pair-wise comparisons. we first notice that, consistent with the results in, ulpb outperformed pssm with a slightly larger p -value of than the usual significance cut-off. as seen in figure 4b, the npv and odv methods are significantly better than the pssm and ulpb methods. we can see that the odv method benefited from optimization albeit minimizing the objective function in does not guarantee maximization of the auc. eukaryotic transcription factor binding sites here we compare the proposed npv and odv methods to the ulpb and pssm methods on eukaryotic tf binding sites. as in the previous section, we conducted 10-fold cross-validation experiments on the 28-tf jaspar data set. figure 5a shows the plot of auc across the tfs for each method. we can see that both the odv and npv methods have the best auc on out of tfs while the ulpb and pssm methods have the best auc on and tfs, respectively. all the methods have the best auc of on ma and ma while the odv, npv and pssm methods have the best auc of on ma. similarly, statistical tests were performed on all the pairs of methods. figure 5b shows that the npv and odv methods are significantly better than the pssm and ulpb methods. ulpb is significantly better than pssm, which is again consistent with the results reported in. overall, performance of the four methods remain unchanged as we shift from prokaryotic transcription factors to eukaryotic ones. this implies that a tfbs search method effective on prokaryotic transcription factors will perform equally well on eukaryotic transcription factors and vice versa. motif subtype identification in vector spaces it has been shown that the binding sites of a tf can be better represented by motif subtypes than by a single motif. in search for new binding sites, two position-specific scoring matrices are used to score an l -mer and the higher score of the two is assigned to this l -mer. searching with two pssms was shown to be superior to searching with a single pssm by cross-species conservation statistics in these studies. we demonstrate that motif subtypes can be readily identified once we embed l -mers in a vector space. the purpose here, however, is not to compare motif subtype identification algorithms. we adopted a slightly different approach to motif subtype identification from those in previous work, while the idea is similar. as usual, all the l -mers were first embedded in a vector space. the known binding sites of a tf were clustered into two subtypes by the k -means algorithm. immediately, we have a variant of the npv method called the k npv method, where k = denotes the number of motif subtypes. the k npv method first computes the mean vectors of these two subtypes, μ+ and μ+ and scores an l -mer s by score=maxstμ+1−μ−,stμ+2−μ−, where μ− is the mean vector of the non-binding sites. figure illustrates the k npv method. similarly, the k odv method scores an l -mer s by score=maxstβ+1/||β+1||,stβ+2/||β+2||, where β+ i is obtained using tfbss in cluster i, i =. unlike the k npv method, the lengths of β+ i’s may be very different and hence β+ i’s are scaled to unit vectors so as not to bias the scoring function. we note that the choice of k = came from previous studies. generally, k can be greater than or even automatically selected. this however is beyond the scope of this study and may be investigated in the future. we assessed the k npv and k odv methods by 10-fold cross-validation on both the regulondb and jaspar data sets. figure shows the results in terms of auc. we observe in figure 7a that overall introducing motif subtypes into the npv and odv methods improves the search performance. results in figure 7b also support this observation. the k npv and k odv are comparable on both the regulondb and jaspar data sets. these results are consistent with those reported in. independent validation on chip-seq data to evaluate the proposed npv and odv methods on the whole genome scale, we built tf models using tfbss in the jaspar database to scan all the human 1000-base promoter sequences obtained from the ucsc genome browser database. chip-seq peaks from the encode project were also retrieved. specifically, the wgencoderegtfbsclusteredv table of build hg was obtained. we checked tfs in table against the annotations and found jaspar tfs, recognized by antibodies present in the encode annotations. the mapping is listed in the first columns of table subspaces r4l, r and r are denoted by and respectively. for the npv and odv methods, the best weight and subspace combination was found by 5-fold cross-validation on the jaspar tfbss, while flanking genomic sequences of the tfbss were the sources of negative binding sites. to assess the compared methods, we considered the part of a roc curve where fpr is at most and calculated the auc scaled to between and this is nearly equivalent to allowing at most false positive hits per promoter on average. as a peak spans about bases, it is considered recalled when it fully contains a predicted binding site. similarly, a predicted binding site must be fully covered by a peak to be a true positive hit. in table we observe that odv, npv, ulpb and pssm produced the best auc on and out of tests, respectively. statistical tests showed that odv significantly outperformed the other methods, npv significantly outperformed ulpb and pssm, and ulpb and pssm are comparable. we notice that both npv and odv performed worse than the other two methods on mef2a. as npv and odv both sample negative examples from flanking sequences of tfbss, we suspect that this is one example where the flanking sequences do not represent well the entire promoters. odv performed consistently across tests corresponding to the same jaspar id such as the three for ctcf. examining the best weight and subspace, we can see that the subspace agrees on out of tf models, while the weight agrees on only of them. the latter may be because odv optimizes the β vector and hence is less sensitive to the weight used to embed an l -mer.  in this work, we proposed to search for transcription factor binding sites in vector spaces. the novel npv and odv methods were introduced to construct a query vector to search for binding sites of a tf. we compared our methods to a state-of-the-art method, the ulpb method, and the widely-used pssm method. cross-validation experiments revealed that the npv and odv methods significantly outperformed the ulpb and pssm methods on prokaryotic as well as eukaryotic tf binding sties. independent validation on human chip-seq data further verified that the npv and odv methods are significantly better than the other compared methods. one of the advantages of our framework is that it allows one to easily search for binding sites in various subspaces. hence, one can search in the best subspace for each individual tf since one can hardly find an optimal subspace for all the tfs. another advantage is that under the proposed framework one can readily identify motif subtypes for a tf. hence, to exploit this advantage, we introduced the k npv and k odv methods, immediate variants of the npv and odv methods. we demonstrated that, consistent with results in previous studies, k npv significantly improved npv on the two data sets. our future work aims for extending our proposed methods to handling known binding sites of variable lengths. we will seek to approach this problem without resorting to multiple sequence alignment, which is notoriously time-consuming. in the meantime, we will also seek to identify additional promising subspaces to search for tf binding sites in. competing interests both authors declared that they have no competing interests. author’s contributions cl and ch conceived the study. cl collected the data, carried out the experiments and drafted the manuscript. ch guided the study and revised the manuscript. both authors read and approved the final manuscript. supplementary material additional file 1 detailed notation. click here for file acknowledgements this work was supported in part by national science foundation.
a number of search methods have been introduced over the years. finally, independent validation on chip-seq data showed that the odv and npv methods significantly outperformed the other compared methods. extensive cross-validation experiments showed that the proposed methods significantly outperformed the ungapped likelihood under positional background method, a state-of-the-art method, and the widely-used position-specific scoring matrix method. we further demonstrated that motif subtypes of a tf can be readily identified in this framework and two variants called the k npv and k odv methods benefited significantly from motif subtype identification. computational approaches to transcription factor binding site identification have been actively researched in the past decade. learning from known binding sites, new binding sites of a transcription factor in unannotated sequences can be identified. however, one can rarely find one single method that performs the best on all the transcription factors. instead, to identify the best method for a particular transcription factor, one usually has to compare a handful of methods. hence, it is highly desirable for a method to perform automatic optimization for individual transcription factors. we proposed to search for transcription factor binding sites in vector spaces. this framework allows us to identify the best method for each individual transcription factor. we further introduced two novel methods, the negative-to-positive vector and optimal discriminating vector methods, to construct query vectors to search for binding sites in vector spaces.
 computational approaches to transcription factor binding site identification have been actively researched in the past decade. learning from known binding sites, new binding sites of a transcription factor in unannotated sequences can be identified. a number of search methods have been introduced over the years. however, one can rarely find one single method that performs the best on all the transcription factors. instead, to identify the best method for a particular transcription factor, one usually has to compare a handful of methods. hence, it is highly desirable for a method to perform automatic optimization for individual transcription factors.  we proposed to search for transcription factor binding sites in vector spaces. this framework allows us to identify the best method for each individual transcription factor. we further introduced two novel methods, the negative-to-positive vector and optimal discriminating vector methods, to construct query vectors to search for binding sites in vector spaces. extensive cross-validation experiments showed that the proposed methods significantly outperformed the ungapped likelihood under positional background method, a state-of-the-art method, and the widely-used position-specific scoring matrix method. we further demonstrated that motif subtypes of a tf can be readily identified in this framework and two variants called the k npv and k odv methods benefited significantly from motif subtype identification. finally, independent validation on chip-seq data showed that the odv and npv methods significantly outperformed the other compared methods.  we conclude that the proposed framework is highly flexible. it enables the two novel methods to automatically identify a tf-specific subspace to search for binding sites. implementations are available as source code at: http://biogrid.engr.uconn.edu/tfbs_search/. 