BACKGROUND
many nuclear proteins perform essential functions through interaction with dna.
for instance, transcription factors activate or repress downstream gene expression by binding to specific dna motifs in promoters  <cit> .
to understand the molecular mechanism of protein-dna recognition, it is important to identify the dna-binding residues in proteins.
the identification is straightforward if the structure of a protein-dna complex is known.
however, it is rather expensive and time-consuming to solve the structure of a protein-dna complex.
currently, only a few hundreds of protein-dna complexes have structural data available in the protein data bank  <cit> .
with the rapid accumulation of sequence data from many genomes, computational methods are needed for accurate prediction of dna-binding residues in protein sequences.
the prediction results can provide useful information for protein functional annotation, protein-dna docking, and experimental studies such as site-directed mutagenesis.
machine learning is particularly appealing for modelling the dna-binding pattern of amino acid residues.
although some experimental observations have been made for dna-binding residues in protein structures, the molecular recognition pattern is still poorly understood  <cit> .
it is thus desired that machine learning methods can be used to model the complex patterns hidden in the available structural data, and the resulting classifier can be applied to reliable identification of dna-binding residues in protein sequences.
the machine learning problem can be formally specified as follows: given the amino acid sequence of a protein that is supposed to interact with dna, the task is to predict which amino acid residues may be located at the interaction interface.
since both the structure of the protein and the sequence of the target dna are assumed to be unknown, it is challenging to predict dna-binding residues from amino acid properties and local sequence patterns.
several machine learning methods have been reported for predicting dna-binding residues in protein sequences.
ahmad et al.
<cit>  analyzed the structural data of representative protein-dna complexes, and used the amino acid sequences in these structures to train artificial neural networks  for dna-binding site prediction.
yan et al.
<cit>  constructed naïve bayes classifiers using the amino acid identities of dna-binding sites and their sequence neighbours.
however, the prediction accuracy was relatively low in these studies  <cit> , probably because amino acid sequences were directly used for classifier construction.
the use of domain-specific knowledge for input encoding has been shown to enhance classifier performance.
ahmad and sarai  <cit>  developed an ann-based method to utilize evolutionary information in terms of position-specific scoring matrices .
the scores in a pssm indicate how well each amino acid position of a sequence is conserved among its homologues.
since functional sites tend to be conserved among homologous proteins, pssms may provide relevant information for predicting dna-binding residues.
it was found that the average of sensitivity and specificity could be increased by up to  <dig> % using pssms when compared with ann predictors using sequence information only  <cit> .
more recently, pssms were also used to train support vector machines  and logistic regression models for accurate prediction of dna-binding residues  <cit> .
in our previous studies  <cit> , ann and svm classifiers were constructed using relevant biochemical features, including the hydrophobicity index, side chain pka value, and molecular mass of an amino acid.
these features were used to represent biological knowledge, which might not be learned from the training data of dna-binding residues.
it was found that classifier performance was significantly improved by the use of biochemical features for input encoding, and the svm classifier outperformed the ann predictor  <cit> .
there are two main objectives of the present study.
the first objective is to improve the prediction accuracy by combining different types of biological knowledge in classifier construction.
although either pssms or biochemical features have been used for input encoding, it is still unknown whether classifier performance can be further improved through a combination of relevant features, including new descriptors of evolutionary information.
one potential problem is that the use of pssms for classifier construction gives rise to a large number of input variables.
a training data instance normally includes multiple neighbouring residues for providing context information, and each residue has  <dig> pssm scores.
considering the relatively small dataset currently available for modelling dna-binding sites, too many input variables may result in model overfitting for most machine learning algorithms.
thus, the second objective is to investigate whether accurate classifiers can be constructed using the random forest  learning algorithm, which has the capability to handle a large number of input variables and avoid model overfitting  <cit> .
the results obtained in this study indicate that dna-binding site prediction can be significantly improved by using the rf-based approach with biochemical features and several new descriptors of evolutionary information for input encoding.
methods
data preparation
this study used two amino acid sequence datasets, pdna- <dig> and pdc25t, which were extracted from the structural data of protein-dna complexes available at the protein data bank .
the pdna- <dig> dataset was used classifier construction in this work as well as several previous studies  <cit> .
the amino acid sequences in pdna- <dig> were derived from  <dig> structures of representative protein-dna complexes, and the dataset had less than 25% identity among the sequences.
the pdc25t dataset was derived from the protein-dna complexes that were not included in pdna- <dig>  the sequences in pdc25t had less than 25% identity among them as well as with the sequences in pdna- <dig>  in this study, pdc25t was used as a separate test dataset for classifier performance evaluation and comparison.
as in our previous studies  <cit> , an amino acid residue was designated as a binding site if the side chain or backbone atoms of the residue fell within a cutoff distance of  <dig>  Å from any atoms of the dna molecule in the complex.
all the other residues were regarded as non-binding sites.
both pdna- <dig> and pdc25t are imbalanced datasets with ~15% residues labelled as dna-binding and ~85% residues being non-binding.
training strategies
classifiers were trained using residue-wise data instances derived from the sequence dataset .
each data instance had eleven consecutive residues, and the target residue was positioned in the middle of the subsequence.
a data instance was labelled as positive if the target residue was dna-binding, or negative if the target residue was non-binding.
the context information provided by the five neighbouring residues on each side of the target residue was previously shown to be optimal for sequence-based prediction of dna-binding residues  <cit> .
in classifier construction, the input vector was generated by encoding each residue with three biochemical features and several descriptors of evolutionary information .
in our previous studies  <cit> , the three biochemical features, including the hydrophobicity index , side chain pka value , and molecular mass  of an amino acid, were shown to be relevant for dna-binding site prediction.
evolutionary information extraction
for dna-binding site prediction, the labelled datasets derived from the available structures are relatively small in size.
however, there are abundant unlabeled sequence data in public databases such as uniprot  <cit> .
the unlabeled data contain evolutionary information about the conservation of each sequence position.
because dna-binding residues tend to be conserved among homologous proteins  <cit> , evolutionary information can be used to enhance classifier performance.
the procedure for extracting evolutionary information from sequence alignments is outlined in figure  <dig>  for a given protein sequence p, its homologues in a reference database can be retrieved and aligned to p using the psi-blast program  <cit> .
the sequence alignment is then used to compute evolutionary conservation scores for each residue in p. in this study, the protein sequence dataset uniprotkb  was used as the reference database, and psi-blast was run for three iterations with the e-value threshold set to 1e- <dig>  the following descriptors of evolutionary information have been investigated for dna-binding site prediction:
blast-based conservation score : let hp = {h <dig>  h <dig> ..., hn} be the set of n hits  in the psi-blast search for a query sequence p. each hit is a pair-wise sequence alignment, in which psi-blast indicates whether two aligned residues are identical or show similarity based on the blosum <dig> scoring matrix  <cit> .
the b score for the residue ai at position i in p is computed as follows:
where f  is set to  <dig> if ai is aligned to an identical or similar residue in hj, or  <dig> otherwise, and c is a pseudo-count .
the term  is used to scale the feature value, and it becomes smaller when n gets larger.
if p has no hit in the database , the feature value is set to  <dig>  the b score was used to construct artificial neural network classifiers in our previous study  <cit> .
mean and standard deviation of biochemical feature values: for each residue ai in the sequence p, the mean () and standard deviation  of a biochemical feature x, x ∈ {h, k, m}, are calculated as follows:
where χ is the value of feature x for the amino acid residue in hj, which is aligned to ai at position i in p. the mean of feature x, also referred to as hm, km or mm in this paper, captures the biochemical properties of an amino acid position in the sequence alignment.
it has been shown that basic and polar amino acids are overrepresented while acidic and hydrophobic amino acids are underrepresented in the population of dna-binding sites  <cit> .
the standard deviation of feature x, also called hd, kd or md, reveals how well the biochemical properties of an amino acid position are conserved in the aligned homologous sequences.
position-specific scoring matrix : the pssm scores are generated by psi-blast  <cit> , and there are  <dig> values for each sequence position.
the evolutionary information captured by pssms was previously shown to improve the performance of artificial neural networks and support vector machines for dna-binding site prediction  <cit> .
however, pssm is rather designed for blast searches, and it may not capture all the evolutionary information for modelling dna-binding sites.
random forests
the use of evolutionary information for classifier construction results in a large number of input variables.
in particular, since pssm has  <dig> scores for each sequence position, it gives rise to  <dig> inputs for a data instance with eleven residues.
considering the relatively small size of the training dataset, too many inputs may result in model overfitting.
in this study, we used the random forest learning algorithm, which was shown to have the capability of handling a large number of input variables and avoiding model overfitting  <cit> .
random forests  use a combination of independent decision trees to improve classifier performance.
specifically, each decision tree in a forest is constructed using a bootstrap sample from the training data.
during tree construction, m variables out of all the n input variables  are randomly selected at each node, and the tree node is split using the selected m variables.
because of the random feature selection, rfs can handle a large number of input variables and avoid overfitting.
for classifying a data instance, a rf classifier combines the votes made by the decision trees, and gives the most popular class as the output of the ensemble.
it has been shown that rfs outperform adaboost ensembles on noisy datasets, and can work well on data with many weak inputs  <cit> .
these characteristics of rfs are appealing since the dna-binding data appear to be noisy and contain many weak sequence-derived features.
in this study, we used the software package available at  construct rf classifiers with the default parameter settings.
in particular, the number of variables selected to split each node  was set to the floor of square root of the total number of input variables.
other values of m were also tested, but did not result in significant improvement of classifier performance for dna-binding site prediction.
classifier evaluation
we performed fivefold cross-validation experiments using the pdna- <dig> dataset for the initial estimation of classifier performance.
the trained classifier was further evaluated using the pdc25t dataset.
the following performance measures were used in this study:
where tp is the number of true positives ; tn is the number of true negatives ; fp is the number of false positives ; and fn is the number of false negatives .
since the datasets used in this study are imbalanced, the overall accuracy alone could be misleading.
for instance, a classifier could achieve ~85% accuracy by simply predicting all the residues as negatives.
thus, both sensitivity and specificity are also computed from prediction results.
furthermore, the average of sensitivity and specificity, referred to as strength in this paper, may provide a fair measure of classifier performance as shown in previous studies  <cit> .
the receiver operating characteristic  curve is probably the most robust approach for classifier evaluation and comparison  <cit> .
the roc curve is drawn by plotting the true positive rate  against the false positive rate, which equals to .
in this work, the roc curve has been generated by using different threshold values for the output of a classifier and plotting the true positive rate against false positive rate for each threshold value.
the area under the roc curve  can be used as a reliable measure of classifier performance  <cit> .
since the roc plot is a unit square, the maximum value of auc is  <dig>  which is achieved by a perfect classifier.
weak classifiers and random guessing have auc values close to  <dig> .
RESULTS
random forests for sequence-based prediction of dna-binding residues
as the first step to develop the new approach for dna-binding site prediction, random forests  were trained with three biochemical features that were used to construct ann and svm predictors in our previous studies  <cit> .
the biochemical features, including the hydrophobicity index , side chain pka value  and molecular mass  of an amino acid, were shown to provide relevant information for predicting dna-binding residues  <cit> .
the input vector contained  <dig> feature values because each data instance was a subsequence of eleven consecutive residues with the target residue in the middle position .
the context information provided by the ten neighbouring residues was found to be optimal for dna-binding site prediction  <cit> .
as shown in table  <dig>  the rf classifier constructed without evolutionary information achieved  <dig> % overall accuracy with  <dig> % sensitivity and  <dig> % specificity in fivefold cross-validation experiments on the pdna- <dig> dataset.
since the dataset was imbalanced with only 15% of the amino acid residues as dna-binding sites, the performance of the rf classifier was also measured by the average of sensitivity and specificity , and the area under the receiver operating characteristic curve .
different training parameters were tested for constructing the rf classifier, and the above performance measures were obtained with  <dig> decision trees in the forest and m =  <dig> .
the results suggest that, with the three biochemical features, the rf classifier is slightly more accurate than the ann and svm predictors  <cit> .
by using the same dataset , the ann and svm predictors achieved the prediction strength of  <dig> % and  <dig> %, respectively.
the roc auc of the ann and svm predictors is also less than that of the rf classifier.
however, rfs have the major advantage in handling a large number of input variables should various descriptors of evolutionary information be used for input encoding.
improved classifier performance by using evolutionary information
three types of evolutionary information, including the blast-based conservation score, position-specific scoring matrices , and the means and standard deviations of biochemical feature values, have been examined for their effect on classifier performance.
the conservation score  was previously used to train anns for dna-binding site prediction  <cit> .
as shown in table  <dig>  the prediction strength and roc auc are slightly improved by adding the b score to the three biochemical features, suggesting that the conservation score does not capture all the evolutionary information for sequence-based prediction of dna-binding residues.
however, rf classifier performance is significantly improved by using the pssm descriptor of evolutionary information.
pssms were derived from the psi-blast search against the uniprotkb database as described in methods.
because each residue was encoded with  <dig> pssm scores and  <dig> biochemical features, the input vector contained  <dig> values for a data instance with eleven residues.
as shown in table  <dig>  the use of pssm for input encoding improved the prediction strength to  <dig> %.
the classifier also had higher roc auc  than the rf classifier constructed using the three biochemical features alone .
the results were obtained with  <dig> decision trees in the forest and the training parameter m set to  <dig>  other parameter settings were also tested, but did not give rise to better classifier performance.
the means  and standard deviations  of the three biochemical features represent new descriptors of evolutionary information, which indicate how well the biochemical properties of an amino acid position are conserved in the sequence alignment from the psi-blast search.
it was found that the use of hm, km, hd, and kd in classifier construction improved the prediction strength to  <dig> % with auc =  <dig>  .
the rf classifier was constructed using  <dig> decision trees and m =  <dig>  however, adding mm and md to the input vector did not result in further improvement of classifier performance .
interestingly, the most accurate classifier was obtained with a combination of pssm, hm, hd, km and kd in addition to the three biochemical features for input encoding.
since the input vector had  <dig> variables , the training parameter m was set to  <dig> for the forest with  <dig> decision trees.
as shown in table  <dig>  the resulting classifier achieved the overall accuracy of  <dig> % with  <dig> % sensitivity and  <dig> % specificity.
the prediction strength reached  <dig> %, representing an increase of  <dig> % when compared with the performance achieved without evolutionary information .
this rf also had the highest level of roc auc  among all the classifiers .
the significant improvement of classifier performance by using evolutionary information has further been demonstrated in the roc analysis .
the roc curves have been generated by varying the output threshold of rf classifiers, and each point on a roc curve represents a trade-off between sensitivity and specificity.
for classifier performance comparison, the roc curve of a more accurate classifier is closer to the left-hand and top borders of the plot.
as shown in figure  <dig>  the rf classifier trained with the two types of evolutionary information  is clearly better than the classifier constructed using only biochemical features .
comparison of classifier performance using a separate test dataset
to further demonstrate the improved prediction of dna-binding residues, the most accurate rf  has been compared with the previous classifiers  using a separate test dataset, pdc25t.
bindn uses the svm classifier constructed using the three biochemical features  in our previous study  <cit> .
the dp-bind web server  provides pssm-based svm and kernel logistic regression predictors for dna-binding site prediction  <cit> .
dbs-pssm  is the ann predictor trained with pssm and sequence information  <cit> .
all the above classifiers have been constructed using the same training dataset, pdna- <dig>  which shares less than 25% sequence identity with the pdc25t dataset.
as shown in table  <dig>  bindn-rf gives the best predictive performance with the prediction strength at  <dig> % and roc auc equal to  <dig> .
importantly, the performance measures achieved by bindn-rf on the separate test dataset  are comparable with those from the fivefold cross-validation , suggesting that over-fitting has been avoided in the construction of the rf classifier.
dp-bind also gives relatively high performance with  <dig> % prediction strength and roc auc =  <dig>  on the pdc25t dataset.
however, the ann predictor trained with pssm and sequence information  shows very low performance on the pdc25t dataset, probably owing to poor generalization of the representative dna-binding residues in the relatively small training dataset .
in figure  <dig>  roc curves have been generated for the four classifiers  based on their predictions made for the pdc25t test dataset.
clearly, the rf classifier  shows the best performance for almost all the trade-offs between sensitivity and specificity.
the results suggest that the rf-based approach developed in this work is better than the previous methods for sequence-based prediction of dna-binding residues.
structural validation of predicted dna-binding residues
to determine whether the prediction results can provide useful information for understanding protein-dna interactions and that the rf-based approach is better than our previous method , the predicted dna-binding residues have been examined in the context of three-dimensional structures.
figure  <dig> shows representative predictions made by bindn-rf and bindn for the  <dig> sequences in the pdc25t test dataset.
the predictions were based solely on amino acid sequence information, and the structural data were used only for visualization of the prediction results.
in figure 4a, dna-binding residues have been predicted using the rf classifier  for the bacterial qacr protein  involved in multidrug binding and transcriptional regulation  <cit> .
significantly,  <dig> of the  <dig> dna-binding residues were correctly predicted, and there were only  <dig> false positive predictions for the  <dig> non-binding residues in each protein subunit.
when the qacr sequence was analyzed using bindn, the false positive rate was very high  although all the  <dig> dna-binding residues were correctly identified .
thus, for experimental studies such as site-directed mutagenesis, the prediction result from bindn does not provide as much useful information as that from bindn-rf.
the bindn-rf web server
to make the accurate rf classifier available to the biological research community, we have developed the bindn-rf web server .
users can enter an amino acid sequence in fasta format, and specify the desired level of sensitivity or specificity for dna-binding site prediction.
for a query sequence, the system performs a three-iteration psi-blast search against the uniprotkb database to extract evolutionary information as described in methods.
the rf classifier constructed in this work is then used to predict dna-binding residues in the query sequence.
the user-defined level of sensitivity or specificity is used to determine the output threshold for the rf classifier according to its roc curve.
thus, users can choose a specificity level higher than the default value  to reduce the number of false positive predictions.
the output report of bindn-rf has been designed to be self-explanatory, and is similar to that of bindn.
a detailed description about the report format can be found in our previous paper  <cit> .
CONCLUSIONS
a random forest-based approach has been described in this paper for predicting dna-binding residues in protein sequences.
since random forests can handle a large number of input variables and avoid model overfitting, accurate classifiers have been constructed by combining biochemical features with several descriptors of evolutionary information for input encoding.
the new descriptors developed in the present work have been shown to enhance classifier performance when they are used together with the biochemical features and position-specific scoring matrices.
thus, the new descriptors capture certain evolutionary information that is not contained in position-specific scoring matrices previously used for dna-binding site prediction.
the best random forest classifier achieved  <dig> % overall accuracy with  <dig> % sensitivity and  <dig> % specificity on a separate test dataset.
predictions at this level of accuracy may provide useful information for protein-dna docking and experimental studies such as site-directed mutagenesis for understanding protein-dna interactions.
the new approach has been implemented in the bindn-rf web server for online prediction of dna-binding residues in protein sequences.
competing interests
the authors declare that they have no competing interests.
authors' contributions
lw initiated the study, conducted the data analysis, and drafted the manuscript.
mqy and jyy participated in result interpretation and manuscript preparation.

 many nuclear proteins perform essential functions through interaction with dna. for instance, transcription factors activate or repress downstream gene expression by binding to specific dna motifs in promoters. to understand the molecular mechanism of protein-dna recognition, it is important to identify the dna-binding residues in proteins. the identification is straightforward if the structure of a protein-dna complex is known. however, it is rather expensive and time-consuming to solve the structure of a protein-dna complex. currently, only a few hundreds of protein-dna complexes have structural data available in the protein data bank. with the rapid accumulation of sequence data from many genomes, computational methods are needed for accurate prediction of dna-binding residues in protein sequences. the prediction results can provide useful information for protein functional annotation, protein-dna docking, and experimental studies such as site-directed mutagenesis. machine learning is particularly appealing for modelling the dna-binding pattern of amino acid residues. although some experimental observations have been made for dna-binding residues in protein structures, the molecular recognition pattern is still poorly understood. it is thus desired that machine learning methods can be used to model the complex patterns hidden in the available structural data, and the resulting classifier can be applied to reliable identification of dna-binding residues in protein sequences. the machine learning problem can be formally specified as follows: given the amino acid sequence of a protein that is supposed to interact with dna, the task is to predict which amino acid residues may be located at the interaction interface. since both the structure of the protein and the sequence of the target dna are assumed to be unknown, it is challenging to predict dna-binding residues from amino acid properties and local sequence patterns. several machine learning methods have been reported for predicting dna-binding residues in protein sequences. ahmad et al. analyzed the structural data of representative protein-dna complexes, and used the amino acid sequences in these structures to train artificial neural networks for dna-binding site prediction. yan et al. constructed naïve bayes classifiers using the amino acid identities of dna-binding sites and their sequence neighbours. however, the prediction accuracy was relatively low in these studies, probably because amino acid sequences were directly used for classifier construction. the use of domain-specific knowledge for input encoding has been shown to enhance classifier performance. ahmad and sarai developed an ann-based method to utilize evolutionary information in terms of position-specific scoring matrices. the scores in a pssm indicate how well each amino acid position of a sequence is conserved among its homologues. since functional sites tend to be conserved among homologous proteins, pssms may provide relevant information for predicting dna-binding residues. it was found that the average of sensitivity and specificity could be increased by up to % using pssms when compared with ann predictors using sequence information only. more recently, pssms were also used to train support vector machines and logistic regression models for accurate prediction of dna-binding residues. in our previous studies, ann and svm classifiers were constructed using relevant biochemical features, including the hydrophobicity index, side chain pka value, and molecular mass of an amino acid. these features were used to represent biological knowledge, which might not be learned from the training data of dna-binding residues. it was found that classifier performance was significantly improved by the use of biochemical features for input encoding, and the svm classifier outperformed the ann predictor. there are two main objectives of the present study. the first objective is to improve the prediction accuracy by combining different types of biological knowledge in classifier construction. although either pssms or biochemical features have been used for input encoding, it is still unknown whether classifier performance can be further improved through a combination of relevant features, including new descriptors of evolutionary information. one potential problem is that the use of pssms for classifier construction gives rise to a large number of input variables. a training data instance normally includes multiple neighbouring residues for providing context information, and each residue has pssm scores. considering the relatively small dataset currently available for modelling dna-binding sites, too many input variables may result in model overfitting for most machine learning algorithms. thus, the second objective is to investigate whether accurate classifiers can be constructed using the random forest learning algorithm, which has the capability to handle a large number of input variables and avoid model overfitting. the results obtained in this study indicate that dna-binding site prediction can be significantly improved by using the rf-based approach with biochemical features and several new descriptors of evolutionary information for input encoding. methods data preparation this study used two amino acid sequence datasets, pdna- and pdc25t, which were extracted from the structural data of protein-dna complexes available at the protein data bank. the pdna- dataset was used classifier construction in this work as well as several previous studies. the amino acid sequences in pdna- were derived from structures of representative protein-dna complexes, and the dataset had less than 25% identity among the sequences. the pdc25t dataset was derived from the protein-dna complexes that were not included in pdna- the sequences in pdc25t had less than 25% identity among them as well as with the sequences in pdna- in this study, pdc25t was used as a separate test dataset for classifier performance evaluation and comparison. as in our previous studies, an amino acid residue was designated as a binding site if the side chain or backbone atoms of the residue fell within a cutoff distance of Å from any atoms of the dna molecule in the complex. all the other residues were regarded as non-binding sites. both pdna- and pdc25t are imbalanced datasets with ~15% residues labelled as dna-binding and ~85% residues being non-binding. training strategies classifiers were trained using residue-wise data instances derived from the sequence dataset. each data instance had eleven consecutive residues, and the target residue was positioned in the middle of the subsequence. a data instance was labelled as positive if the target residue was dna-binding, or negative if the target residue was non-binding. the context information provided by the five neighbouring residues on each side of the target residue was previously shown to be optimal for sequence-based prediction of dna-binding residues. in classifier construction, the input vector was generated by encoding each residue with three biochemical features and several descriptors of evolutionary information. in our previous studies, the three biochemical features, including the hydrophobicity index, side chain pka value, and molecular mass of an amino acid, were shown to be relevant for dna-binding site prediction. evolutionary information extraction for dna-binding site prediction, the labelled datasets derived from the available structures are relatively small in size. however, there are abundant unlabeled sequence data in public databases such as uniprot. the unlabeled data contain evolutionary information about the conservation of each sequence position. because dna-binding residues tend to be conserved among homologous proteins, evolutionary information can be used to enhance classifier performance. the procedure for extracting evolutionary information from sequence alignments is outlined in figure for a given protein sequence p, its homologues in a reference database can be retrieved and aligned to p using the psi-blast program. the sequence alignment is then used to compute evolutionary conservation scores for each residue in p. in this study, the protein sequence dataset uniprotkb was used as the reference database, and psi-blast was run for three iterations with the e-value threshold set to 1e- the following descriptors of evolutionary information have been investigated for dna-binding site prediction: blast-based conservation score: let hp = {h h..., hn} be the set of n hits in the psi-blast search for a query sequence p. each hit is a pair-wise sequence alignment, in which psi-blast indicates whether two aligned residues are identical or show similarity based on the blosum scoring matrix. the b score for the residue ai at position i in p is computed as follows: where f is set to if ai is aligned to an identical or similar residue in hj, or otherwise, and c is a pseudo-count. the term is used to scale the feature value, and it becomes smaller when n gets larger. if p has no hit in the database, the feature value is set to the b score was used to construct artificial neural network classifiers in our previous study. mean and standard deviation of biochemical feature values: for each residue ai in the sequence p, the mean () and standard deviation of a biochemical feature x, x ∈ {h, k, m}, are calculated as follows: where χ is the value of feature x for the amino acid residue in hj, which is aligned to ai at position i in p. the mean of feature x, also referred to as hm, km or mm in this paper, captures the biochemical properties of an amino acid position in the sequence alignment. it has been shown that basic and polar amino acids are overrepresented while acidic and hydrophobic amino acids are underrepresented in the population of dna-binding sites. the standard deviation of feature x, also called hd, kd or md, reveals how well the biochemical properties of an amino acid position are conserved in the aligned homologous sequences. position-specific scoring matrix: the pssm scores are generated by psi-blast, and there are values for each sequence position. the evolutionary information captured by pssms was previously shown to improve the performance of artificial neural networks and support vector machines for dna-binding site prediction. however, pssm is rather designed for blast searches, and it may not capture all the evolutionary information for modelling dna-binding sites. random forests the use of evolutionary information for classifier construction results in a large number of input variables. in particular, since pssm has scores for each sequence position, it gives rise to inputs for a data instance with eleven residues. considering the relatively small size of the training dataset, too many inputs may result in model overfitting. in this study, we used the random forest learning algorithm, which was shown to have the capability of handling a large number of input variables and avoiding model overfitting. random forests use a combination of independent decision trees to improve classifier performance. specifically, each decision tree in a forest is constructed using a bootstrap sample from the training data. during tree construction, m variables out of all the n input variables are randomly selected at each node, and the tree node is split using the selected m variables. because of the random feature selection, rfs can handle a large number of input variables and avoid overfitting. for classifying a data instance, a rf classifier combines the votes made by the decision trees, and gives the most popular class as the output of the ensemble. it has been shown that rfs outperform adaboost ensembles on noisy datasets, and can work well on data with many weak inputs. these characteristics of rfs are appealing since the dna-binding data appear to be noisy and contain many weak sequence-derived features. in this study, we used the software package available at construct rf classifiers with the default parameter settings. in particular, the number of variables selected to split each node was set to the floor of square root of the total number of input variables. other values of m were also tested, but did not result in significant improvement of classifier performance for dna-binding site prediction. classifier evaluation we performed fivefold cross-validation experiments using the pdna- dataset for the initial estimation of classifier performance. the trained classifier was further evaluated using the pdc25t dataset. the following performance measures were used in this study: where tp is the number of true positives; tn is the number of true negatives; fp is the number of false positives; and fn is the number of false negatives. since the datasets used in this study are imbalanced, the overall accuracy alone could be misleading. for instance, a classifier could achieve ~85% accuracy by simply predicting all the residues as negatives. thus, both sensitivity and specificity are also computed from prediction results. furthermore, the average of sensitivity and specificity, referred to as strength in this paper, may provide a fair measure of classifier performance as shown in previous studies. the receiver operating characteristic curve is probably the most robust approach for classifier evaluation and comparison. the roc curve is drawn by plotting the true positive rate against the false positive rate, which equals to. in this work, the roc curve has been generated by using different threshold values for the output of a classifier and plotting the true positive rate against false positive rate for each threshold value. the area under the roc curve can be used as a reliable measure of classifier performance. since the roc plot is a unit square, the maximum value of auc is which is achieved by a perfect classifier. weak classifiers and random guessing have auc values close to.  random forests for sequence-based prediction of dna-binding residues as the first step to develop the new approach for dna-binding site prediction, random forests were trained with three biochemical features that were used to construct ann and svm predictors in our previous studies. the biochemical features, including the hydrophobicity index, side chain pka value and molecular mass of an amino acid, were shown to provide relevant information for predicting dna-binding residues. the input vector contained feature values because each data instance was a subsequence of eleven consecutive residues with the target residue in the middle position. the context information provided by the ten neighbouring residues was found to be optimal for dna-binding site prediction. as shown in table the rf classifier constructed without evolutionary information achieved % overall accuracy with % sensitivity and % specificity in fivefold cross-validation experiments on the pdna- dataset. since the dataset was imbalanced with only 15% of the amino acid residues as dna-binding sites, the performance of the rf classifier was also measured by the average of sensitivity and specificity, and the area under the receiver operating characteristic curve. different training parameters were tested for constructing the rf classifier, and the above performance measures were obtained with decision trees in the forest and m =. the results suggest that, with the three biochemical features, the rf classifier is slightly more accurate than the ann and svm predictors. by using the same dataset, the ann and svm predictors achieved the prediction strength of % and %, respectively. the roc auc of the ann and svm predictors is also less than that of the rf classifier. however, rfs have the major advantage in handling a large number of input variables should various descriptors of evolutionary information be used for input encoding. improved classifier performance by using evolutionary information three types of evolutionary information, including the blast-based conservation score, position-specific scoring matrices, and the means and standard deviations of biochemical feature values, have been examined for their effect on classifier performance. the conservation score was previously used to train anns for dna-binding site prediction. as shown in table the prediction strength and roc auc are slightly improved by adding the b score to the three biochemical features, suggesting that the conservation score does not capture all the evolutionary information for sequence-based prediction of dna-binding residues. however, rf classifier performance is significantly improved by using the pssm descriptor of evolutionary information. pssms were derived from the psi-blast search against the uniprotkb database as described in methods. because each residue was encoded with pssm scores and biochemical features, the input vector contained values for a data instance with eleven residues. as shown in table the use of pssm for input encoding improved the prediction strength to %. the classifier also had higher roc auc than the rf classifier constructed using the three biochemical features alone. the results were obtained with decision trees in the forest and the training parameter m set to other parameter settings were also tested, but did not give rise to better classifier performance. the means and standard deviations of the three biochemical features represent new descriptors of evolutionary information, which indicate how well the biochemical properties of an amino acid position are conserved in the sequence alignment from the psi-blast search. it was found that the use of hm, km, hd, and kd in classifier construction improved the prediction strength to % with auc =. the rf classifier was constructed using decision trees and m = however, adding mm and md to the input vector did not result in further improvement of classifier performance. interestingly, the most accurate classifier was obtained with a combination of pssm, hm, hd, km and kd in addition to the three biochemical features for input encoding. since the input vector had variables, the training parameter m was set to for the forest with decision trees. as shown in table the resulting classifier achieved the overall accuracy of % with % sensitivity and % specificity. the prediction strength reached %, representing an increase of % when compared with the performance achieved without evolutionary information. this rf also had the highest level of roc auc among all the classifiers. the significant improvement of classifier performance by using evolutionary information has further been demonstrated in the roc analysis. the roc curves have been generated by varying the output threshold of rf classifiers, and each point on a roc curve represents a trade-off between sensitivity and specificity. for classifier performance comparison, the roc curve of a more accurate classifier is closer to the left-hand and top borders of the plot. as shown in figure the rf classifier trained with the two types of evolutionary information is clearly better than the classifier constructed using only biochemical features. comparison of classifier performance using a separate test dataset to further demonstrate the improved prediction of dna-binding residues, the most accurate rf has been compared with the previous classifiers using a separate test dataset, pdc25t. bindn uses the svm classifier constructed using the three biochemical features in our previous study. the dp-bind web server provides pssm-based svm and kernel logistic regression predictors for dna-binding site prediction. dbs-pssm is the ann predictor trained with pssm and sequence information. all the above classifiers have been constructed using the same training dataset, pdna- which shares less than 25% sequence identity with the pdc25t dataset. as shown in table bindn-rf gives the best predictive performance with the prediction strength at % and roc auc equal to. importantly, the performance measures achieved by bindn-rf on the separate test dataset are comparable with those from the fivefold cross-validation, suggesting that over-fitting has been avoided in the construction of the rf classifier. dp-bind also gives relatively high performance with % prediction strength and roc auc = on the pdc25t dataset. however, the ann predictor trained with pssm and sequence information shows very low performance on the pdc25t dataset, probably owing to poor generalization of the representative dna-binding residues in the relatively small training dataset. in figure roc curves have been generated for the four classifiers based on their predictions made for the pdc25t test dataset. clearly, the rf classifier shows the best performance for almost all the trade-offs between sensitivity and specificity. the results suggest that the rf-based approach developed in this work is better than the previous methods for sequence-based prediction of dna-binding residues. structural validation of predicted dna-binding residues to determine whether the prediction results can provide useful information for understanding protein-dna interactions and that the rf-based approach is better than our previous method, the predicted dna-binding residues have been examined in the context of three-dimensional structures. figure shows representative predictions made by bindn-rf and bindn for the sequences in the pdc25t test dataset. the predictions were based solely on amino acid sequence information, and the structural data were used only for visualization of the prediction results. in figure 4a, dna-binding residues have been predicted using the rf classifier for the bacterial qacr protein involved in multidrug binding and transcriptional regulation. significantly, of the dna-binding residues were correctly predicted, and there were only false positive predictions for the non-binding residues in each protein subunit. when the qacr sequence was analyzed using bindn, the false positive rate was very high although all the dna-binding residues were correctly identified. thus, for experimental studies such as site-directed mutagenesis, the prediction result from bindn does not provide as much useful information as that from bindn-rf. the bindn-rf web server to make the accurate rf classifier available to the biological research community, we have developed the bindn-rf web server. users can enter an amino acid sequence in fasta format, and specify the desired level of sensitivity or specificity for dna-binding site prediction. for a query sequence, the system performs a three-iteration psi-blast search against the uniprotkb database to extract evolutionary information as described in methods. the rf classifier constructed in this work is then used to predict dna-binding residues in the query sequence. the user-defined level of sensitivity or specificity is used to determine the output threshold for the rf classifier according to its roc curve. thus, users can choose a specificity level higher than the default value to reduce the number of false positive predictions. the output report of bindn-rf has been designed to be self-explanatory, and is similar to that of bindn. a detailed description about the report format can be found in our previous paper.  a random forest-based approach has been described in this paper for predicting dna-binding residues in protein sequences. since random forests can handle a large number of input variables and avoid model overfitting, accurate classifiers have been constructed by combining biochemical features with several descriptors of evolutionary information for input encoding. the new descriptors developed in the present work have been shown to enhance classifier performance when they are used together with the biochemical features and position-specific scoring matrices. thus, the new descriptors capture certain evolutionary information that is not contained in position-specific scoring matrices previously used for dna-binding site prediction. the best random forest classifier achieved % overall accuracy with % sensitivity and % specificity on a separate test dataset. predictions at this level of accuracy may provide useful information for protein-dna docking and experimental studies such as site-directed mutagenesis for understanding protein-dna interactions. the new approach has been implemented in the bindn-rf web server for online prediction of dna-binding residues in protein sequences. competing interests the authors declare that they have no competing interests. authors' contributions lw initiated the study, conducted the data analysis, and drafted the manuscript. mqy and jyy participated in result interpretation and manuscript preparation. 
the evolutionary information contained in the unlabeled sequence data was represented as position-specific scoring matrices and several new descriptors. the rf classifier was further evaluated using a separate test dataset, and the predicted dna-binding residues were examined in the context of three-dimensional structures. with the rapid accumulation of sequence data, it becomes an important but challenging task to accurately predict dna-binding residues directly from amino acid sequence data. a new machine learning approach has been developed in this study for predicting dna-binding residues from amino acid sequence data. the approach used both the labelled data instances collected from the available structures of protein-dna complexes and the abundant unlabeled data found in protein sequence databases. the results suggest that the rf-based approach gives rise to more accurate prediction of dna-binding residues than previous studies. however, structural data are available for only a few hundreds of protein-dna complexes. the sequence-derived features were then used to train random forests, which could handle a large number of input variables and avoid model overfitting. to understand the molecular mechanism of protein-dna recognition, it is necessary to identify the dna-binding residues in dna-binding proteins. the use of evolutionary information was found to significantly improve classifier performance. a new web server called bindn-rf has thus been developed to make the rf classifier accessible to the biological research community. protein-dna interactions are involved in many biological processes essential for cellular function.
 protein-dna interactions are involved in many biological processes essential for cellular function. to understand the molecular mechanism of protein-dna recognition, it is necessary to identify the dna-binding residues in dna-binding proteins. however, structural data are available for only a few hundreds of protein-dna complexes. with the rapid accumulation of sequence data, it becomes an important but challenging task to accurately predict dna-binding residues directly from amino acid sequence data.  a new machine learning approach has been developed in this study for predicting dna-binding residues from amino acid sequence data. the approach used both the labelled data instances collected from the available structures of protein-dna complexes and the abundant unlabeled data found in protein sequence databases. the evolutionary information contained in the unlabeled sequence data was represented as position-specific scoring matrices and several new descriptors. the sequence-derived features were then used to train random forests, which could handle a large number of input variables and avoid model overfitting. the use of evolutionary information was found to significantly improve classifier performance. the rf classifier was further evaluated using a separate test dataset, and the predicted dna-binding residues were examined in the context of three-dimensional structures.  the results suggest that the rf-based approach gives rise to more accurate prediction of dna-binding residues than previous studies. a new web server called bindn-rf has thus been developed to make the rf classifier accessible to the biological research community. 14– july the international conference on bioinformatics & computational biology las vegas, nv, usa 