BACKGROUND
identification of functionally important regions directly from a protein sequence is a challenging problem in molecular biology  <cit> .
investigation of possible protein-protein interactions and prediction of the associated physical binding areas facilitate the study of all aspects of cellular function  <cit> .
the principles that govern the interaction of two proteins and the general properties of their interacting interfaces remain uncovered  <cit> , resulting in the difficulties of predicting interface regions directly from protein sequences.
even when the structure of a protein is available, it is still not a trivial task to localize the functional interfaces and to clarify the contribution of each involved residue  <cit> .
previous studies observed that not all the interface residues contribute the same level of free energy in a complex  <cit> .
using the alanine scanning mutagenesis  <cit> , which estimates the energetic contribution of individual side-chains, it suggests that a small set of interface residues can contribute the most to the binding free energy  <cit> .
these critical residues are called hot spots; they give rise to a significant increase in the absolute binding energy when mutated to alanine  <cit> .
it is interestingly observed that hot spots are not uniformly spread along the interfaces.
instead, they are clustered as densely packed regions and are surrounded by energetically less important residues which might serve to occlude bulk solvent from the hot spots  <cit> .
the assemblies of the hot spots and its neighboring moderately conserved residues are called hot regions  <cit> .
a single or a few hot regions can be found in the interacting interface of two proteins  <cit> .
within the dense clusters, the hot spots and some moderately conserved residues both contribute to the stability of the complex  <cit> .
several approaches have attempted to predict interacting sites based on structure information  <cit> .
some of the approaches identify potential surface patches based on the shape of structures and then use features such as solvation potential, hydrophobicity, planarity, or accessible surface area to differentiate interacting sites from the other surface patches.
evolutionary information has also been demonstrated as a useful feature to this problem and widely employed when structures are available  <cit> .
while little correlation between interface and conservation is observed at the level of amino acid side-chains  <cit> , the conservation degrees of hot spots are more significant  <cit> .
several studies have shown that hot spots are usually more conserved than other surface residues and clustered in space  <cit> .
it has been also shown that structurally conserved residues at protein-protein interfaces correlate with the experimental alanine-scanning hot spots  <cit> .
in other words, the residues that affect the binding free energy dramatically tend to be strictly conserved during evolution.
in this regard, lichtarge et al.
proposed an evolutionary trace method to facilitate the study of protein interfaces  <cit> , followed by the development of an easy-to-use facility named consurf by armon et al.
in  <dig>  <cit> .
the procedure is based on extraction of functionally important residues from homologous proteins, and after that the conserved residues are mapped onto the protein surface to identify the functional interfaces  <cit> .
the task becomes much more challenging when only sequence information is available.
in such situation, the information about residue composition remains.
besides, evolutionary information is also available if there are sufficient homologues.
in this regard, a classification scheme based on neural networks or support vector machines  with the features extracted from a sliding window on amino acid composition and evolutionary information is usually adopted  <cit> .
constructing a classifier requires a set of training data for which the protein structures are available.
after that, the interacting residues of a query sequence can be predicted without structure information.
even though the information about which conserved residues form clusters in space is absent and cannot be exploited here, another observation from  <cit> , interface residues tend to form clusters in sequence, has been aggressively employed in recent studies to refine the predicting results  <cit> .
there also exist approaches that attempt to tackle this problem without learning from existing structures.
gallet et al.
showed in their work that the interacting residues can be identified by hydrophobic moments  <cit> .
as evolutionary information is demonstrated to be useful in finding interacting sites, we present here an alternative approach to discover conserved residues, sequential pattern mining  <cit> .
different from the evolutionary information derived by multiple sequence alignment of homologous sequences, the pattern mining approach focuses on the concurrence of several conserved blocks present in a subset of protein homologues  <cit> .
sequential pattern mining discovers a particular subsequence that frequently occurs among a set of sequences  <cit> .
this technique has been widely used to identify protein motifs in many previous studies  <cit> , where the term motif refers to such a subsequence that captures the characteristic regarding a specific biochemical function  <cit> .
finding functional motifs directly from protein sequences is challenging, because many sequence motifs are discontinuous and the spacing between motif elements is usually large and irregular  <cit> .
by considering large flexible gaps in sequential pattern mining, the developed method can deliver long patterns spanning large wildcard regions efficiently  <cit> .
though the conserved blocks in our patterns are largely separated in sequences, they are often close to each other in 3d structures and play critical roles to protein functions  <cit> .
the proposed methodology performs well even when the similarity identities between input sequences are low or the functional sites are only conserved in a few members of the input sequences  <cit> .
this feature is important since it has been observed that residues that are conserved only in a specific subfamily may play more family-specific functional roles and are usually found at functional patches  <cit> .
we expect that a highly supported pattern may highlight the residues that were conserved together during evolution for a particular purpose, for example, interacting with other proteins.
the experimental results conducted in this work reveal that the conservation information provided by sequential pattern mining is helpful to this problem before any existing structures are included to facilitate the learning task.
this paper investigates the effectiveness of the approach by answering the following two questions:  are the locations of the sequential blocks near the interfaces of protein-protein interactions?
and  do the derived sequential blocks tend to cluster together in space?
of course the first question is more related to the objective of this study.
but by answering the second question, we expect to make it clearer why the proposed methodology works.
we do not address the recall issue in this paper because we are aware of that it might not be possible to identify the complete set of interacting residues by a single pattern or in a single run of mining process.
in fact, identifying important residues associated with hot regions is not identical to the problem of predicting interacting residues.
as mentioned in the previous paragraphs, not all the interface residues are hot spots and expected to be conserved.
on the other hand, some interior residues might also contribute to the stability of the complexes and are thus conserved.
this work aims to show that the information provided by sequential pattern mining is useful to discovering hot regions of protein-protein interactions.
this information can be refined and incorporated in other approaches to enhance the predicting power of the state of the art predictors.
RESULTS
in this section, we first describe the datasets used in this work and how the patterns are selected for different experiments.
using the five proteins in the first dataset, we investigate the potential of sequential pattern mining in identifying hot regions of protein-protein interactions by examining carefully the discovered patterns.
to illustrate the advantages of our method, we compare our results with consurf's results.
next, we use the  <dig> protein chains of the second dataset to evaluate the general performance of the proposed method.
the details of the datasets and the experimental procedures are described in the following subsections.
datasets
pattern selection
for the first dataset, the top ten large-size patterns are examined for the mining results of each query protein.
the size of a pattern is defined as the number of conserved residues it contains.
in the first experiment, it is observed in every case that the hot regions can be revealed directly by the maximum-size pattern.
thus in the second experiment, we investigate how the maximum-size pattern of each query protein performs in identifying protein interacting regions automatically.
results on the first dataset
the performance of the proposed methodology is evaluated from two aspects.
first, the effectiveness of identifying hot regions is evaluated.
second, the efficiency of the pattern mining algorithm is compared with consurf, where multiple sequence alignment is employed in identifying conserved residues.
in addition, the conservation plots generated by consurf are included for comparison.
the mining results for the five proteins in the first dataset are shown in figure  <dig>   <dig>   <dig>   <dig>   <dig>  in that the patterns are plotted on the complexes for easy visualization.
in these figures, the discovered conserved blocks are shown in sticks representation.
in most cases, all the sequential blocks of the pattern cluster in one region of the protein and form the substructure associated with the interface of the complex.
differently, for the protein grpe in figure  <dig>  the conserved blocks form two hot regions that together constitute the interacting interface.
the conservation plots generated by magiic-pro are compared with that produced by consurf, as shown in figure  <dig>  the conservation information suggested by consurf might be too noisy to predict hot regions directly from the sequences.
it would be helpful if the structures of complexes are available as suggested by armon et al.
and lichtarge et al.
in their papers  <cit> .
finally, table  <dig> shows the executing time for magiic-pro and consurf respectively.
results on the second dataset
the summary of the experimental results on the second dataset is provided in table  <dig>  while the details can be found in the online supplement of this paper  <cit> .
among the  <dig> protein chains in the second dataset, two protein chains are excluded from the test set because the protein sequence of the protein chain  is not available in the pdb file and the protein chain  does not have enough homologues for pattern mining .
as listed in table  <dig>  magiic-pro successfully generated patterns for  <dig> protein chains.
for each chain, we selected the pattern with the most components  as the prediction of hot regions.
since only patterns with at least two blocks are reported, a maximum-size pattern always has two or more blocks to examine.
here we define two indices to evaluate the quality of a pattern:
<dig>  clustering propensity: the percentage of sequential blocks in a pattern p that interacts with at least one of the other blocks in p. the interaction between a pair of blocks is defined by the following criterion: there exists an atom from one block that is within  <dig> Å to an atom of the other block.
<dig>  interface propensity: the percentage of sequential blocks in a pattern p that contacts another protein chain in the complex.
the definition of contact is that any of the atoms from the block is within  <dig> Å to any atom of another protein chain in the complex.
the clustering propensity of a pattern reflects its reliability.
we consider that a higher value of this index indicates that the pattern is more biologically meaningful, either from function or structure point of view.
for each query protein, the clustering and interface propensities are calculated for its maximum-size pattern.
the average values for different categories of protein complexes are provided in table  <dig>  the group of enzyme-inhibitor complexes slightly outperforms the other categories.
it can be seen in table  <dig> that the results on the non-redundant set are similar.
when creating the non-redundant set, the program cd-hit was applied directly to the  <dig> protein chains to avoid selecting the protein chains that failed to deliver patterns as the representatives.
similar conclusion can be made from table  <dig>  as summarized in table  <dig>  there are about 66% of the derived blocks close to the contacting areas of protein-protein interactions.
furthermore, there are about 92% of the blocks clustering with at least one of the other blocks to form protein substructures in space.
it is observed in some cases that some clustered but non-interacting blocks are actually the binding sites of other molecules .
in table  <dig>  we show the statistics about the number of blocks of the maximum-size patterns for the  <dig> protein chains.
the number of blocks that contribute to interface is further collected in table  <dig>  in table  <dig>  it is of interest to check the number of proteins whose maximum-size pattern discovers at least two or three interacting blocks.
the percentages are 83% and 54% respectively.
we conclude that most of the tested proteins can be benefited by this approach, and similar records  are observed on the non-redundant set in table  <dig>
CONCLUSIONS
conservation information is important in predicting hot regions involved in protein-protein binding.
however, the conservation information at residue level is not sufficient in predicting hot regions because not all the reported residues are conserved for the same purpose .
the conservation information derived by the pattern mining approach is more precise than that generated by multiple sequence alignment followed by constructing the evolutionary tree.
that is, the concurrence of conserved blocks among a subset of protein homologues is focused.
the experiments conducted in this paper reveal that the derived conserved blocks tend to cluster together in space and most of the aggregated blocks are related with interacting interfaces.
the detected regions possess high conservation and thus are considered as the computational hot regions.
by using sequential pattern mining, it may be possible to predict hot spots of an interface without exhaustive mutagenesis and thermodynamic analysis and thus the link between protein functions and their primary sequences can be constructed much more rapidly.

 identification of functionally important regions directly from a protein sequence is a challenging problem in molecular biology. investigation of possible protein-protein interactions and prediction of the associated physical binding areas facilitate the study of all aspects of cellular function. the principles that govern the interaction of two proteins and the general properties of their interacting interfaces remain uncovered, resulting in the difficulties of predicting interface regions directly from protein sequences. even when the structure of a protein is available, it is still not a trivial task to localize the functional interfaces and to clarify the contribution of each involved residue. previous studies observed that not all the interface residues contribute the same level of free energy in a complex. using the alanine scanning mutagenesis, which estimates the energetic contribution of individual side-chains, it suggests that a small set of interface residues can contribute the most to the binding free energy. these critical residues are called hot spots; they give rise to a significant increase in the absolute binding energy when mutated to alanine. it is interestingly observed that hot spots are not uniformly spread along the interfaces. instead, they are clustered as densely packed regions and are surrounded by energetically less important residues which might serve to occlude bulk solvent from the hot spots. the assemblies of the hot spots and its neighboring moderately conserved residues are called hot regions. a single or a few hot regions can be found in the interacting interface of two proteins. within the dense clusters, the hot spots and some moderately conserved residues both contribute to the stability of the complex. several approaches have attempted to predict interacting sites based on structure information. some of the approaches identify potential surface patches based on the shape of structures and then use features such as solvation potential, hydrophobicity, planarity, or accessible surface area to differentiate interacting sites from the other surface patches. evolutionary information has also been demonstrated as a useful feature to this problem and widely employed when structures are available. while little correlation between interface and conservation is observed at the level of amino acid side-chains, the conservation degrees of hot spots are more significant. several studies have shown that hot spots are usually more conserved than other surface residues and clustered in space. it has been also shown that structurally conserved residues at protein-protein interfaces correlate with the experimental alanine-scanning hot spots. in other words, the residues that affect the binding free energy dramatically tend to be strictly conserved during evolution. in this regard, lichtarge et al. proposed an evolutionary trace method to facilitate the study of protein interfaces, followed by the development of an easy-to-use facility named consurf by armon et al. in. the procedure is based on extraction of functionally important residues from homologous proteins, and after that the conserved residues are mapped onto the protein surface to identify the functional interfaces. the task becomes much more challenging when only sequence information is available. in such situation, the information about residue composition remains. besides, evolutionary information is also available if there are sufficient homologues. in this regard, a classification scheme based on neural networks or support vector machines with the features extracted from a sliding window on amino acid composition and evolutionary information is usually adopted. constructing a classifier requires a set of training data for which the protein structures are available. after that, the interacting residues of a query sequence can be predicted without structure information. even though the information about which conserved residues form clusters in space is absent and cannot be exploited here, another observation from, interface residues tend to form clusters in sequence, has been aggressively employed in recent studies to refine the predicting results. there also exist approaches that attempt to tackle this problem without learning from existing structures. gallet et al. showed in their work that the interacting residues can be identified by hydrophobic moments. as evolutionary information is demonstrated to be useful in finding interacting sites, we present here an alternative approach to discover conserved residues, sequential pattern mining. different from the evolutionary information derived by multiple sequence alignment of homologous sequences, the pattern mining approach focuses on the concurrence of several conserved blocks present in a subset of protein homologues. sequential pattern mining discovers a particular subsequence that frequently occurs among a set of sequences. this technique has been widely used to identify protein motifs in many previous studies, where the term motif refers to such a subsequence that captures the characteristic regarding a specific biochemical function. finding functional motifs directly from protein sequences is challenging, because many sequence motifs are discontinuous and the spacing between motif elements is usually large and irregular. by considering large flexible gaps in sequential pattern mining, the developed method can deliver long patterns spanning large wildcard regions efficiently. though the conserved blocks in our patterns are largely separated in sequences, they are often close to each other in 3d structures and play critical roles to protein functions. the proposed methodology performs well even when the similarity identities between input sequences are low or the functional sites are only conserved in a few members of the input sequences. this feature is important since it has been observed that residues that are conserved only in a specific subfamily may play more family-specific functional roles and are usually found at functional patches. we expect that a highly supported pattern may highlight the residues that were conserved together during evolution for a particular purpose, for example, interacting with other proteins. the experimental results conducted in this work reveal that the conservation information provided by sequential pattern mining is helpful to this problem before any existing structures are included to facilitate the learning task. this paper investigates the effectiveness of the approach by answering the following two questions: are the locations of the sequential blocks near the interfaces of protein-protein interactions? and do the derived sequential blocks tend to cluster together in space? of course the first question is more related to the objective of this study. but by answering the second question, we expect to make it clearer why the proposed methodology works. we do not address the recall issue in this paper because we are aware of that it might not be possible to identify the complete set of interacting residues by a single pattern or in a single run of mining process. in fact, identifying important residues associated with hot regions is not identical to the problem of predicting interacting residues. as mentioned in the previous paragraphs, not all the interface residues are hot spots and expected to be conserved. on the other hand, some interior residues might also contribute to the stability of the complexes and are thus conserved. this work aims to show that the information provided by sequential pattern mining is useful to discovering hot regions of protein-protein interactions. this information can be refined and incorporated in other approaches to enhance the predicting power of the state of the art predictors.  in this section, we first describe the datasets used in this work and how the patterns are selected for different experiments. using the five proteins in the first dataset, we investigate the potential of sequential pattern mining in identifying hot regions of protein-protein interactions by examining carefully the discovered patterns. to illustrate the advantages of our method, we compare our results with consurf's results. next, we use the protein chains of the second dataset to evaluate the general performance of the proposed method. the details of the datasets and the experimental procedures are described in the following subsections. datasets pattern selection for the first dataset, the top ten large-size patterns are examined for the mining results of each query protein. the size of a pattern is defined as the number of conserved residues it contains. in the first experiment, it is observed in every case that the hot regions can be revealed directly by the maximum-size pattern. thus in the second experiment, we investigate how the maximum-size pattern of each query protein performs in identifying protein interacting regions automatically. results on the first dataset the performance of the proposed methodology is evaluated from two aspects. first, the effectiveness of identifying hot regions is evaluated. second, the efficiency of the pattern mining algorithm is compared with consurf, where multiple sequence alignment is employed in identifying conserved residues. in addition, the conservation plots generated by consurf are included for comparison. the mining results for the five proteins in the first dataset are shown in figure in that the patterns are plotted on the complexes for easy visualization. in these figures, the discovered conserved blocks are shown in sticks representation. in most cases, all the sequential blocks of the pattern cluster in one region of the protein and form the substructure associated with the interface of the complex. differently, for the protein grpe in figure the conserved blocks form two hot regions that together constitute the interacting interface. the conservation plots generated by magiic-pro are compared with that produced by consurf, as shown in figure the conservation information suggested by consurf might be too noisy to predict hot regions directly from the sequences. it would be helpful if the structures of complexes are available as suggested by armon et al. and lichtarge et al. in their papers. finally, table shows the executing time for magiic-pro and consurf respectively. results on the second dataset the summary of the experimental results on the second dataset is provided in table while the details can be found in the online supplement of this paper. among the protein chains in the second dataset, two protein chains are excluded from the test set because the protein sequence of the protein chain is not available in the pdb file and the protein chain does not have enough homologues for pattern mining. as listed in table magiic-pro successfully generated patterns for protein chains. for each chain, we selected the pattern with the most components as the prediction of hot regions. since only patterns with at least two blocks are reported, a maximum-size pattern always has two or more blocks to examine. here we define two indices to evaluate the quality of a pattern: clustering propensity: the percentage of sequential blocks in a pattern p that interacts with at least one of the other blocks in p. the interaction between a pair of blocks is defined by the following criterion: there exists an atom from one block that is within Å to an atom of the other block. interface propensity: the percentage of sequential blocks in a pattern p that contacts another protein chain in the complex. the definition of contact is that any of the atoms from the block is within Å to any atom of another protein chain in the complex. the clustering propensity of a pattern reflects its reliability. we consider that a higher value of this index indicates that the pattern is more biologically meaningful, either from function or structure point of view. for each query protein, the clustering and interface propensities are calculated for its maximum-size pattern. the average values for different categories of protein complexes are provided in table the group of enzyme-inhibitor complexes slightly outperforms the other categories. it can be seen in table that the results on the non-redundant set are similar. when creating the non-redundant set, the program cd-hit was applied directly to the protein chains to avoid selecting the protein chains that failed to deliver patterns as the representatives. similar conclusion can be made from table as summarized in table there are about 66% of the derived blocks close to the contacting areas of protein-protein interactions. furthermore, there are about 92% of the blocks clustering with at least one of the other blocks to form protein substructures in space. it is observed in some cases that some clustered but non-interacting blocks are actually the binding sites of other molecules. in table we show the statistics about the number of blocks of the maximum-size patterns for the protein chains. the number of blocks that contribute to interface is further collected in table in table it is of interest to check the number of proteins whose maximum-size pattern discovers at least two or three interacting blocks. the percentages are 83% and 54% respectively. we conclude that most of the tested proteins can be benefited by this approach, and similar records are observed on the non-redundant set in table  conservation information is important in predicting hot regions involved in protein-protein binding. however, the conservation information at residue level is not sufficient in predicting hot regions because not all the reported residues are conserved for the same purpose. the conservation information derived by the pattern mining approach is more precise than that generated by multiple sequence alignment followed by constructing the evolutionary tree. that is, the concurrence of conserved blocks among a subset of protein homologues is focused. the experiments conducted in this paper reveal that the derived conserved blocks tend to cluster together in space and most of the aggregated blocks are related with interacting interfaces. the detected regions possess high conservation and thus are considered as the computational hot regions. by using sequential pattern mining, it may be possible to predict hot spots of an interface without exhaustive mutagenesis and thermodynamic analysis and thus the link between protein functions and their primary sequences can be constructed much more rapidly. 
it is observed that a functional region of protein structures usually consists of several peptide segments linked with large wildcard regions. the experiments conducted in this work demonstrate that the derived long patterns automatically discover the important residues that form one or several hot regions of protein-protein interactions. about 92% of the derived blocks are observed to be clustered in space with at least one of the other blocks, and about 66% of the blocks are found to be near the interface of protein-protein interactions. this work aims to demonstrate that the important residues associated with the interface of protein-protein interactions may be automatically discovered by sequential pattern mining. as more and more protein sequences are deposited without available structural information, it is strongly desirable to predict protein binding regions by their sequences alone. a derived pattern is called a cluster-like pattern since the discovered conserved residues are always grouped into several blocks, which each corresponds to a local conserved region on the protein sequence. this information would be useful to characterizing protein sequences, predicting protein function, finding potential partners, and facilitating protein docking for drug discovery. the detected regions possess high conservation and thus are considered as the computational hot regions. the methodology is evaluated by conducting experiments on the web server magiic-pro based on a well known benchmark containing protein chains from distinct complexes. among the tested proteins, there are sequential blocks discovered, blocks per protein chain on average.
 identification of protein interacting sites is an important task in computational molecular biology. as more and more protein sequences are deposited without available structural information, it is strongly desirable to predict protein binding regions by their sequences alone. this paper presents a pattern mining approach to tackle this problem. it is observed that a functional region of protein structures usually consists of several peptide segments linked with large wildcard regions. thus, the proposed mining technology considers large irregular gaps when growing patterns, in order to find the residues that are simultaneously conserved but largely separated on the sequences. a derived pattern is called a cluster-like pattern since the discovered conserved residues are always grouped into several blocks, which each corresponds to a local conserved region on the protein sequence.  the experiments conducted in this work demonstrate that the derived long patterns automatically discover the important residues that form one or several hot regions of protein-protein interactions. the methodology is evaluated by conducting experiments on the web server magiic-pro based on a well known benchmark containing protein chains from distinct complexes. among the tested proteins, there are sequential blocks discovered, blocks per protein chain on average. about 92% of the derived blocks are observed to be clustered in space with at least one of the other blocks, and about 66% of the blocks are found to be near the interface of protein-protein interactions. it is summarized that for about 83% of the tested proteins, at least two interacting blocks can be discovered by this approach.  this work aims to demonstrate that the important residues associated with the interface of protein-protein interactions may be automatically discovered by sequential pattern mining. the detected regions possess high conservation and thus are considered as the computational hot regions. this information would be useful to characterizing protein sequences, predicting protein function, finding potential partners, and facilitating protein docking for drug discovery. 2– april the tenth annual international conference on research in computational biology venice, italy 