BACKGROUND
protein-protein interaction is intrinsic to most cellular processes and can aid significantly in identifying the function of newly discovered proteins and in understanding the molecular networks they participate in  <cit> .
therefore, one of the major remaining goals in functional genomics is to determine protein interaction networks for the whole organism.
to solve this problem, a vast set of impressive experimental techniques has been developed to predict the physical interactions which could lead to the identification of the functional relationships between proteins.
these techniques include; yeast two-hybrid-based methods  <cit> ; mass spectrometry  <cit> ; tandem affinity purification  <cit> ; protein chips  <cit> ; and hybrid approaches  <cit> .
these techniques have assisted in identifying hundreds of potential interacting proteins in several species such as yeast, drosophila, and helicobacter-pylori  <cit> .
they are however, both very expensive and significantly time consuming and to date the ppi pairs obtained cover only a fraction of the complete ppi network.
the technical limitations associated with the mentioned biochemical approaches have resulted in a growing need for development of computational tools that are capable of identifying ppis  <cit> .
hence, computational approaches remain essential both to assist in design and validation of experimental studies and for the prediction of interaction partners and detailed structures of protein complexes  <cit> .
as a result, a number of computational methods have been developed.
a number of the earlier computational methods were based on genomic information, such as similarity of expression profiles  <cit> , phylogenetic profiles  <cit>  or phylogenetic trees  <cit>  and adjacency of genes  <cit> .
however, the main limitations of such methods are that they can be applied only to completely sequenced gene and can be used only with essential proteins that are common to most organisms  <cit> .
most of the recent computational methods employ domain knowledge to predict the ppi.
the motivation behind this employment is that molecular interactions are typically mediated by a great variety of interacting domains  <cit> .
sprinzak et al.
<cit>  developed the association method  which defines a simple measure of interaction probability between two domains as the fraction of interacting protein pairs among all protein pairs containing the domain pairs.
the limitation of this method lies in the possibility to assign high association scores to domain pairs with low frequency.
deng et al.
<cit>  developed the maximum likelihood estimation  method which is based on the assumption that two proteins interact if at least one pair of domains of the two proteins interact.
huang et al.
<cit>  introduced the maximum specificity set cover .
huang started by selecting high quality protein interactions based on a clustering measure and then used mssc to assign probabilities to domain pairs.
as most of the existing domain-based methods consider only single-domain pairs and assume independence between domain-domain interactions, xue-wen et al.
<cit>  introduced a domain-based random forest of decision trees to infer protein interactions.
this method is capable of exploring all possible domain interactions and making predictions based on all the protein domains.
a recent tool termed pipe  was developed by sylvain et al.
<cit> .
pipe is based on the assumption that some of the interactions between proteins are mediated by a finite number of short polypeptide sequences.
these sequences are typically shorter than the classical domains, and are used repeatedly in different proteins and contexts within the cell.
once the interaction database is large enough to sample these sequences, it should be possible to accurately predict such ppis.
pipe uses the primary structure of proteins together with the available protein interaction data to predict the potential interaction between any target pair of saccharomyces cerevisiae proteins.
most of the methods discussed have common limitations:
• they are based on previously identified domains, and the identification of domain is a long and computationally expensive process.
• they all focus on domain structure and none considers the complete sequence information.
we understand that protein domains are highly informative for predicting ppi as they reflect the potential structural relationships between proteins.
however, other sequence parts  may also contribute significantly to the information by showing differences between proteins.
• they are not universal because their accuracy and reliability is dependant on the domain information or interaction marks of the protein partners.
• they often have limited abilities to detect novel interactions and to differentiate them from false positives.
a high rate of false negatives is another disadvantage associated with most of these methods.
in this paper, we introduce a simple yet effective method to predict ppi based on pairwise similarity and using only protein primary structure.
two proteins may interact by the means of the scores similarities they produce against subsequences of amino acids created by a large shifting window which passes over concatenated protein training sequences.
this work is motivated by the observation that the pairwise score, which measures the similarity between two protein sequences by a local gapped alignment, provides a relevant measure of similarity between protein sequences.
this similarity incorporates biological knowledge about protein evolutionary structural relationships  <cit> .
RESULTS
in our first experimental work, we tested the performance of our method on randomly selected  <dig> protein sequences from the yeast protein interaction.
the datasets are prepared as listed in table  <dig>  the mean, standard deviation and confidence level  of the length of the training and testing datasets are listed in table  <dig>
the goal of this experiment is to confirm that two sequences may interact if they are similar, but one must also be careful that the training and testing sets are sequence independent.
therefore, for each sequence  in the  testing set , we calculate the similarity sores  against each of the other  sequences in the training set .
the default alignment parameters are used; gap opening penalty and extension penalties of  <dig> and  <dig>  respectively, and the blosum  <dig> matrix.
the similarity averages  are calculated and finally the average  and standard deviation  of all averages are recorded.
the process is illustrated as follows:
we understand that similarity score is meaningful information when comparing protein sequences as it is derived from accumulated knowledge of both protein structure and function.
however, similarity score is difficult to interpret as it is not normalized on length.
therefore, we calculated the identity scores averages  and then the average  and standard deviation  of all averages are recorded.
for each sequence  in the testing set we align it against each sequence in the training set, count the number of positions that have identical amino acids and then divide by the total length of the alignment.
the process is illustrated as follows:
the maximum identity score  for each sequence in the testing set against each sequence in the training set is identified and the average  and standard deviation  of the  are then reported.
the process is illustrated as follow:
the final averages and standard deviations calculated from ,  and  are summarized in table  <dig>
this information shows that on average proteins in the testing set have realistic similar homologies in the training set.
the feature extraction step starts by creating a long string of amino acids by concatenating all of the  <dig> protein sequences available in the training dataset.
by choosing a large window of size  <dig>  we were able to generate  <dig> subsequences of lengths  <dig>   <dig> and  <dig>  respectively .
all protein sequences in the training and testing datasets were scored against the  <dig> generated subsequences using smith-waterman  algorithm as implemented in fasta  <cit> .
the sw  <cit>  has undergone two decades of empirical optimization in the field of bioinformatics and thus, considerable prior knowledge is implicitly incorporated into the pairwise sequence similarity scores and hence into the ppi-ps vector representation.
for instance, if we have a protein sequence s then the corresponding score will be  where m- <dig> is the total number of proteins and  is the e-value of the sw score between sequence s and the ith subsequence.
in this case, the default parameters are used; gap opening penalty and extension penalties of  <dig> and  <dig>  respectively, and the blosum  <dig> matrix.
based on prior biological knowledge about the interaction information between proteins, the feature vectors of two "interacted" proteins s <dig> and s <dig> are concatenated and added to the positive set, and the "non-interacting" proteins are also concatenated and added to the negative set for both training and testing datasets.
following the preparation of the training and testing sets, we employed gist svm to discriminate between the "interacted" and "non-interacted" proteins in the testing dataset.
the gist svm software is implemented by noble et al.
and it is available at .
in all experiments, gaussian radial basis function kernel  was used, the rbf kernel allows pockets of data to be classified which is more powerful approach than simply using a linear dot product  <cit> .
the function has the form , where x, xi ∈ x and γ >  <dig>  in all of the experimental work, the scaling parameter γ was set to  <dig> .
the accuracies of our predictions are measured by specificity , sensitivity  and the receiver operating characteristic .
the specificity is defined as the ratio of the number of matched interactions between the predicted set, and the observed testing set, over the total number of predicted interactions.
the sensitivity is defined as the ratio of the number of matched interactions to the total number of observed interactions in the testing set  <cit> .
the roc is the fraction of true positives  vs. the fraction of false positives .
in this particularly straightforward experimental work, we were able to achieve overall accuracy of 100%.
however it's pertinent to provide more analysis of the algorithm's performance and results.
in figure  <dig>  we summarize the similarity score of each protein sequence in the testing dataset against the three generated subsequences.
in our second experimental work, we assess the recognition ability of our method in classifying between  <dig> interacted protein pairs  and  <dig> non-interacted protein pairs .
the dataset used was randomly selected by sylvain et.
al  <cit>  and used to evaluate pipe's accuracy.
it was generated from the yeast protein interaction literature for which at least three different lines of experimental evidence supported the interaction.
the mean, standard deviation and confidence level  of the length of the  <dig> positive and  <dig> negative protein sequences are listed in table  <dig>  the averages and standard deviations calculated from ,  and  are summarized in table  <dig>
these results show that on average proteins in the testing set have high similar homologies to those in the training set.
we created a long string of amino acids by concatenating all of the  <dig> protein sequences .
various window sizes are used to generate various amino acid subsequences.
all of the  <dig> protein sequences were scored against the generated subsequences.
the experimental set up used was similar to that mentioned in the previous experiment, with the exception that hold-one-out cross-validation was employed to measure the accuracy.
in table  <dig>  we record the roc, sn, sp and the overall accuracy based on various window sizes.
the results show that window size equal to  <dig> produced better roc, sn, sp and overall accuracy results.
the proposed method shows an improvement over pipe.
pipe produced a sn of  <dig>  for detecting yeast protein interaction with  <dig>  sp and an overall accuracy of  <dig> .
to insure the effect of the leave-one-out evaluation, further investigation was conducted by creating a long string of amino acids by concatenating all of the  <dig> protein sequences except for the two sequences which are to be classified.
the results in this case show no statistical difference in accuracy .
this is most probably due to the fact that we eliminate only one feature vector.
in addition to its superior accuracy, ppi-ps has two further advantages when compared to pipe.
firstly, the pipe method is computationally intensive and the evaluation of pipe's performance over the same dataset took approximately  <dig>  hours of computation time compared to only a few minutes using ppi-ps  <cit> .
secondly, as is mentioned by the pipe's authors, their method is expected to be weak if it is used for detecting novel interactions among genome wide large-scale data sets.
this is not true for ppi-ps as can be seen in the subsequent sections of this paper which describe a large scale data test.
for the third experiment we furthermore split the  <dig> interacted protein pairs into two sets a  and b .
we also split the  <dig> non-interacted protein pairs into two sets c  and d .
we then combined a with c to create a training dataset and b with d to create a testing dataset.
a set up similar to that describe for experiment  <dig> was employed.
in table  <dig> we show roc, sn, sp and overall accuracy calculated using several window sizes .
values of n =  <dig> and  <dig> yielded more accurate results.
we understand that embedding pairs of protein sequences in a vector space could be order dependent  <cit>  and therefore, we ran additional experimental work to check the order dependency for sequence pairs.
we classified the testing pairs with the order of the sequence reversed.
instead of classifying the concatenation of s <dig> to s <dig>  we classified s <dig> to s <dig>  we then reported the average accuracy and compared it to the original order average.
table  <dig> summarizes this comparison and the results show no statistical effect on the accuracy.
in the fourth experimental work, we assess the recognition ability of our method on the dataset created by xue-wen et al.
<cit> .
xue-wen initially obtained  <dig>  interacting protein pairs in the yeast organism from dip,  <dig> pairs from deng et al.
<cit>  and  <dig> pairs from schwikowski et al.
<cit> .
the datasets were then combined by removing the overlapping interaction pairs and excluding the pairs for which at least one of the proteins had no domain information.
finally,  <dig> protein interaction pairs remained among  <dig> proteins, and they were separated evenly  into training and testing datasets.
as non-interacting protein data are unavailable, the negative samples are randomly generated.
a protein pair is considered to be a negative sample if the pair does not exist in the interaction set.
a total of  <dig> negative samples were generated and also separated into two halves.
both final training and testing datasets contain  <dig> samples,  <dig> positive and  <dig> negative samples.
the mean, standard deviation and confidence level  of the length of the  <dig> training examples and the  <dig> testing examples are listed in table  <dig>  the averages and standard deviations calculated from ,  and  are summarized in table  <dig>
this information shows that on average proteins in the testing set have high similar homologies in the training set.
in table  <dig> we show roc, sn, sp and overall accuracy calculated using various window sizes .
values of n =  <dig> produced more accurate results.
we further compared the classification accuracy averages based on the original and reverse protein order as discussed in the third experiment.
table  <dig> summarizes the comparison.
the results show no significant statistical effect on the accuracy.
for comparative purposes, we tested two further state-of-the-art sequence based methods, maximum likelihood estimation  developed by deng et al.
<cit>  and domain-based random forest of decision trees, developed by xue-wen et al.
<cit> .
the results of the primary experiment with a window size n =  <dig> are summarized in figure  <dig>  the figure also shows a performance comparison between ppi-ps and the other two state-of-the-art sequence based methods; mle and domain-based random forest of decision trees.
higher sn, sp and overall accuracy correspond to more accurate ppi detection performance.
selecting any of these performance measures, it is clear that the ppi-ps method performs better than the other methods.
discussion
the method presented in this paper is based on the assumption that two proteins may interact if their pairwise scores against large subsequences of amino acids created by shifting a window over concatenated protein training sequences are similar.
it is commonly understood that, this assumption excludes the applicability of interactions of proteins which are not similar or evolutionary related to each other.
however, the main contribution of this paper is to show that pairwise sequence comparison can be extremely powerful when combined with support vector machines .
moreover, we are motivated by the fact that sw alignment score provides a relevant measure of similarity between proteins.
therefore protein sequence similarity typically implies homology, which in turn may imply structural and functional similarity  <cit> .
the experimental results have shown that the ppi-ps method applied to different datasets from the yeast saccharomyces cerevisiae protein interaction literature can predict ppis with higher specificity and sensitivity than pipe, mle and decision forest methods.
the detailed properties of the protein datasets used in this research work are presented and analysed.
the average maximum sequence identity between testing and training datasets is considered high which could confirm that two sequences may interact if they are similar.
in addition, this could also make the prediction task easier as in this case many of the test sequences have homologs in the training dataset.
ideally, one would create a dataset in which there is low sequence similarity between members in order to prove generalizability, however, in this study we used previously established benchmark datasets in order to make our results directly comparable.
the remarkable accuracy of our method follows from the combination of two widely used and significantly powerful algorithms.
firstly, the svm algorithm is based on a sound mathematical framework and much of its power is derived from its criterion for selecting a separating hyperplane that maintains a maximum margin from any point in the training set  <cit> .
secondly, sw scores have been developed to quantify the similarity of biological sequences.
their parameters have been optimized over the past two decades to provide relevant measures of similarity between sequences and they now represent core tools in computational biology  <cit> .
one significant characteristic of any protein-protein interaction prediction algorithm is the computation efficiency.
in order to gauge the computational cost of the proposed approach, ppi-ps includes svm optimization, whose complexity is roughly o, where n in this case is the number of training set examples  <cit> .
the feature sensitivity measure step of ppi-ps method involves computing n <dig> pairwise scores.
using sw itself is computed by dynamic programming and each computation is o, where m is the length of the longest sequence in the training set.
the method presented here is encouraged by the success of our earlier method, subss  <cit>  which was used to distinguish between high confidence protein interaction pairs and low confidence or unknown protein interaction pairs.
despite the fact that subss has shown considerable accuracy improvement over the existing techniques, subss has three main limitations:  the size of the sliding window used and analyzed was very small.
small size subsequence of amino acid is likely to appear in many protein sequences makes it difficult to judge whether the two proteins are actually interacting or not.
sliding a small window size yields more subsequences which significantly increase the computational time.
since each sw computation cost is o, the total cost to compare α protein sequences to β subsequences is o. small window size will increase the value of β.  the results produced by subss are not stable since the method is designed to randomly select several negative examples from the low confidence protein interacting pairs every time the method runs.
in this work only large values of n were used and analyzed.
the method is intensively tested and validated by comparing it with highly respected existing methods.
it is important to mention that the idea of representing protein sequence via its similarity to a collection of other sequences is not novel.
liao et al.
<cit>  and zaki et al.
<cit>  have conducted similar work in their algorithm to detect protein remote homology.
CONCLUSIONS
protein-protein interaction has proven to be a valuable biological knowledge and starting point for understanding how the cell internally works.
in this study we propose a method for ppi prediction using only the primary structure information of protein sequence.
the method was developed based on a combination of pairwise similarity and support vector machine.
it is shown that pairwise similarity score provides relevant measure of similarity between protein sequences.
this similarity incorporates biological knowledge about proteins and its extremely powerful when combined with support vector machine to predict ppi.
finally, the success of the ppi-ps method at predicting ppi encouraged us to plan future investigations such as optimizing the subsequence size and applying the method on gold standard positive  and negative  interaction sets recently created by ramazan et al.
<cit> .
we understand that similarity is not the only evidence of protein interaction; however, researchers have not intensively tested how much evidence similarity could provide.
a combination of knowledge about gene ontology , inter-domain linker region and interacting sites may significantly improve the prediction accuracy.

 protein-protein interaction is intrinsic to most cellular processes and can aid significantly in identifying the function of newly discovered proteins and in understanding the molecular networks they participate in. therefore, one of the major remaining goals in functional genomics is to determine protein interaction networks for the whole organism. to solve this problem, a vast set of impressive experimental techniques has been developed to predict the physical interactions which could lead to the identification of the functional relationships between proteins. these techniques include; yeast two-hybrid-based methods; mass spectrometry; tandem affinity purification; protein chips; and hybrid approaches. these techniques have assisted in identifying hundreds of potential interacting proteins in several species such as yeast, drosophila, and helicobacter-pylori. they are however, both very expensive and significantly time consuming and to date the ppi pairs obtained cover only a fraction of the complete ppi network. the technical limitations associated with the mentioned biochemical approaches have resulted in a growing need for development of computational tools that are capable of identifying ppis. hence, computational approaches remain essential both to assist in design and validation of experimental studies and for the prediction of interaction partners and detailed structures of protein complexes. as a result, a number of computational methods have been developed. a number of the earlier computational methods were based on genomic information, such as similarity of expression profiles, phylogenetic profiles or phylogenetic trees and adjacency of genes. however, the main limitations of such methods are that they can be applied only to completely sequenced gene and can be used only with essential proteins that are common to most organisms. most of the recent computational methods employ domain knowledge to predict the ppi. the motivation behind this employment is that molecular interactions are typically mediated by a great variety of interacting domains. sprinzak et al. developed the association method which defines a simple measure of interaction probability between two domains as the fraction of interacting protein pairs among all protein pairs containing the domain pairs. the limitation of this method lies in the possibility to assign high association scores to domain pairs with low frequency. deng et al. developed the maximum likelihood estimation method which is based on the assumption that two proteins interact if at least one pair of domains of the two proteins interact. huang et al. introduced the maximum specificity set cover. huang started by selecting high quality protein interactions based on a clustering measure and then used mssc to assign probabilities to domain pairs. as most of the existing domain-based methods consider only single-domain pairs and assume independence between domain-domain interactions, xue-wen et al. introduced a domain-based random forest of decision trees to infer protein interactions. this method is capable of exploring all possible domain interactions and making predictions based on all the protein domains. a recent tool termed pipe was developed by sylvain et al.. pipe is based on the assumption that some of the interactions between proteins are mediated by a finite number of short polypeptide sequences. these sequences are typically shorter than the classical domains, and are used repeatedly in different proteins and contexts within the cell. once the interaction database is large enough to sample these sequences, it should be possible to accurately predict such ppis. pipe uses the primary structure of proteins together with the available protein interaction data to predict the potential interaction between any target pair of saccharomyces cerevisiae proteins. most of the methods discussed have common limitations: • they are based on previously identified domains, and the identification of domain is a long and computationally expensive process. • they all focus on domain structure and none considers the complete sequence information. we understand that protein domains are highly informative for predicting ppi as they reflect the potential structural relationships between proteins. however, other sequence parts may also contribute significantly to the information by showing differences between proteins. • they are not universal because their accuracy and reliability is dependant on the domain information or interaction marks of the protein partners. • they often have limited abilities to detect novel interactions and to differentiate them from false positives. a high rate of false negatives is another disadvantage associated with most of these methods. in this paper, we introduce a simple yet effective method to predict ppi based on pairwise similarity and using only protein primary structure. two proteins may interact by the means of the scores similarities they produce against subsequences of amino acids created by a large shifting window which passes over concatenated protein training sequences. this work is motivated by the observation that the pairwise score, which measures the similarity between two protein sequences by a local gapped alignment, provides a relevant measure of similarity between protein sequences. this similarity incorporates biological knowledge about protein evolutionary structural relationships.  in our first experimental work, we tested the performance of our method on randomly selected protein sequences from the yeast protein interaction. the datasets are prepared as listed in table the mean, standard deviation and confidence level of the length of the training and testing datasets are listed in table the goal of this experiment is to confirm that two sequences may interact if they are similar, but one must also be careful that the training and testing sets are sequence independent. therefore, for each sequence in the testing set, we calculate the similarity sores against each of the other sequences in the training set. the default alignment parameters are used; gap opening penalty and extension penalties of and respectively, and the blosum matrix. the similarity averages are calculated and finally the average and standard deviation of all averages are recorded. the process is illustrated as follows: we understand that similarity score is meaningful information when comparing protein sequences as it is derived from accumulated knowledge of both protein structure and function. however, similarity score is difficult to interpret as it is not normalized on length. therefore, we calculated the identity scores averages and then the average and standard deviation of all averages are recorded. for each sequence in the testing set we align it against each sequence in the training set, count the number of positions that have identical amino acids and then divide by the total length of the alignment. the process is illustrated as follows: the maximum identity score for each sequence in the testing set against each sequence in the training set is identified and the average and standard deviation of the are then reported. the process is illustrated as follow: the final averages and standard deviations calculated from, and are summarized in table this information shows that on average proteins in the testing set have realistic similar homologies in the training set. the feature extraction step starts by creating a long string of amino acids by concatenating all of the protein sequences available in the training dataset. by choosing a large window of size we were able to generate subsequences of lengths and respectively. all protein sequences in the training and testing datasets were scored against the generated subsequences using smith-waterman algorithm as implemented in fasta. the sw has undergone two decades of empirical optimization in the field of bioinformatics and thus, considerable prior knowledge is implicitly incorporated into the pairwise sequence similarity scores and hence into the ppi-ps vector representation. for instance, if we have a protein sequence s then the corresponding score will be where m- is the total number of proteins and is the e-value of the sw score between sequence s and the ith subsequence. in this case, the default parameters are used; gap opening penalty and extension penalties of and respectively, and the blosum matrix. based on prior biological knowledge about the interaction information between proteins, the feature vectors of two "interacted" proteins s and s are concatenated and added to the positive set, and the "non-interacting" proteins are also concatenated and added to the negative set for both training and testing datasets. following the preparation of the training and testing sets, we employed gist svm to discriminate between the "interacted" and "non-interacted" proteins in the testing dataset. the gist svm software is implemented by noble et al. and it is available at. in all experiments, gaussian radial basis function kernel was used, the rbf kernel allows pockets of data to be classified which is more powerful approach than simply using a linear dot product. the function has the form, where x, xi ∈ x and γ > in all of the experimental work, the scaling parameter γ was set to. the accuracies of our predictions are measured by specificity, sensitivity and the receiver operating characteristic. the specificity is defined as the ratio of the number of matched interactions between the predicted set, and the observed testing set, over the total number of predicted interactions. the sensitivity is defined as the ratio of the number of matched interactions to the total number of observed interactions in the testing set. the roc is the fraction of true positives vs. the fraction of false positives. in this particularly straightforward experimental work, we were able to achieve overall accuracy of 100%. however it's pertinent to provide more analysis of the algorithm's performance and results. in figure we summarize the similarity score of each protein sequence in the testing dataset against the three generated subsequences. in our second experimental work, we assess the recognition ability of our method in classifying between interacted protein pairs and non-interacted protein pairs. the dataset used was randomly selected by sylvain et. al and used to evaluate pipe's accuracy. it was generated from the yeast protein interaction literature for which at least three different lines of experimental evidence supported the interaction. the mean, standard deviation and confidence level of the length of the positive and negative protein sequences are listed in table the averages and standard deviations calculated from, and are summarized in table these results show that on average proteins in the testing set have high similar homologies to those in the training set. we created a long string of amino acids by concatenating all of the protein sequences. various window sizes are used to generate various amino acid subsequences. all of the protein sequences were scored against the generated subsequences. the experimental set up used was similar to that mentioned in the previous experiment, with the exception that hold-one-out cross-validation was employed to measure the accuracy. in table we record the roc, sn, sp and the overall accuracy based on various window sizes. the results show that window size equal to produced better roc, sn, sp and overall accuracy results. the proposed method shows an improvement over pipe. pipe produced a sn of for detecting yeast protein interaction with sp and an overall accuracy of. to insure the effect of the leave-one-out evaluation, further investigation was conducted by creating a long string of amino acids by concatenating all of the protein sequences except for the two sequences which are to be classified. the results in this case show no statistical difference in accuracy. this is most probably due to the fact that we eliminate only one feature vector. in addition to its superior accuracy, ppi-ps has two further advantages when compared to pipe. firstly, the pipe method is computationally intensive and the evaluation of pipe's performance over the same dataset took approximately hours of computation time compared to only a few minutes using ppi-ps. secondly, as is mentioned by the pipe's authors, their method is expected to be weak if it is used for detecting novel interactions among genome wide large-scale data sets. this is not true for ppi-ps as can be seen in the subsequent sections of this paper which describe a large scale data test. for the third experiment we furthermore split the interacted protein pairs into two sets a and b. we also split the non-interacted protein pairs into two sets c and d. we then combined a with c to create a training dataset and b with d to create a testing dataset. a set up similar to that describe for experiment was employed. in table we show roc, sn, sp and overall accuracy calculated using several window sizes. values of n = and yielded more accurate results. we understand that embedding pairs of protein sequences in a vector space could be order dependent and therefore, we ran additional experimental work to check the order dependency for sequence pairs. we classified the testing pairs with the order of the sequence reversed. instead of classifying the concatenation of s to s we classified s to s we then reported the average accuracy and compared it to the original order average. table summarizes this comparison and the results show no statistical effect on the accuracy. in the fourth experimental work, we assess the recognition ability of our method on the dataset created by xue-wen et al.. xue-wen initially obtained interacting protein pairs in the yeast organism from dip, pairs from deng et al. and pairs from schwikowski et al.. the datasets were then combined by removing the overlapping interaction pairs and excluding the pairs for which at least one of the proteins had no domain information. finally, protein interaction pairs remained among proteins, and they were separated evenly into training and testing datasets. as non-interacting protein data are unavailable, the negative samples are randomly generated. a protein pair is considered to be a negative sample if the pair does not exist in the interaction set. a total of negative samples were generated and also separated into two halves. both final training and testing datasets contain samples, positive and negative samples. the mean, standard deviation and confidence level of the length of the training examples and the testing examples are listed in table the averages and standard deviations calculated from, and are summarized in table this information shows that on average proteins in the testing set have high similar homologies in the training set. in table we show roc, sn, sp and overall accuracy calculated using various window sizes. values of n = produced more accurate results. we further compared the classification accuracy averages based on the original and reverse protein order as discussed in the third experiment. table summarizes the comparison. the results show no significant statistical effect on the accuracy. for comparative purposes, we tested two further state-of-the-art sequence based methods, maximum likelihood estimation developed by deng et al. and domain-based random forest of decision trees, developed by xue-wen et al.. the results of the primary experiment with a window size n = are summarized in figure the figure also shows a performance comparison between ppi-ps and the other two state-of-the-art sequence based methods; mle and domain-based random forest of decision trees. higher sn, sp and overall accuracy correspond to more accurate ppi detection performance. selecting any of these performance measures, it is clear that the ppi-ps method performs better than the other methods. discussion the method presented in this paper is based on the assumption that two proteins may interact if their pairwise scores against large subsequences of amino acids created by shifting a window over concatenated protein training sequences are similar. it is commonly understood that, this assumption excludes the applicability of interactions of proteins which are not similar or evolutionary related to each other. however, the main contribution of this paper is to show that pairwise sequence comparison can be extremely powerful when combined with support vector machines. moreover, we are motivated by the fact that sw alignment score provides a relevant measure of similarity between proteins. therefore protein sequence similarity typically implies homology, which in turn may imply structural and functional similarity. the experimental results have shown that the ppi-ps method applied to different datasets from the yeast saccharomyces cerevisiae protein interaction literature can predict ppis with higher specificity and sensitivity than pipe, mle and decision forest methods. the detailed properties of the protein datasets used in this research work are presented and analysed. the average maximum sequence identity between testing and training datasets is considered high which could confirm that two sequences may interact if they are similar. in addition, this could also make the prediction task easier as in this case many of the test sequences have homologs in the training dataset. ideally, one would create a dataset in which there is low sequence similarity between members in order to prove generalizability, however, in this study we used previously established benchmark datasets in order to make our results directly comparable. the remarkable accuracy of our method follows from the combination of two widely used and significantly powerful algorithms. firstly, the svm algorithm is based on a sound mathematical framework and much of its power is derived from its criterion for selecting a separating hyperplane that maintains a maximum margin from any point in the training set. secondly, sw scores have been developed to quantify the similarity of biological sequences. their parameters have been optimized over the past two decades to provide relevant measures of similarity between sequences and they now represent core tools in computational biology. one significant characteristic of any protein-protein interaction prediction algorithm is the computation efficiency. in order to gauge the computational cost of the proposed approach, ppi-ps includes svm optimization, whose complexity is roughly o, where n in this case is the number of training set examples. the feature sensitivity measure step of ppi-ps method involves computing n pairwise scores. using sw itself is computed by dynamic programming and each computation is o, where m is the length of the longest sequence in the training set. the method presented here is encouraged by the success of our earlier method, subss which was used to distinguish between high confidence protein interaction pairs and low confidence or unknown protein interaction pairs. despite the fact that subss has shown considerable accuracy improvement over the existing techniques, subss has three main limitations: the size of the sliding window used and analyzed was very small. small size subsequence of amino acid is likely to appear in many protein sequences makes it difficult to judge whether the two proteins are actually interacting or not. sliding a small window size yields more subsequences which significantly increase the computational time. since each sw computation cost is o, the total cost to compare α protein sequences to β subsequences is o. small window size will increase the value of β. the results produced by subss are not stable since the method is designed to randomly select several negative examples from the low confidence protein interacting pairs every time the method runs. in this work only large values of n were used and analyzed. the method is intensively tested and validated by comparing it with highly respected existing methods. it is important to mention that the idea of representing protein sequence via its similarity to a collection of other sequences is not novel. liao et al. and zaki et al. have conducted similar work in their algorithm to detect protein remote homology.  protein-protein interaction has proven to be a valuable biological knowledge and starting point for understanding how the cell internally works. in this study we propose a method for ppi prediction using only the primary structure information of protein sequence. the method was developed based on a combination of pairwise similarity and support vector machine. it is shown that pairwise similarity score provides relevant measure of similarity between protein sequences. this similarity incorporates biological knowledge about proteins and its extremely powerful when combined with support vector machine to predict ppi. finally, the success of the ppi-ps method at predicting ppi encouraged us to plan future investigations such as optimizing the subsequence size and applying the method on gold standard positive and negative interaction sets recently created by ramazan et al.. we understand that similarity is not the only evidence of protein interaction; however, researchers have not intensively tested how much evidence similarity could provide. a combination of knowledge about gene ontology, inter-domain linker region and interacting sites may significantly improve the prediction accuracy. 
in this paper, we propose a simple yet effective method to detect ppi based on pairwise similarity and using only the primary structure of the protein. the ppi based on pairwise similarity method consists of a representation of each protein sequence by a vector of pairwise similarities against large subsequences of amino acids created by a shifting window which passes over concatenated protein training sequences. the proposed method achieved reasonable improvement over the existing state-of-the-art methods for ppi prediction. given that the association and dissociation of protein molecules is crucial, computational tools capable of effectively identifying ppi are desirable. pairwise similarity score provides a relevant measure of similarity between protein sequences. protein-protein interaction is essential to most biological processes. to assess the ability of the proposed method to recognize the difference between "interacted" and "non-interacted" proteins pairs, we applied it on different datasets from the available yeast saccharomyces cerevisiae protein interaction. these vectors are then used to compute the kernel matrix which will be exploited in conjunction with support vector machines. this similarity incorporates biological knowledge about proteins and it is extremely powerful when combined with support vector machine to predict ppi.
 protein-protein interaction is essential to most biological processes. abnormal interactions may have implications in a number of neurological syndromes. given that the association and dissociation of protein molecules is crucial, computational tools capable of effectively identifying ppi are desirable. in this paper, we propose a simple yet effective method to detect ppi based on pairwise similarity and using only the primary structure of the protein. the ppi based on pairwise similarity method consists of a representation of each protein sequence by a vector of pairwise similarities against large subsequences of amino acids created by a shifting window which passes over concatenated protein training sequences. each coordinate of this vector is typically the e-value of the smith-waterman score. these vectors are then used to compute the kernel matrix which will be exploited in conjunction with support vector machines.  to assess the ability of the proposed method to recognize the difference between "interacted" and "non-interacted" proteins pairs, we applied it on different datasets from the available yeast saccharomyces cerevisiae protein interaction. the proposed method achieved reasonable improvement over the existing state-of-the-art methods for ppi prediction.  pairwise similarity score provides a relevant measure of similarity between protein sequences. this similarity incorporates biological knowledge about proteins and it is extremely powerful when combined with support vector machine to predict ppi. 