<title>Background</title> <p>The development of automated methods for inferring functional association of proteins from sequence and genomic data is becoming an increasingly important area of investigation in bioinformatics and computational biology. In effect, the determination of unknown gene interactions in functional pathways and perhaps, their association with diseases, relies crucially on sound computational algorithms capable of producing meaningful predictions.</p> <p>The homology-based methods are useful to assign function to proteins by establishing sequence similarity of the underlying sequences with others with previously assigned function [##REF##14681450##1##]. There is a variety of those homology-based methods that use specific aspects of similarity between protein attributes, such as similarity between complete sequences [##REF##12051862##2##, ####UREF##0##3##, ##REF##10704319##4####10704319##4##], presence of motifs and functional blocks [##REF##9016540##5##], specific spatial positions of functional residues [##REF##9719646##6##,##REF##9385633##7##] or combinations of the aforementioned [##UREF##1##8##].</p> <p>However, when similarity of the underlined sequences is not sufficiently significant, alternative approaches have been considered. Several non homology-based methods have been developed to predict functional relationships between proteins [##REF##15193308##9##,##REF##10866208##10##], using additional sources of genomic information [##REF##16507154##11##, ####REF##12169557##12##, ##REF##16385560##13####16385560##13##]. These methods have been called application-based in context, and they include phylogenetic profiles, protein fusions (Rosetta Stone), gene coexpresion, and neighborhood conservation [##REF##10866208##10##]. It has been demonstrated that functional relationships, functional modules, molecular networks and genotype-phenotype relationships can be accurately predicted using these methods [##REF##10866208##10##].</p> <p>Among modern post-genomic approaches developed in recent years, those based on the correlated presence and absence of genes (i. e. phylogenetic profiles) among a collection of organisms have proven to be particularly effective [##REF##10200254##14##,##REF##12794638##15##]. Theoretically, with the increasing availability of complete genome sequences from more organisms, these methods hold the promise of increasing efficacy. Particularly, phylogenetic profiles have been successfully used for assigning protein function, for localizing proteins in cells, for reconstructing metabolic pathways, and for phylogenetic studies, among other applications [##REF##16507154##11##,##REF##12912833##16##, ####REF##14571375##17##, ##REF##12169563##18####12169563##18##].</p> <p>Predictions obtained from phylogenetic profiles depend critically on the employed clustering method. Most clustering algorithms used to date are based on the calculation of Euclidean and Hamming distances between pair of elements [##REF##15128446##19##], which means that the clustering is directed by the intrinsic properties of these patterns and no additional information is often considered, albeit there are few exceptions [##REF##14571375##17##]. For example, other studies have employed a variety of metrics such as intergenic distance [##REF##12169563##18##] and kernels [##REF##16507154##11##]. It is known that proteins do not only interact by pairs [##UREF##2##20##]. For example, in the case of metabolic pathways, a biologically meaningful function is normally performed by a group of proteins. Also, our previous work demonstrated that often proteins can have functional analogs with no sequence similarity that can displace each other [##REF##12794638##15##]. Thus, in order to predict a link, it is necessary to employ a method capable of considering not only a direct but also an indirect relationship created by the association with a third party element. The Bond Energy Algorithm (<italic>BEA</italic>) is a widely used methodology to create vertical fragmentation of distributed databases. This algorithm creates a collection of clusters based on the relationships of the surrounding elements of the analyzed data in a particular cluster using an non-trivial Attribute Affinity measure, which is a weight matrix denoting the strength of the relationship among all the elements in the data set. We would like to posit here that non obvious relationships can be predicted by this method when an apparently non related element is linked to another one by a third element [##UREF##3##21##,##REF##17044165##22##]. <italic>BEA </italic>uses a two step approach to clustering: the first step is the ordering algorithm, while the second step is the grouping algorithm.</p> <p>Despite its clustering capabilities, <italic>BEA </italic>has only recently been used in bioinformatics studies [##REF##17044165##22##]. We propose a new method for clustering phylogenetic profiles, consisting in applying <italic>BEA</italic>, to predict functional associations of profiles and to detect displacements of functionally equivalent analog proteins. Here we show that <italic>BEA </italic>can detect functional associations between profiles not detected by conventional methods. A major goal of this work is to explore the extent in which the prediction of protein functional interactions can be accurately inferred from protein phylogenetic profiles. Therefore, we have focused on improving the clustering of these patterns by using implicit information not considered by most clustering methods. It is also possible to consider explicit domain knowledge in order to improve results in all clustering algorithms (e.g. an underlying metric incorporating knowledge constraints). Similarly, a consequence of our study is to find whether or not the implicit information derived from phylogenetic patterns is useful for inferring functional interactions without the resort of additional domain knowledge.</p>
<title>Methods</title> <title>Data sets</title> <p>We employed a collection of different data sets for conducting the experiments and validations reported here.</p> <title>Clusters of Orthologous Groups (COG) phylogenetic patterns [##UREF##9##30##]</title> <p>This data set consists of a phylogenetic classification of proteins encoded in complete genomes. <italic>COGs </italic>were identified by comparison of protein sequences from 43 complete genomes, representing 30 major phylogenetic lineages.</p> <p>In order to extract the maximum amount of information from the rapidly accumulating genome sequences, all conserved genes need to be classified according to their homologous relationships. Comparison of proteins encoded in seven completely sequenced genomes from five major phylogenetic lineages and elucidation of consistent patterns of sequence similarities allowed the delineation of 720 clusters of orthologous groups (<italic>COGs</italic>).</p> <p>Specifically, each <italic>COG </italic>consists of individual orthologous proteins or set of orthologous from at least three lineages. Orthologous typically have the same function, allowing transfer of functional information from one member to an entire <italic>COG</italic>. This relation automatically yields a number of functional predictions for poorly characterized genomes. The <italic>COGs </italic>comprise a framework for functional and evolutionary genome analysis [##REF##9381173##23##,##REF##11125040##24##]. In this classification, the protein group is classified by functional category, as shown in Table ##TAB##7##8##.</p> <title>Database of Interacting Proteins (DIP) [##UREF##14##36##]</title> <p>The <italic>DIP </italic>database catalogs experimentally determined interactions between proteins. It combines information from a variety of sources to create a single, consistent set of protein-protein interactions. The data stored within the <italic>DIP </italic>database were curated, both, manually by expert curators and also automatically using computational approaches that utilize the knowledge about the protein-protein interaction networks extracted from the most reliable, core subset of the <italic>DIP </italic>data [##REF##14681454##37##,##REF##11752321##38##].</p> <title>ECOCYC [##UREF##15##39##]</title> <p><italic>EcoCyc </italic>is a bioinformatics database that describes the genome and the biochemical machinery of <italic>E. coli K-12 MG1655</italic>. The long-term goal of the project is to describe the molecular catalog of the <italic>E. coli </italic>cell, as well as the functions of each of its molecular parts, to facilitate a system-level understanding of <italic>E. coli</italic>. <italic>EcoCyc </italic>is an electronic reference source for <italic>E. coli </italic>biologists, and for biologists who work with related microorganisms.</p> <p><italic>EcoCyc </italic>contains the complete genome sequence of <italic>E. coli</italic>, and describes the nucleotide position and function (if known) of every <italic>E. coli </italic>gene. A staff of five fulltime curators update the annotation of the <italic>E. coli </italic>genome on an ongoing basis using a literature-based curation strategy. Users can retrieve the nucleotide sequence of a gene, and the amino-acid sequence of a gene product.</p> <p><italic>EcoCyc </italic>describes all known metabolic pathways and signal-transduction pathways of <italic>E. coli</italic>. it describes each metabolic enzyme of <italic>E. coli</italic>, including its cofactors, activators, inhibitors, and subunit structure [##REF##11752253##40##,##REF##15608210##41##].</p> <title>Algorithms</title> <p>The Bond Energy Algorithm (<italic>BEA</italic>) has been widely used for vertical fragmentation of distributed databases. This algorithm was originally proposed by McCormick and Hoffer and Severande [##UREF##16##42##]. <italic>BEA </italic>creates clusters using a non-trivial similarity metric (attribute affinity measure) defined on the elements of the data set. In consequence, diffcult relationships in which a third element is needed to make the relationship obvious can be discovered by this method (e. g. transitive relationships).</p> <p><italic>BEA </italic>is comprised by two algorithms, the first one is used for ordering the data set to locate the most related elements close together (and to separate the unrelated elements) and the second one is used for creating the groups to determine at what point has to make a cut on the ordered data set (i.e. create a cluster).</p> <title>The BEA Ordering Algorithm</title> <p>The fundamental task in designing a distributed databases vertical fragmentation algorithm is to find some means of grouping the attributes of a relation table) based on the attribute affinity values in <italic>AA </italic>(Attribute Affinity Matrix). It has been suggested by [##UREF##17##43##] and [##UREF##18##44##] that (<italic>BEA</italic>) [##UREF##16##42##] should be used for this purpose. It is considered appropriate for the following reasons [##UREF##17##43##]:</p> <p>1. It is designed specifically to determine groups of similar items and opposed to, say, a linear ordering of the items (i.e., it clusters the attributes with large affinity values together, and the ones with smaller values together).</p> <p>2. The final groupings are insensitive to the order in which items are presented to the algorithm.</p> <p>3. The algorithm complexity is similar to other methods but can have better results [<italic>O</italic>(<italic>n</italic>2), where <italic>n </italic>is the number of attributes].</p> <p>4. Secondary interrelationships between clustered attribute groups are identifiable.</p> <p>The bond energy algorithm takes as input the attribute affinity matrix, permutes its rows and columns, and generates a clustered affinity matrix (<italic>CA</italic>). The permutation is done in such a way as to maximize the following global affinity measure (<italic>AM</italic>):</p> <p></p> <p>where</p> <p></p> <p>The last set of conditions takes care of the cases where an attribute is being placed in <italic>CA </italic>to the left of the leftmost attribute or to the right of the rightmost attribute during column permutations, and prior to the topmost row and following the last row during row permutations. In these cases, we take 0 to be the <italic>aff </italic>values between the attributes being considered for placement and its left or right (top or bottom) neighbors, which do not exist in <italic>CA</italic>.</p> <p>The maximization function considers the nearest neighbors only, thereby resulting in the grouping of large values with large ones, and small values with small ones. Also, the attribute affinity matrix (<italic>AA</italic>) is symmetric, because is a matrix of all element of the data set similarity values, which reduces the objective function of the formulation above to:</p> <p></p> <p>where <italic>A</italic><sub><italic>i </italic></sub>is an attribute of the relation, <italic>AA </italic>is the Attribute Affinity Matrix, <italic>CA </italic>is the Clustered Affinity Matrix, and <italic>AM </italic>is the Affinity Measure.</p> <p>The generation of the clustered affinity matrix (<italic>CA</italic>) is hold in three steps:</p> <p>1. <italic>Initialization</italic>. Place and fix one of the columns of <italic>AA </italic>arbitrarily into <italic>CA</italic>. Column 1 was chosen in the algorithm.</p> <p>2. <italic>Iteration</italic>. Pick each of the remaining <italic>n</italic>-<italic>i </italic>columns (where <italic>i </italic>is the number of columns already placed in <italic>CA</italic>) and try to place them in the remaining <italic>i </italic>+ 1 positions in the <italic>CA </italic>matrix. Choose the placement that makes the greatest contribution to the global affinity measure described above. Continue this step until no more columns remain to be placed.</p> <p>3. <italic>Row ordering</italic>. Once the column ordering is determined, the placement of the rows should also be reordered to make their relative positions match the position of the columns.</p> <p>For the second step of the algorithm to work, we need to define what is meant by the contribution of an profile to the affinity measure. This contribution can be derived as follows. Recall that the global affinity measure <italic>AM </italic>was previously defined as</p> <p></p> <p>which can be rewritten as:</p> <p></p> <p>Let us define the bond between two attributes <italic>A</italic><sub><italic>x </italic></sub>and <italic>A</italic><sub><italic>y </italic></sub>as</p> <p></p> <p>This is where <italic>BEA </italic>find indirect relationships.</p> <p>Then <italic>AM </italic>can be written as:</p> <p></p> <p>Now consider the following <italic>n </italic>attributes:</p> <p></p> <p>The global affinity measure for these attributes can be written as:</p> <p></p> <p>Now we consider placing a new attribute <italic>A</italic><sub><italic>k </italic></sub>and <italic>A</italic><sub><italic>j </italic></sub>in the clustered affinity matrix. The new global affinity measure can be similarly written as:</p> <p></p> <p>where <italic>AM' </italic>is the Affinity Measure before the insert position, <italic>AM" </italic>is the Affinity Measure after the insert position, <italic>bond</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>) is the Bond Energy Evaluation for the insertion of the elements, and <italic>bond</italic>(<italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>) is the Bond Energy Evaluation for the separation of the elements.</p> <p>Thus, the next contribution to the global affinity measure of placing attribute <italic>A</italic><sub><italic>k </italic></sub>between <italic>A</italic><sub><italic>i </italic></sub>and <italic>A</italic><sub><italic>j </italic></sub>is:</p> <p></p> <p>The input data for our experiments were Phylogenetic Profiles, this means that the entries are strings of <italic>1's </italic>and <italic>0's </italic>that shows the presence or absence of a certain protein in some organisms, in which every column represented a gene and every row was an organism. The Hamming distance between pairs of phylogenetic profiles was used to calculate the entries of the Attribute Affinity Matrix (<italic>AA</italic>) that represents the relationship between proteins.</p> <p>Then we run the algorithm as follows:</p> <p><bold>input</bold>: Phylogenetic Profiles.</p> <p><bold>output</bold>: <italic>CA</italic>: Clustered Affinity matrix and order list array.</p> <p>begin</p> <p>   [initialize; the AA matrix is created]</p> <p>   <italic>CA</italic>(•, 1) ← AA(•, 1)</p> <p>   CA(•, 2) ← AA(•, 2)</p> <p>   <italic>index </italic>← 3</p> <p>   <bold>while </bold><italic>index </italic>≤ <italic>n </italic><bold>do </bold>[choose the "best" location for profile <italic>AA</italic><sub><italic>index</italic></sub>]</p> <p>   <bold>begin</bold></p> <p>      <bold>for </bold><italic>i </italic><bold>from </bold>1 <bold>to </bold><italic>index </italic>- 1 <bold>by </bold>1 <bold>do</bold></p> <p>         calculate <italic>cont</italic>(<italic>AA</italic><sub><italic>i</italic>-1</sub>, <italic>AA</italic><sub><italic>index</italic></sub>, <italic>AA</italic><sub><italic>i</italic></sub>)</p> <p>      <bold>end-for</bold></p> <p>      calculate <italic>cont</italic>(<italic>AA</italic><sub><italic>index</italic>-1</sub>, <italic>AA</italic><sub><italic>index</italic></sub>, <italic>AA</italic><sub><italic>index</italic>+1 </sub>[boundary condition]</p> <p>      <italic>loc </italic>← placement given by maximum <italic>cont </italic>value</p> <p>      <bold>for </bold><italic>j </italic><bold>from </bold><italic>index </italic><bold>to </bold><italic>loc </italic><bold>by </bold>-1 <bold>do </bold>[shuffle the two matrices]</p> <p>         calculate <italic>CA</italic>(•, j) ← <italic>CA</italic>(•, <italic>j </italic>- 1)</p> <p>      <bold>end-for</bold></p> <p>      <italic>CA</italic>(•, <italic>loc</italic>) ← <italic>AA</italic>(•, <italic>index</italic>)</p> <p>      <italic>index </italic>← <italic>index </italic>+ 1</p> <p>   <bold>end-while</bold></p> <p>   order the rows according to the relative ordering of columns</p> <p><bold>end</bold>.</p> <p>Note: • means for each element in the data set.</p> <title>The BEA Grouping Algorithm</title> <p>Once <italic>BEA </italic>ordering algorithm was executed on the input data, the <italic>CA </italic>matrix must be grouped, for this propose we used a "guilty by association" method based on <italic>COG</italic>'s functional categories. Particularly, the unknown function of a protein was transferred from the neighbor proteins with characterized function in the <italic>CA</italic>[##REF##10977076##45##,##REF##11101803##46##].</p> <p>Especifically,</p> <p>if <italic>i </italic>+ 1 and <italic>i </italic>- 1 category is known and <italic>category</italic>(<italic>i </italic>- 1) is equal to <italic>category</italic>(<italic>i </italic>+ 1) then <italic>category</italic>(<italic>i</italic>) = <italic>category</italic>(<italic>i </italic>- 1)</p> <p>where <italic>i </italic>is the position in the ordered matrix.</p> <p>The cutting point is calculated when a change in the classification occurs.</p> <p>We repeat the cut process until reaching the total number of elements in the <italic>CA </italic>matrix.</p> <title>Validations</title> <p>Our validations were made using the above mentioned data sets: the <italic>COG's </italic>functional categories for testing <italic>BEA </italic>ordering algorithm; and the <italic>DIP </italic>and <italic>ECOCYC </italic>databases were used as additional data sets for testing accuracy of <italic>BEA </italic>grouping algorithm.</p>
<title>Results and Discussion</title> <title>Experiments</title> <p>The first version of the <italic>COG </italic>database provides a collection of 3307phylogenetic profiles [##REF##9381173##23##,##REF##11125040##24##]. Using this information we conducted a series of computational simulations with <italic>BEA </italic>and compared our results with those produced by other clustering methods, such as <italic>k</italic>-means, Hierarchical Clustering and Partition Around Medoids (<italic>PAM</italic>).</p> <p>A predefined collection of input parameters is required by most clustering algorithms. The number of clusters, the initial position of cluster centers, and the distance metric, are typically provided as input to the clustering algorithm. Appropriate values for parameters are often determined empirically, especially, when there is little information on the underlying structure of the data set. The definition of these parameters is known to be critical for obtaining meaningful clustering results [##UREF##4##25##].</p> <p>For instance, in the <italic>k</italic>-means algorithm we used a random positioning of 18 centers for the clusters. The determination of this number of centers was based on the number of different functional categories described in the <italic>COG </italic>database. Recall that <italic>COG </italic>phlogenetic profiles and <italic>COG </italic>functional categories are independent assessments. The selected metric was the Hamming distance due to the fact that it is a suitable measure for binary data. The accuracy of the algorithm was calculated as the average performance of 10 simulations of the algorithm based on the ten-fold validation method [##UREF##5##26##,##UREF##6##27##]. The Matlab package [##UREF##7##28##] was employed for this experiment.</p> <p>Results produced by <italic>k</italic>-means are typically sensitive to initial conditions. For example, a particular partition of points in which any single point is moved to a different cluster increases the total sum of distances. This problem can be approached by an appropriate choice of starting points. Specifically, we employed a version of the <italic>k</italic>-means algorithm that uses a two-phase iterative algorithm to minimize the sum of point-to-centroid distances, summed over all <italic>k </italic>clusters [##UREF##4##25##].</p> <p>The first phase use "batch" updates, in which each iteration consists of re-assigning points to their nearest cluster centroid, all at once, followed by recalculation of cluster centroid. This phase may be viewed as providing a fast but potentially only approximate solution and as a starting point for the second phase. The second phase use "online" updates, in which points are individually reassigned in the space in order to reduce the sum of distances; cluster centroids are recomputed after each reassignment. Each iteration during this second phase consists of stepwise pass though all the points to assign the new centroids. For the Hierarchical Clustering experiments, we used the R package statistical toolkit (AGNES). AGNES is fully described in [##UREF##4##25##,##UREF##8##29##]. Compared to other agglomerative clustering methods such as "hclus", "agnes" yields the agglomerative coefficient which measures the amount of clustering structure found.</p> <p>The AGNES algorithm constructs a hierarchy of clusters. Initially each observation is a small cluster by itself. Clusters are merged until only one large cluster remains which contains all the observations. At each stage of the algorithm the two nearest clusters are combined to form a single larger cluster. We used the average method in which the distance between two clusters is the average of the dissimilarities between the points in one cluster and the points in the other. The obtained agglomerative coefficient of 0.7788952 provided the basis to cut the branch at the coefficient value. The chosen metric was again the Hamming distance. As mentioned above, we repeated 10 cycles and used the average result of them.</p> <p>For the experiments with <italic>PAM </italic>we also used the R package statistical toolkit. 18 clusters was provided as input parameter to the algorithm as for "<italic>k</italic>-means". <italic>PAM </italic>is a more robust version of <italic>k</italic>-means since it additionally takes a dissimilarity matrix as input. <italic>PAM </italic>algorithm is based on the search for <italic>k </italic>representative objects or medoids among the observations of the data set. These observations should represent the structure of the data. After finding a set of <italic>k </italic>medoids, <italic>k </italic>clusters are constructed by assigning each observation to the nearest medoid. The goal is to find <italic>k </italic>representative objects which minimize the sum of the dissimilarities of the observations to their closest representative object. By default, when medoids are not specified, the algorithm first looks for a good initial set of medoids (this is called the build phase). Then, it finds a local minimum for the objective function, that is, a solution reached until there is not a single switch of an element within a medoid that decreases the objective function (this is called the swap phase). When the medoids are specified, their order is not critical, in general, the algorithms have been designed to be independ of the order of the observations. The metric was set to Manhattan, as before. We hold 10 cycles and took the average result for a better accuracy.</p> <p>In contrast, for the experiments with <italic>BEA</italic>, the number of clusters was automatically created by the cutting method in conjunction with a grouping step based on the "guilty by association" principle. The Hamming was also used for the experiments with <italic>BEA </italic>and we hold 10 cycles, as before.</p> <p>A more detailed description of <italic>BEA </italic>is presented in the Methods section.</p>
<title>Results and Discussion</title> <title>Experiments</title> <p>The first version of the <italic>COG </italic>database provides a collection of 3307phylogenetic profiles [##REF##9381173##23##,##REF##11125040##24##]. Using this information we conducted a series of computational simulations with <italic>BEA </italic>and compared our results with those produced by other clustering methods, such as <italic>k</italic>-means, Hierarchical Clustering and Partition Around Medoids (<italic>PAM</italic>).</p> <p>A predefined collection of input parameters is required by most clustering algorithms. The number of clusters, the initial position of cluster centers, and the distance metric, are typically provided as input to the clustering algorithm. Appropriate values for parameters are often determined empirically, especially, when there is little information on the underlying structure of the data set. The definition of these parameters is known to be critical for obtaining meaningful clustering results [##UREF##4##25##].</p> <p>For instance, in the <italic>k</italic>-means algorithm we used a random positioning of 18 centers for the clusters. The determination of this number of centers was based on the number of different functional categories described in the <italic>COG </italic>database. Recall that <italic>COG </italic>phlogenetic profiles and <italic>COG </italic>functional categories are independent assessments. The selected metric was the Hamming distance due to the fact that it is a suitable measure for binary data. The accuracy of the algorithm was calculated as the average performance of 10 simulations of the algorithm based on the ten-fold validation method [##UREF##5##26##,##UREF##6##27##]. The Matlab package [##UREF##7##28##] was employed for this experiment.</p> <p>Results produced by <italic>k</italic>-means are typically sensitive to initial conditions. For example, a particular partition of points in which any single point is moved to a different cluster increases the total sum of distances. This problem can be approached by an appropriate choice of starting points. Specifically, we employed a version of the <italic>k</italic>-means algorithm that uses a two-phase iterative algorithm to minimize the sum of point-to-centroid distances, summed over all <italic>k </italic>clusters [##UREF##4##25##].</p> <p>The first phase use "batch" updates, in which each iteration consists of re-assigning points to their nearest cluster centroid, all at once, followed by recalculation of cluster centroid. This phase may be viewed as providing a fast but potentially only approximate solution and as a starting point for the second phase. The second phase use "online" updates, in which points are individually reassigned in the space in order to reduce the sum of distances; cluster centroids are recomputed after each reassignment. Each iteration during this second phase consists of stepwise pass though all the points to assign the new centroids. For the Hierarchical Clustering experiments, we used the R package statistical toolkit (AGNES). AGNES is fully described in [##UREF##4##25##,##UREF##8##29##]. Compared to other agglomerative clustering methods such as "hclus", "agnes" yields the agglomerative coefficient which measures the amount of clustering structure found.</p> <p>The AGNES algorithm constructs a hierarchy of clusters. Initially each observation is a small cluster by itself. Clusters are merged until only one large cluster remains which contains all the observations. At each stage of the algorithm the two nearest clusters are combined to form a single larger cluster. We used the average method in which the distance between two clusters is the average of the dissimilarities between the points in one cluster and the points in the other. The obtained agglomerative coefficient of 0.7788952 provided the basis to cut the branch at the coefficient value. The chosen metric was again the Hamming distance. As mentioned above, we repeated 10 cycles and used the average result of them.</p> <p>For the experiments with <italic>PAM </italic>we also used the R package statistical toolkit. 18 clusters was provided as input parameter to the algorithm as for "<italic>k</italic>-means". <italic>PAM </italic>is a more robust version of <italic>k</italic>-means since it additionally takes a dissimilarity matrix as input. <italic>PAM </italic>algorithm is based on the search for <italic>k </italic>representative objects or medoids among the observations of the data set. These observations should represent the structure of the data. After finding a set of <italic>k </italic>medoids, <italic>k </italic>clusters are constructed by assigning each observation to the nearest medoid. The goal is to find <italic>k </italic>representative objects which minimize the sum of the dissimilarities of the observations to their closest representative object. By default, when medoids are not specified, the algorithm first looks for a good initial set of medoids (this is called the build phase). Then, it finds a local minimum for the objective function, that is, a solution reached until there is not a single switch of an element within a medoid that decreases the objective function (this is called the swap phase). When the medoids are specified, their order is not critical, in general, the algorithms have been designed to be independ of the order of the observations. The metric was set to Manhattan, as before. We hold 10 cycles and took the average result for a better accuracy.</p> <p>In contrast, for the experiments with <italic>BEA</italic>, the number of clusters was automatically created by the cutting method in conjunction with a grouping step based on the "guilty by association" principle. The Hamming was also used for the experiments with <italic>BEA </italic>and we hold 10 cycles, as before.</p> <p>A more detailed description of <italic>BEA </italic>is presented in the Methods section.</p>
<title>Conclusion</title> <p>The focus of this study was to improve the prediction capabilities of phylogenetic profiles using <italic>BEA</italic>. Our results showed that <italic>BEA </italic>increases the accuracy of predictions of protein modules with respect to the traditional clustering methods, especially when the underlying phylogenetic patterns are relatively dissimilar. In effect, <italic>BEA </italic>was capable to detect relationships among proteins by relying on the presence or absence of third party proteins. This method is capable of finding relationships such as: if a protein <italic>A </italic>works with protein <italic>C </italic>and protein <italic>B </italic>is an analog of <italic>A </italic>then <italic>A </italic>and <italic>B </italic>will be related though <italic>C</italic>. So <italic>A </italic>and <italic>B </italic>will be functionally equivalent while <italic>A </italic>and <italic>C</italic>, and <italic>B </italic>and <italic>C </italic>will be functionally linked. This study shows that taking into account indirect relationships can be useful for detecting associations between proteins and reconstructing functional modules. If additional criteria is provided, as genomic context information, to classify different levels of relationships, higher level of accuracy could be achieved using <italic>BEA</italic>. Therefore, it will be useful to complement the information provided by phylogenetic profiles with additional genomic context information, such as intergenic distance and experimental data as implemented in GeConT [##UREF##10##32##].</p> <p>This information can be included in the <italic>AA </italic>matrix to create clusters. <italic>BEA </italic>may also be improved by using different criteria for separating clusters to increase the capabilities of the algorithm for detecting genetic circuits for system biology [##UREF##11##33##]. On the one hand, <italic>BEA </italic>has many advantages, such as low processing time and memory requirements. By using the information of the attribute affinity matrix, direct and indirect relationships are considered, so this creates a balanced and more accurate classification. Based on the results presented here, we showed that <italic>BEA </italic>holds much promise to create better classifications for protein relationships and gene function annotation. A limitation of <italic>BEA </italic>from the computational perspective is the greedy nature of the algorithm, such that results are sensitive to the order of the input data. This problem could be solved by using a Genetic Algorithms to optimize the search of the solution space [##UREF##12##34##,##UREF##13##35##].</p>
<p>This is an Open Access article distributed under the terms of the Creative Commons Attribution License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/2.0"/>), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</p> <title>Background</title> <p>Non-homology based methods such as phylogenetic profiles are effective for predicting functional relationships between proteins with no considerable sequence or structure similarity. Those methods rely heavily on traditional similarity metrics defined on pairs of phylogenetic patterns. Proteins do not exclusively interact in pairs as the final biological function of a protein in the cellular context is often hold by a group of proteins. In order to accurately infer modules of functionally interacting proteins, the consideration of not only direct but also indirect relationships is required.</p> <p>In this paper, we used the Bond Energy Algorithm (<italic>BEA</italic>) to predict functionally related groups of proteins. With <italic>BEA </italic>we create clusters of phylogenetic profiles based on the associations of the surrounding elements of the analyzed data using a metric that considers linked relationships among elements in the data set.</p> <title>Results</title> <p>Using phylogenetic profiles obtained from the Cluster of Orthologous Groups of Proteins (<italic>COG</italic>) database, we conducted a series of clustering experiments using <italic>BEA </italic>to predict (upper level) relationships between profiles. We evaluated our results by comparing with <italic>COG's </italic>functional categories, And even more, with the experimentally determined functional relationships between proteins provided by the <italic>DIP </italic>and <italic>ECOCYC </italic>databases. Our results demonstrate that <italic>BEA </italic>is capable of predicting meaningful modules of functionally related proteins. <italic>BEA </italic>outperforms traditionally used clustering methods, such as <italic>k</italic>-means and hierarchical clustering by predicting functional relationships between proteins with higher accuracy.</p> <title>Conclusion</title> <p>This study shows that the linked relationships of phylogenetic profiles obtained by <italic>BEA </italic>is useful for detecting functional associations between profiles and extending functional modules not found by traditional methods. <italic>BEA </italic>is capable of detecting relationship among phylogenetic patterns by linking them through a common element shared in a group. Additionally, we discuss how the proposed method may become more powerful if other criteria to classify different levels of protein functional interactions, as gene neighborhood or protein fusion information, is provided.</p>
<title>Results</title> <p>In this study we used <italic>BEA </italic>to classify phylogenetic profiles obtained from the <italic>COG </italic>database and conduct a series of experiments with experimental and theoretical data such as the <italic>COG </italic>Functional Categories, <italic>DIP</italic>, and <italic>ECOCYC </italic>databases. These tests provide a measurement of the biological significance of our results. We have chosen the aforementioned databases to evaluate our clustering algorithm as they provide a large collection of experimentally confirmed protein-interaction pairs. In addition, these databases are based on COGs, which provide uniformity with respect to the data set used in this study. It would also be interesting to evaluate our predictions with metabolic pathway and/or functional categories which likely will produce similar results. See Table ##TAB##0##1##.</p> <title>Validations with COG functional categories</title> <p>For the first testing, we used the functional categories established by the <italic>COG </italic>database. The individual <italic>COGs </italic>are constructed by grouping putative orthologous by bidirectional best hit in completely sequenced genomes [##UREF##9##30##]. Therefore, we think using <italic>COGs </italic>instead of individual proteins is less prone to classification errors. We tested <italic>BEA </italic>ordering algorithm by calibrating the cutting points by giving the functional category as an input. The functional category of a cluster is calculated by density (the majority of the elements in the cluster that have the same function). <italic>BEA </italic>accuracy was close to 99.90% of correct classification (3307 elements in the existing 18 categories). In effect, 3304 out of 3307 <italic>COGs </italic>were classified satisfactorily in each of the 18 existing categories. In contrast <italic>k</italic>-means classified 30.15% correctly, Hierarchical Clustering obtained 20.38% and <italic>PAM </italic>made 3.33% resulting in a notorious better accuracy for <italic>BEA</italic>.</p> <p>In our previous studies we showed that <italic>COG0611 </italic>(Protein ThiL with Functional Classification H) and <italic>COG1564 </italic>(Protein Thi80 with Functional Classification H) are non homolog proteins with similar functions [##REF##12794638##15##]. In our present study we show that they are related by <italic>COG0352 </italic>(Protein Thiamine monophosphate synthase with Functional Classification H). This means that <italic>COG0611 </italic>and <italic>COG1564 </italic>were close and bonded by <italic>COG0352</italic>. This demonstrates that <italic>BEA </italic>ordering algorithm worked as expected, locating functionally related proteins close together and separating unrelated proteins. However, we expected a diminishing of the accuracy of results as we removed the functional categories as an input to <italic>BEA </italic>ordering algorithm.</p> <title>Validations with DIP</title> <p>For the second testing, we used <italic>DIP </italic>(Database of Interacting Proteins, Additional file ##SUPPL##0##1##). Particularly, 154 protein relationships were used for validations of the different methods [##REF##15718304##31##]. The <italic>DIP </italic>database describes experimentally determined physical interactions between pairs of proteins. Therefore, in this validation we consider that two proteins are related if they belong to the same cluster. If the <italic>DIP </italic>relationship is contained in the same cluster then it is presumed to be a true positive, otherwise the relationship was considered a false negative. A caveat of using <italic>DIP </italic>is that in this database proteins that do not belong to the same functional cluster could physically interact. We also verified if the relationship was close to the neighbor clusters, maximum five, in order to calculate the efficiency of the algorithm. <italic>BEA </italic>accuracy in classification was approximately 62.37% in the same cluster (97 out of 154 <italic>DIP </italic>relationships were correctly classified). In contrast <italic>k</italic>-means classified 46.10% correctly, Hierarchical Clustering obtained 22.73% and <italic>PAM </italic>made 21.43% resulting in a notorious better accuracy for <italic>BEA</italic>.</p> <p>The comparisons for surrounding clusters are shown in Tables ##TAB##1##2##, ##TAB##2##3## and ##TAB##3##4## (Additional file ##SUPPL##1##4##).</p> <title>Validations with ECOCYC</title> <p>For this test, we used the <italic>ECOCYC </italic>database. Specifically, 192 protein relationships were used [##REF##15718304##31##] (Additional file ##SUPPL##2##2##). The <italic>ECOCYC </italic>database shows the relationships between pairs of proteins in <italic>E. coli</italic>. In this validation, we considered that two proteins are related if they belong to the same cluster. If the <italic>ECOCYC </italic>relationship was contained in the same cluster then it was presumed to be a true positive, otherwise this relationship was considered a false negative, as before. We also verified if the relationship is contained in the neighboring clusters using a radius of maximum 5 clusters, in order to analyze the efficiency of the algorithm. Under this validation, 84.37% of the entire data set was classified correctly in the same cluster (162 out of 192 <italic>ECOCYC </italic>relationships were clustered correctly). Compared with the other methods <italic>k</italic>-means classified 50.00% correctly, Hierarchical Clustering obtained 37.50% and <italic>PAM </italic>made 5.73% resulting again in a higher accuracy for <italic>BEA</italic>. The comparisons for surrounding clusters are shown in Tables ##TAB##4##5##, ##TAB##5##6## and ##TAB##6##7## (Additional file ##SUPPL##3##5##).</p> <p>As can be seen in this testing, <italic>BEA </italic>has a higher accuracy in classifying relationships between phylogenetic profiles. However, the capability of <italic>BEA </italic>was not totally exploited as we discuss in the next section.</p> <title>Discussion</title> <p>As shown, the validation with <italic>COG </italic>functional categories obtained a high classification accuracy. However, the purpose of this test was to exclusively validate <italic>BEA </italic>ordering algorithm in order to calibrate the cutting points. This calibration may be seen as a "guilty by association" algorithm based on <italic>COG</italic>'s functional categories. The next two validations were more important, as they were used to test both <italic>BEA </italic>ordering algorithm and to analyze <italic>BEA </italic>grouping algorithm (i. e. the overall performance and organizing of the algorithm. See Figure ##FIG##0##1## and ##FIG##1##2##, Additional file ##SUPPL##4##3##).</p> <p>We compared the three validations and analyzed the data set of the <italic>DIP </italic>and <italic>ECOCYC </italic>to understand the grouping obtained by our method. The analysis concluded that for <italic>DIP</italic>, the 57.80% of the relationship of these proteins are in the same functional category and 42.21% in a different category. This shows us that <italic>BEA </italic>is classifying reasonably well even when the proteins belong to a different functional category, although our method was used for functional category classification. For the <italic>ECOCYC </italic>classification we found that 84.375% belong to the same functional category and 15.625% are in a different functional category and BEA found exactly the same result.</p> <p>One interesting aspect to emphasize is that there should exists several useful classification criteria depending on the abstraction level in the conceptual hierarchy of the biology of organisms to be observed. For example, at the metabolic pathway level a proper classification would include proteins with different functional categories in the same cluster. Therefore, if we perform classifications based exclusively on functional categories then the metabolic pathways would be hardly revealed by this method.</p> <p>Also we analyzed the cluster distribution and concluded that it is well balanced. This implies that the elements of the data set are well distributed among all the clusters as can be seen in Figure ##FIG##2##3##. In the case of the same functional category relationships, we found that <italic>COG0611 </italic>(Protein ThiL with Functional Category H) and <italic>COG1564 </italic>(Protein Thi80 with Functional Category H) are in the same cluster and they are related by <italic>COG0352 </italic>(Protein Thiamine monophosphate synthase with Functional Category H). This shows that when proteins belong to the same functional category, then they will be located close together in the <italic>CA </italic>matrix. Also, we found that the relationship of <italic>COG3052 </italic>(Protein ThiE with Functional Category H), and <italic>COG1060 </italic>(Protein Thi4 with Functional Category H) is very strong and this is because they participate in thiamin biosynthesis as shown in our previous work [##REF##12794638##15##]. However, for those proteins that belong to different functional category even thought they are related (analogous proteins) [##REF##12794638##15##] could not be accurately classified from phylogenetic profiles. For example, <italic>COG2225 </italic>(Protein ThiN with Functional Category C belonging to cluster 11), <italic>COG0352 </italic>(Protein ThiE with Functional Category H belonging to cluster 15), and <italic>COG1992 </italic>(Protein MTH861 with Functional Category S belonging to cluster 19). Another example is <italic>COG02022 </italic>(Protein ThiG with Functional Category F belonging to cluster 14), and <italic>COG1635 </italic>(Protein Thi4 with Functional Category R belonging to cluster 18). And also, <italic>COG1060 </italic>(Protein ThiH with Functional Category HR belonging to cluster 15), <italic>COG1635 </italic>(Protein Thi4 with Functional Category R belonging to cluster 18), and <italic>COG0665 </italic>(Protein ThiO with Functional Category E belonging to cluster 13). But in this case, we found that they are classified in the surrounding clusters. As can be seen the relationship between analogous proteins must be classified considering the surrounding clusters.</p> <p>We have not intended our validations to be exhaustive by using all available databases. However, the consideration of additional databases such as GO, Funcat, among others, would be useful for more comprehensive validations.</p> <title>Authors' contributions</title> <p>EM suggested the biological model. RLAW and EEV suggested the use of BEA. RLAW implemented the algorithm and performed the computational experiments. RLAW, EEV, and EM wrote the manuscript. All authors contributed equally in this research. All authors read and approved the final manuscript.</p> <title>Supplementary Material</title>
<title>Acknowledgements</title> <p>We thank to Mateo Pellegrini for the interesting discussions of this work. We thank to Salvador Venegas for critical reading of the manuscript. We thank to Arturo Ocadiz and Shirley Ainsworth for technical assistance. This work was supported by the Consejo Nacional de Ciencia y Tecnología (CONACYT) under SEP-CONACYT award No. SEP-2004-C01-47434. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agency.</p>
<fig position="float" id="F1"><label>Figure 1</label><caption><p><bold>Example of Bea Cluster</bold>. This figure shows an example of the clusters of BEA clustering.</p></caption></fig> <fig position="float" id="F2"><label>Figure 2</label><caption><p><bold>Example of BEA clustering heatmap</bold>. This figure shows an example of a heatmap of BEA clustering.</p></caption></fig> <fig position="float" id="F3"><label>Figure 3</label><caption><p><bold>Bea Cluster</bold>. This figure show the distribution of the clusters for BEA.</p></caption></fig>
<table-wrap position="float" id="T1"><label>Table 1</label><caption><p>Resulting classification for all methods</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">Code</td><td align="center">COGs</td><td align="center">PREDICTED BEA</td><td align="center">PREDICTED HIERARCHICAL</td><td align="center">PREDICTED K-MEANS</td><td align="center">PREDICTED PAM</td></tr></thead><tbody><tr><td align="center">Information storage and processing</td><td/><td/><td/><td/><td/></tr><tr><td align="center">J</td><td align="center">217</td><td align="center">213</td><td align="center">321</td><td align="center">544</td><td align="center">754</td></tr><tr><td align="center">K</td><td align="center">132</td><td align="center">122</td><td align="center">4</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">L</td><td align="center">184</td><td align="center">181</td><td align="center">39</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">Cellular processes</td><td/><td/><td/><td/><td/></tr><tr><td align="center">D</td><td align="center">32</td><td align="center">32</td><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">O</td><td align="center">110</td><td align="center">104</td><td align="center">26</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">M</td><td align="center">155</td><td align="center">153</td><td align="center">140</td><td align="center">84</td><td align="center">0</td></tr><tr><td align="center">N</td><td align="center">133</td><td align="center">130</td><td align="center">46</td><td align="center">81</td><td align="center">100</td></tr><tr><td align="center">P</td><td align="center">160</td><td align="center">149</td><td align="center">10</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">T</td><td align="center">97</td><td align="center">83</td><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">Metabolism</td><td/><td/><td/><td/><td/></tr><tr><td align="center">C</td><td align="center">224</td><td align="center">220</td><td align="center">65</td><td align="center">24</td><td align="center">0</td></tr><tr><td align="center">G</td><td align="center">171</td><td align="center">164</td><td align="center">17</td><td align="center">197</td><td align="center">62</td></tr><tr><td align="center">E</td><td align="center">233</td><td align="center">226</td><td align="center">584</td><td align="center">260</td><td align="center">312</td></tr><tr><td align="center">F</td><td align="center">85</td><td align="center">83</td><td align="center">18</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">H</td><td align="center">154</td><td align="center">141</td><td align="center">49</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">I</td><td align="center">75</td><td align="center">72</td><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">Q</td><td align="center">62</td><td align="center">55</td><td align="center">0</td><td align="center">0</td><td align="center">0</td></tr><tr><td align="center">Poorly characterized</td><td/><td/><td/><td/><td/></tr><tr><td align="center">R</td><td align="center">449</td><td align="center">431</td><td align="center">113</td><td align="center">250</td><td align="center">0</td></tr><tr><td align="center">S</td><td align="center">750</td><td align="center">748</td><td align="center">1875</td><td align="center">1867</td><td align="center">2079</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T2"><label>Table 2</label><caption><p>Validation 1 for DIP in the same cluster</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">62.37662</td><td align="center">37.62338</td></tr><tr><td align="center">K-MEANS</td><td align="center">40.09091</td><td align="center">59.90909</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">22.77922</td><td align="center">77.22078</td></tr><tr><td align="center">PAM</td><td align="center">8.41558</td><td align="center">91.58442</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T3"><label>Table 3</label><caption><p>Validation 2 for DIP in the near cluster</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">71.428571</td><td align="center">28.571429</td></tr><tr><td align="center">K-MEANS</td><td align="center">46.1038961</td><td align="center">53.8961039</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">22.7272727</td><td align="center">77.2727273</td></tr><tr><td align="center">PAM</td><td align="center">21.4285714</td><td align="center">78.5714286</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T4"><label>Table 4</label><caption><p>Validation 3 for DIP in the surrounding five clusters</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">86.3636364</td><td align="center">13.6363636</td></tr><tr><td align="center">K-MEANS</td><td align="center">57.7922078</td><td align="center">42.2077922</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">40.9090909</td><td align="center">59.0909091</td></tr><tr><td align="center">PAM</td><td align="center">55.1948052</td><td align="center">44.8051948</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T5"><label>Table 5</label><caption><p>Validation 1 for ECOCYC in the same cluster</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">84.375</td><td align="center">15.625</td></tr><tr><td align="center">K-MEANS</td><td align="center">50.00</td><td align="center">50.00</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">37.50</td><td align="center">62.50</td></tr><tr><td align="center">PAM</td><td align="center">5.7291667</td><td align="center">94.2708333</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T6"><label>Table 6</label><caption><p>Validation 2 for ECOCYC in the near cluster</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">88.5416667</td><td align="center">11.4583333</td></tr><tr><td align="center">K-MEANS</td><td align="center">52.0833333</td><td align="center">47.9166667</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">38.0208333</td><td align="center">61.9791667</td></tr><tr><td align="center">PAM</td><td align="center">15.625</td><td align="center">84.375</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T7"><label>Table 7</label><caption><p>Validation 3 for ECOCYC in the surrounding five clusters</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">ALGORITHM</td><td align="center">CORRECT</td><td align="center">INCORRECT</td></tr></thead><tbody><tr><td align="center">BEA</td><td align="center">95.8333333</td><td align="center">4.1666667</td></tr><tr><td align="center">K-MEANS</td><td align="center">65.625</td><td align="center">34.375</td></tr><tr><td align="center">HIERARCHICAL</td><td align="center">46.3541667</td><td align="center">53.6458333</td></tr><tr><td align="center">PAM</td><td align="center">47.9166667</td><td align="center">52.0833333</td></tr></tbody></table></table-wrap> <table-wrap position="float" id="T8"><label>Table 8</label><caption><p>COG FUNCTIONAL CATEGORIES</p></caption><table frame="hsides" rules="groups"><thead><tr><td align="center">Code</td><td align="center">COGs</td><td align="center">Domains</td><td align="center">Description</td><td align="center">Pathways and functional systems</td></tr></thead><tbody><tr><td align="center">Information storage and processing</td><td/><td/><td/><td/></tr><tr><td align="center">J</td><td align="center">217</td><td align="center">6449</td><td align="center">Translation, ribosomal structure and biogenesis</td><td align="center">4</td></tr><tr><td align="center">K</td><td align="center">132</td><td align="center">5438</td><td align="center">Transcription</td><td align="center">3</td></tr><tr><td align="center">L</td><td align="center">184</td><td align="center">5337</td><td align="center">DNA replication, recombination and repair</td><td align="center">2</td></tr><tr><td align="center">Cellular processes</td><td/><td/><td/><td/></tr><tr><td align="center">D</td><td align="center">32</td><td align="center">842</td><td align="center">Cell division and chromosome partitioning</td><td align="center">-</td></tr><tr><td align="center">O</td><td align="center">110</td><td align="center">3165</td><td align="center">Posttranslational modification, protein turnover, chaperones</td><td align="center">-</td></tr><tr><td align="center">M</td><td align="center">155</td><td align="center">4079</td><td align="center">Cell envelope biogenesis, outer membrane</td><td align="center">1</td></tr><tr><td align="center">N</td><td align="center">133</td><td align="center">3110</td><td align="center">Cell motility and secretion</td><td align="center">2</td></tr><tr><td align="center">P</td><td align="center">160</td><td align="center">5112</td><td align="center">Inorganic ion transport and metabolism</td><td align="center">1</td></tr><tr><td align="center">T</td><td align="center">97</td><td align="center">3627</td><td align="center">Signal transduction mechanisms</td><td align="center">-</td></tr><tr><td align="center">Metabolism</td><td/><td/><td/><td/></tr><tr><td align="center">C</td><td align="center">224</td><td align="center">5594</td><td align="center">Energy production and conversion</td><td align="center">7</td></tr><tr><td align="center">G</td><td align="center">171</td><td align="center">5262</td><td align="center">Carbohydrate transport and metabolism</td><td align="center">4</td></tr><tr><td align="center">E</td><td align="center">233</td><td align="center">8383</td><td align="center">Amino acid transport and metabolism</td><td align="center">10</td></tr><tr><td align="center">F</td><td align="center">85</td><td align="center">2364</td><td align="center">Nucleotide transport and metabolism</td><td align="center">5</td></tr><tr><td align="center">H</td><td align="center">154</td><td align="center">4057</td><td align="center">Coenzyme metabolism</td><td align="center">11</td></tr><tr><td align="center">I</td><td align="center">75</td><td align="center">2609</td><td align="center">Lipid metabolism</td><td align="center">2</td></tr><tr><td align="center">Q</td><td align="center">62</td><td align="center">2754</td><td align="center">Secondary metabolites biosynthesis, transport and catabolism</td><td align="center">-</td></tr><tr><td align="center">Poorly characterized</td><td/><td/><td/><td/></tr><tr><td align="center">R</td><td align="center">449</td><td align="center">11948</td><td align="center">General function prediction only</td><td align="center">-</td></tr><tr><td align="center">S</td><td align="center">750</td><td align="center">6416</td><td align="center">Function unknown</td><td align="center">-</td></tr></tbody></table></table-wrap>
<disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M1" name="1471-2105-9-285-i1" overflow="scroll"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mi>M</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mstyle></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><italic>aff</italic>(<italic>A</italic><sub>0</sub>, <italic>A</italic><sub><italic>j</italic></sub>) = <italic>aff</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub>0</sub>) = <italic>aff</italic>(<italic>A</italic><sub><italic>n</italic>+1</sub>, <italic>A</italic><sub><italic>j</italic></sub>) = <italic>aff</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>n</italic>+1</sub>) = 0</disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M2" name="1471-2105-9-285-i2" overflow="scroll"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mi>M</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mstyle></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M3" name="1471-2105-9-285-i2" overflow="scroll"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mi>M</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mstyle></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M4" name="1471-2105-9-285-i3" overflow="scroll"><mml:semantics><mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>A</mml:mi><mml:mi>M</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo><mml:mo>=</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mstyle></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mstyle><mml:mo>+</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M5" name="1471-2105-9-285-i4" overflow="scroll"><mml:semantics><mml:mrow><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>x</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>y</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>z</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>z</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>x</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>a</mml:mi><mml:mi>f</mml:mi><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>z</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>y</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M6" name="1471-2105-9-285-i5" overflow="scroll"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mi>M</mml:mi><mml:mo>=</mml:mo><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>j</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><italic>A</italic><sub>1</sub><italic>A</italic><sub>2</sub>...<italic>A</italic><sub><italic>i</italic>-1</sub><italic>A</italic><sub><italic>i</italic></sub><italic>A</italic><sub><italic>j</italic></sub><italic>A</italic><sub><italic>j</italic>+1</sub>...<italic>A</italic><sub><italic>n </italic></sub><italic>AM</italic>' = [<italic>A</italic><sub>1</sub><italic>A</italic><sub>2</sub>...<italic>A</italic><sub><italic>i</italic>-1</sub>] <italic>AM" </italic>= [<italic>A</italic><sub><italic>j</italic>+1</sub>...<italic>A</italic><sub><italic>n</italic></sub>]</disp-formula> <disp-formula><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M7" name="1471-2105-9-285-i6" overflow="scroll"><mml:semantics><mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mrow><mml:mi>A</mml:mi><mml:msub><mml:mi>M</mml:mi><mml:mrow><mml:mi>o</mml:mi><mml:mi>l</mml:mi><mml:mi>d</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mi>A</mml:mi><mml:msup><mml:mi>M</mml:mi><mml:mo>′</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:mi>A</mml:mi><mml:msup><mml:mi>M</mml:mi><mml:mo>″</mml:mo></mml:msup><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>j</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>j</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo></mml:mrow></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mrow><mml:mstyle displaystyle="true"><mml:msubsup><mml:mo>∑</mml:mo><mml:mrow><mml:mi>l</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mi>n</mml:mi></mml:msubsup><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>l</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mi>o</mml:mi><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mi>l</mml:mi></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>A</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:mstyle></mml:mrow></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:semantics></mml:math></disp-formula> <disp-formula><italic>AM</italic><sub><italic>new </italic></sub>= <italic>AM' </italic>+ <italic>AM" </italic>+ <italic>bond</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>) + <italic>bond</italic>(<italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>i</italic></sub>) + <italic>bond</italic>(<italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>) + <italic>bond</italic>(<italic>A</italic><sub><italic>j</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>) = <italic>AM' </italic>+ <italic>AM" </italic>+ 2<italic>bond</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>) - 2<italic>bond</italic>(<italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>)</disp-formula> <disp-formula><italic>cont</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>) = <italic>AM</italic><sub><italic>new </italic></sub>- <italic>AM</italic><sub><italic>old </italic></sub>= <italic>bond</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>k</italic></sub>) + <italic>bond</italic>(<italic>A</italic><sub><italic>k</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>) - <italic>bond</italic>(<italic>A</italic><sub><italic>i</italic></sub>, <italic>A</italic><sub><italic>j</italic></sub>)</disp-formula>
<supplementary-material content-type="local-data" id="S1"><caption><title>Additional file 1</title><p>Table of DIP Relationships used for validation.</p></caption></supplementary-material> <supplementary-material content-type="local-data" id="S4"><caption><title>Additional file 4</title><p>DIP validation table.</p></caption></supplementary-material> <supplementary-material content-type="local-data" id="S2"><caption><title>Additional file 2</title><p>Table of ECOCYC Relationships used for validation.</p></caption></supplementary-material> <supplementary-material content-type="local-data" id="S5"><caption><title>Additional file 5</title><p>ECOCYC validation table.</p></caption></supplementary-material> <supplementary-material content-type="local-data" id="S3"><caption><title>Additional file 3</title><p>Result of BEA cluster.</p></caption></supplementary-material>
<table-wrap-foot><p>Classification for COG Functional Categories (One classification for multiple classification COGs).</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database of Interacting Proteins.</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database of Interacting Proteins. Neighbor Cluster Maximum 1.</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database of Interacting Proteins. Neighbor Cluster Maximum 5.</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database ECOCYC.</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database ECOCYC. Neighbor Cluster Maximum 1.</p></table-wrap-foot> <table-wrap-foot><p>Classification for Database ECOCYC. Neighbor Cluster Maximum 5.</p></table-wrap-foot> <table-wrap-foot><p>Classification for COG's Database of Protein Functional Category.</p></table-wrap-foot>
<graphic xlink:href="1471-2105-9-285-1"/> <graphic xlink:href="1471-2105-9-285-2"/> <graphic xlink:href="1471-2105-9-285-3"/>
<media xlink:href="1471-2105-9-285-S1.pdf" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p></caption></media> <media xlink:href="1471-2105-9-285-S4.pdf" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p></caption></media> <media xlink:href="1471-2105-9-285-S2.pdf" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p></caption></media> <media xlink:href="1471-2105-9-285-S5.pdf" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p></caption></media> <media xlink:href="1471-2105-9-285-S3.pdf" mimetype="application" mime-subtype="pdf"><caption><p>Click here for file</p></caption></media>
[{"surname": ["Tian", "Skolnick"], "given-names": ["W", "J"], "article-title": ["How well is enzyme function conserved as a function of pairwise sequence identity"], "source": ["Bioinformatics"], "year": ["2003"], "volume": ["333"], "fpage": ["863"], "lpage": ["882"]}, {"surname": ["Tian", "Arakaki", "Skolnick"], "given-names": ["W", "A", "J"], "article-title": ["EFICAz: a comprehensive approach for accurate genome-scale enzyme function inference"], "source": ["Nucleic Acid Res"], "year": ["2004"], "volume": ["32"], "fpage": ["5225"], "lpage": ["5239"]}, {"surname": ["Snoep", "Westerhoff"], "given-names": ["J", "H"], "source": ["Systems Biology: From isolation to integration, a systems biology approach for building the Silicon Cell"], "year": ["2005"], "publisher-name": ["USA: Springer-Verlag"]}, {"surname": ["Arabie", "Hubert"], "given-names": ["P", "L"], "article-title": ["The bond energy algorithm revisted. IEEE Transaction on Systems"], "source": ["Man and Cybernetics"], "year": ["1990"], "volume": ["20"], "fpage": ["268"], "lpage": ["274"], "pub-id": ["10.1109/21.47829"]}, {"surname": ["Kaufman", "Rousseeuw"], "given-names": ["L", "P"], "source": ["Finding Groups in Data: An Introduction to Cluster Analysis"], "year": ["1990"], "publisher-name": ["New York: Wiley"]}, {"surname": ["Kohavi"], "given-names": ["R"], "article-title": ["A study of cross-validation and bootstrap for accuracy estimation and model selection"], "source": ["International Joint Conference on Artificial Intelligence (IJCAI), IJCAI"], "year": ["1995"]}, {"surname": ["Breiman", "Spector"], "given-names": ["L", "P"], "article-title": ["Submodel selection and evaluation in regression: The X-random case"], "source": ["International Statistical Review"], "year": ["1992"], "volume": ["60"], "fpage": ["D334"], "lpage": ["D337"]}, {"article-title": ["The MathWorks \u2013 MATLAB and Simulink for Technical Computing"]}, {"article-title": ["The R Project for Statistica Toolkit"]}, {"article-title": ["COG clusters of orthologous groups database"]}, {"surname": ["Ciria", "C", "Morett", "Merino"], "given-names": ["R", "AG", "E", "E"], "article-title": ["GeConT: gene context analysis"], "source": ["Bioinformatics, Oxford University Press"], "year": ["2004"]}, {"surname": ["Bernhard"], "given-names": ["OP"], "source": ["System Biology"], "year": ["2006"], "publisher-name": ["New York: Cambridge University Press"]}, {"surname": ["Watanabe", "Vallejo", "E"], "given-names": ["R", "E", "M"], "article-title": ["Inferring fuctional coupling of genes from phylogenetic profiles using the bond energy algorithm with genetic algorithms"], "source": ["Proc of CICB 2006, CICB"], "year": ["2006"]}, {"surname": ["Watanabe", "Vallejo", "Morett"], "given-names": ["R", "E", "E"], "article-title": ["Inferring fuctional coupling of genes from phylogenetic profiles using the bond energy algorithm"], "source": ["Automatic Function Prediction"], "year": ["2006"]}, {"article-title": ["DIP: Home"]}, {"article-title": ["EcoCyc: Encyclopedia of "], "italic": ["Escherichia coli"]}, {"surname": ["McCormick", "Schweitzer", "White"], "given-names": ["W", "P", "T"], "article-title": ["Problem Decomposition and Data Reorganization by a Clustering Technique"], "source": ["Op Res"], "year": ["1972"]}, {"surname": ["Hoffer"], "given-names": ["J"], "article-title": ["A clustering approach to the generation of subfiles for the design of a computer data base"], "source": ["PhD thesis"], "year": ["1975"], "publisher-name": ["Ph.D. dissertion, Ithaca, N.Y.: Department of Operations Research, Cornell University"]}, {"surname": ["Navathe", "Ceri", "Wiederhold", "Dou"], "given-names": ["S", "S", "G", "J"], "article-title": ["Vertical partitioning of algorithms for database design"], "source": ["ACM Trans Databese Syst"], "year": ["1984"]}]
BMC Bioinformatics. 2008 Jun 17; 9:285