Abstract
A protein and a ligand have a process of recognizing each other when they are remote before approaching for binding. In this process, there should be a local portion corresponding to a target of the recognition (a recognition spot) on the protein molecular surface. In this paper, we proposed a new biclustering algorithm BISERS for predicting recognition spots on protein molecular surfaces, in which a portion of the molecular surface of a query protein that frequently shows the similarity to other specific proteins binding to the similar ligand is extracted by biclustering. In BISERS, the similarity between rows as well as the similarity between columns is introduced into the evaluation function for updating the biclusters. In addition, the random sampling is applied to the process of exclusive selection of the column for reducing the computational cost effectively. Experimental results for 60 proteins show the effectiveness of our BISERS algorithm.
Introduction
Since protein is one of the important biological molecules for life phenomenon, understanding the functions of proteins is fundamental to biomedical science. Proteins often show their functions by binding to other compounds (ligands) on protein molecular surfaces. Since hotspot residues play an important role on binding process, so far, many computational methods for predicting the hotspots have been proposed [1] - [4] . On the other hand, a protein and a ligand have a process of recognizing each other when they are remote before approaching for binding. In this process, there should be a local portion corresponding to a target of the recognition (a recognition spot), which is not necessarily the same as a hotspot, on the protein molecular surface.
Introduction
We have proposed a method of predicting a protein recognition spot based on the idea that the recognition spots observed from the proteins binding to similar compounds have some frequently shared features [5] . This method consists of three steps. The first step is extraction of feature points from protein molecular surfaces. In this process, feature points are extracted based on curvature-based approach [6] in the form of point feature histograms [7] with physical properties such as electrostatic potential and hydrophobicity. In the second step, structures of proteins, namely sets of feature points located on the 3D space, are compared and a list of matched feature points is derived from the results of pattern matching between a query protein, which is one whose recognition spot is unknown, and each of the reference proteins, which are proteins whose binding ligands have been analyzed. A matched point matrix, which is a binary matrix that shows correspondences between feature points of the query protein and the reference proteins, is generated by aggregating the lists of matched feature points for all of reference proteins. In the final step, the recognition spot is extracted by biclustering of the matched point matrix. In this process, we have to consider the similarity between columns, since columns in the matched point matrix correspond to reference proteins, which can be classified by prior knowledge. In addition, the exclusive selection of column is required, because more than one columns correspond to the same reference protein. In other words, the bicluster that is composed of columns from the same reference protein is meaningless. Therefore, we have proposed a new biclustering algorithm BISES ((BIclustering based on Similarity and Exclusive Selection of column) [5] , in which the similarity between columns and the exclusive selection of a column are considered.
Introduction
However, our BISES has the following two drawbacks. The first is that the feature points located distantly each other are included in a bicluster generated by BISES. In general, the recognition spot seldom consists of distantly located portions. The second is the computational issue. In BISES, the concept of the group of columns is introduced and one column is selected from each group in updating the bicluster. Although only the combination of selected columns with the highest evaluation value is proceeded to the next step in the greedy manner, the number of combination becomes huge as the size of the data set scales up, which requires large computational resources.
Introduction
In this paper, we propose a new biclustering algorithm BISERS (BIclustering based on Similarity and Exclusive Random Selection of column), which is a modified version of BISES. In BISERS, the similarity between rows, which correspond to feature points in the query protein, as well as the similarity between columns is introduced into the evaluation function for updating the biclusters. In addition, the random sampling is applied to the process of exclusive selection of the column for reducing the computational cost effectively.
Introduction
The rest of this paper is organized as follows. Section 2 briefly describes the method for predicting the protein recognition spots and gives an example of the matched point matrix that is a target of biclustering. In section 3, we present the algorithm BISERS. Section 4 gives experimental results and discussions. Fig. 1 shows a general flow of a method for predicting recognition spots. The first step is extraction of feature points from a protein molecular surface represented as a set of polygon data consisting of the points in 3D space along with physical properties such as hydrophobicity and electrostatic potential. Fig. 2 illustrates an example of the original protein molecular surface and a set of feature points extracted from it. The second step is matching feature points between a query protein and each of reference proteins. In this step, a set of feature points of the query protein and a set of feature points of the reference protein are given, then a list of corresponding feature points in 3D space between a subset from the query feature points and a subset from the reference feature points is generated. An example of the result of matching is shown in Fig. 3 , where the numbers are IDs of the feature points. In this figure, more than one correspondences are shown as 'TOP x' in descending order of the number of corresponding feature points. Since we have many reference proteins, a matched point matrix is generated as a final result of this step by composing of all of the list. Fig. 4 shows an example of the matched point matrix, in which '1' indicates that there is a correspondence between a feature point in the query and the reference proteins.
Overview of Method for Recognition Spots Prediction
In the final step, important feature points are extracted as a bicluster. In other words, feature points in the query protein that have common correspondences to the feature points from the specific reference proteins are significant and regarded as a candidate of the recognition spot. 
International Journal of Bioscience, Biochemistry and Bioinformatics
In this paper, we focus on the final step and propose a method of generating an appropriate bicluster from a matched point matrix.
Biclustering Algorithm with Exclusive Random Selection of Columns

BISES
The matched point matrix has the following characteristics.

Each column represents a reference protein, which can be classified based on various viewpoints.

Each row corresponds to a feature point in a query protein, which means that the row has spatial information in 3D space.

One or more columns correspond to the same reference protein.

BISES, a previous version of biclustering algorithm we have proposed, is based on the algorithm PDNS (Pattern-Driven Neighborhood Search) proposed by Ayadi et al. [8] , in which biclusters are evaluated by correlations of rows and columns and are incrementally updated, namely adding or removing rows and columns, by neighborhood search. BISES introduces the inter-column similarity and the exclusive selection from 'group of columns' in order to deal with the first and the last points mentioned above, but does not consider second point. In addition, BISES encounters computational problem derived from combinatorial explosion for exclusive selection of a column.
BISERS

Evaluation function
To cope with the above-mentioned problems of BISES, we propose a new biclustering algorithm BISERS, which introduces the inter-row similarity as well as inter-column similarity. A row in the matched point matrix corresponds to a feature point that has coordinate values in 3D space. Since the feature points composing recognition spots tend to be closely located, biclusters that include locally arranged feature points should be obtain high evaluation values. Therefore, we define the inter-row similarity ( , ) based on the distance in 3D space between feature points as follow.
Evaluation function
where ( , ) is the distance in 3D space between two feature points p i and p j associated with rows indices i and j in the matched point matrix. On the other hand, each column represents a reference protein. We evaluate the similarity between columns based on the similarity between ligands that the corresponding reference proteins bind to. We use the ligand similarity that has been presented in COMPLIG algorithm proposed by Saito et al. [9] for evaluating inter-column similarity ( , ) as follows.
Evaluation function
where and are the numbers of atoms in ligands M and N respectively, and and are the numbers of bonds in ligands M and N respectively. and are the numbers of matched atoms and matched bonds that are calculated by COMPLIG.
Evaluation function
In PDNS algorithm [8] , the bicluster B(I, J) (I is a set of rows and J is a set of columns included in the bicluster) is evaluated by Average Spearman's Rho (ASR) defined as follows. ),
Evaluation function
International Journal of Bioscience, Biochemistry and Bioinformatics where ( ≠ ) is the Spearman's rank correlation between the rows indices i and j and ( ≠ ) is the Spearman's rank correlation between the columns indices k and l. In BISERS, since the bicluster that includes many rows with high inter-row similarity or many columns with high inter-column similarity is expected to be generated, the modified evaluation function ASR-S (Average Spearman's Rho with Similarity), in which weighted correlation values of rows and columns are introduced into ASR, is defined as follows. .
ASR-S( ) =
∑
Efficient exclusive selection of column
As a result of updating the current bicluster in terms of the column, the updated bicluster might include more than one columns generated from the same reference protein. Since such a bicluster is meaningless, the columns derived from the same protein are grouped and one column at most has to be selected from the group and combined with other columns. In other words, multiple combinations of selected columns have to be considered. For each of them, rows are updated and the value of ASR-S is evaluated. Ideally, the bicluster with the highest ASR-S value is chosen from the all combinations for the next updating step, and these processes are iterated. In this iteration process, however, combinatorial explosion is serious, which prevents practical execution.
Efficient exclusive selection of column
Therefore, in BISERS, only one column is randomly selected from each group without enumerating all combinations in order to generate an updated bicluster. Instead of considering exhaustive combinations, this random sampling process is repeated to get various biclusters. After each generated bicluster is updated in terms of rows, the best bicluster with the highest ASR-S value is proceeded to the next step. The number of random sampling S is defined as follows.
Efficient exclusive selection of column
where n is the number of groups, c i is the number of columns in group i, and S 0 is a constant value. This process is illustrated in Fig. 5 and the algorithm of BISERS is described in Fig. 6 . 
Experimental Results

Data Set

International Journal of Bioscience, Biochemistry and Bioinformatics
We made experiment with data set including 60 proteins shown in Table 1 , four types of proteins binding to each of 15 types of ligands in order to confirm the effectiveness of BISERS. In this table, protein is specified with four letter PDB-ID with one letter chain ID and the number in the parentheses indicates the number of feature points on the molecular surface. 
Effectiveness of Random Sampling

International Journal of Bioscience, Biochemistry and Bioinformatics
First, we confirm the effectiveness of random sampling for the exclusive selection of columns from the viewpoint of the execution time and the accuracy of the results. The accuracy of the results is evaluated by calculating precision, which is the rate of extracted feature points that correspond to residues known to associate with binding in the Protein Data Bank (PDB) [10] . If the residue that is the closest to the extracted feature point is consistent with the residue in actual binding site specified in the PDB data, we judge that the feature point is extracted as the actual binding successfully.
International Journal of Bioscience, Biochemistry and Bioinformatics
BISERS was compared with the method without random sampling, namely all combinations of exclusive selection of columns from each group. Since the latter method takes much execution time for the original dataset mentioned above, we used subsets for this experiment. Fig. 7 and Table 2 show the average precision and calculation time based on ten times of trials for each method. In this table, the average number of the extracted feature points is also shown. While we can observe no significant differences in terms of the precision as well as the number of extracted feature points between two methods, the computational cost of the proposed method with random sampling is extremely reduced, which implies the effectiveness of the proposed method. 
Comparison with Other Biclustering Methods
A query protein is selected out of 60 proteins in the data set and the rest are treated as reference proteins. We prepare two types of matched point matrix from the results of matching feature points. One is the matrix consisting of only TOP 1 column for each of the reference proteins. The other consists of not only TOP 1 but also TOP 2 and 3 columns. Bimax [11] , BiBit [12] , PDNS [8] , BISES [5] and BISERS are applied to the former matrix, which requires no exclusive selection of a column. BISES and BISERS are applied to the latter matrix. In BISERS, the initial bicluster B 0 has four rows and four columns at least, and other parameters are = = 0.6, = = 10, = 30 and S 0 = 100.
Comparison with Other Biclustering Methods
The average precision and the average size of the generated bicluster for 60 query proteins are shown in Table 3 . The size of the bicluster is defined as the product of the number of the feature points and the number of reference proteins in the bicluster. For the matched point matrix containing only TOP 1 columns, BISERS shows the highest average precision, which tells that BISERS considering both the inter-row similarity and the inter-column similarity is effective than some existing biclustering methods. In addition, BISERS considering the exclusive selection from TOP 1, 2, and 3 columns gives the highest precision, which suggests the use of multiple matching results is very significant for predicting the recognition spot from the matched point matrices.
Conclusions
International Journal of Bioscience, Biochemistry and Bioinformatics

{'paper_id': '54496454', 'title': 'A New Biclustering Algorithm with Exclusive Random Selection of Columns for Predicting Recognition Spots on Protein Molecular Surfaces', 's2_url': 'https://api.semanticscholar.org/CorpusID:54496454', 'source': 'S2ORC'}