BACKGROUND
the ongoing sequencing efforts continue to discover the sequences of many new proteins, whose function is unknown.
currently, protein databases contain the sequences of about  <dig> , <dig> proteins, of which more than half are partially or completely uncharacterized  <cit> .
typically, proteins are analyzed by searching for homologous proteins that have already been characterized.
homology establishes the evolutionary relationship among different organisms, and the biological properties of uncharacterized proteins can often be inferred from those of homologous proteins.
however, detecting homology between proteins can be a difficult task.
our ability to detect subtle similarities between proteins depends strongly on the representations we employ for proteins.
sequence and structure are two possible representations of proteins that hinge directly on molecular information.
the essential difference between the representation of a protein as a sequence of amino acids and its representation as a 3d structure traditionally dictated different methodologies, different similarity or distance measures and different comparison algorithms.
the power of these representations in detecting remote homologies differ markedly.
despite extensive efforts, current methods for sequence analysis often fail to detect remote homologies for sequences that have diverged greatly.
in contrast, structure is often conserved more than sequence  <cit> , and detecting structural similarity may help infer function beyond what is possible with sequence analysis.
however, structural information is sparse and available for only a small part of the protein space.
one may argue that the weakness of sequence based methods is rooted in the underlying representation of proteins, the model used for comparison and/or the comparison algorithm, since in principle, according to the central dogma of molecular biology,  all the information that is needed to form the 3d structure is encoded in the sequence.
indeed, in recent years better sequence-based methods were developed  <cit> .
these methods utilize the information in groups of related sequences  to build specific statistical models associated to different groups of proteins  that can be used to search and detect subtle similarities with remotely related proteins.
such generative models assume a statistical source that generates instances according to some underlying distributions, and model the process that generates samples and the corresponding distributions.
when seeking a new similarity measure for proteins that departs from sequence and structure, a natural question is what is the "correct" encoding of proteins?
several works studied the mathematical representation of protein sequences based on sequence properties such as amino acid composition or chemical features  <cit> .
however, these representations had limited success, since they did not capture the essence of proteins as ordered sequences of amino acids.
recently, alternative representations of protein sequences based on the so-called kernel methods were proposed.
these methods are drawn from the field of machine learning and strive to find an adequate mapping of the protein space onto the euclidean space where classification techniques such as support vector machines  or artificial neural networks  can be applied.
under the kernel representation, each protein is typically mapped to a vector in a  feature space, and the resulting vector is termed feature vector.
subsequently, an inner product is defined in the feature space in order to estimate the similarity among different proteins.
a major advantage of the kernel methods is that with an adequate choice of the kernel function, the feature vectors need not be computed explicitly in order to evaluate the similarity relationships.
in addition, the users may build a specific feature space such that the kernel function directly estimates these relationships.
however, string kernels do not easily lend themselves to this property, and therefore they need to be computed explicitly.
the main difference between the different kernel methods reside in the definition of feature elements which are either related to the parameters of some generative process for each group of related proteins or some measure of similarity among the protein sequences.
for instance, the svm-fisher algorithm  <cit>  uses the fisher kernel which is based on hidden markov models .
the components of the feature vector are the derivatives of the log-likelihood score of the sequence with respect to the parameters of a hmm that has been trained for a particular protein family.
tsuda et.
al.
<cit>  implemented another representation based on marginalized and joint kernels and showed that the fisher kernel is in fact a special case of marginalized kernel.
they also experimented with the marginalized count kernels of different orders, that are similar to the spectrum kernel which was first introduced by  <cit> .
the spectrum kernel is evaluated by counting the number of times each possible k-long subsequence of amino acids  occurs in one given protein.
the marginalized count kernel takes into account both the observed frequency of different subsequences and the context .
the mismatch-spectrum kernel  <cit>  is a generalization of the spectrum kernel that considers also mutation probabilities between k-mers which differ by no more than m characters.
the homology kernel  <cit>  is another biologically motivated sequence embedding process that measures the similarity between two proteins by taking into account their respective groups of homologous sequences.
it can be thought of as an extension of the mismatch-spectrum kernel by adding a wildcard character and distinguishing the mismatch penalty between two substrings depending on whether the sequences are grouped together or not.
the covariance kernel is another type of kernel that uses a framework similar to the one employed by our method.
the covariance kernel approach is probabilistic and much work is focused on the implementation of the generative models.
in  <cit> , the covariance kernel is based on the mutual information kernel which measures the similarity between data samples and a certain generative process.
the generative process is characterized by a mediator distribution defined between the  prior and the posterior distribution.
on the other hand,  <cit>  focuses on the representation of biological sequences using the probabilistic suffix tree  <cit>  as the generative model for different groups of related proteins.
the proposed kernel generates a feature vector for protein sequences, where each feature corresponds to a different generative model and its value is the likelihood of the sequence based on that model.
finally, we mention another related work  <cit>  that uses the notion of pairwise kernel.
under this framework, each protein is represented by a vector that consists of pairwise sequence similarities with respect to the set of input sequences.
it is also worth mentioning the many related studies in the field of natural language processing and text analysis.
for example, an approach that in some ways is similar to the pairwise and covariance kernels and in other ways is related to the spectrum kernel approach, is used in  <cit>  to represent verbs and nouns in english texts, with nouns represented as frequency vectors over the set of verbs  and vice versa.
the nouns and verbs are then clustered based on this representation.
studies that attempted to devise automatic methods for text categorization and web-page classification often use similar techniques, where the text is represented as a histogram vector over a vocabulary of words .
here we study a general framework of protein representation called the distance-profile representation, that utilizes the global information in the protein space in search of statistical regularities.
the representation draws on an association measure between input samples  and can use existing measures of similarity, distance or probability .
this representation induces a new measure of similarity for all protein pairs based on their vectorial representations.
our representation is closely related to the covariance and pairwise kernels described above.
however, it is the estimation of pvalues through statistical modeling of the background process, coupled with the transformation to probability distributions, the noise reduction protocols and the choice of the distance function that result in a substantial impact on the performance, and we demonstrate how an adequate choice of the score transformation and the distance metric achieves a considerable improvement in detection of remote homologies.
this paper is organized as follows.
we first introduce the notion of distance-profile.
we describe how to process the feature vectors through noise reduction, and pvalue transformation followed by normalization.
we compare the performance of our new method against several standard algorithms by testing them on a large set of protein families.
RESULTS
the distance-profile representation
our goal is to seek a faithful representation of the protein space that will reflect evolutionary distances even if undetectable by means of existing methods of comparison.
we explore a technique based on the distance-profile technique described in  <cit>  and its derivative as applied to protein sequences in  <cit> .
the power of the representation stems from its ability to recover structure in noisy data and boost weak signals  <cit> .
the distance-profile representation is simple and can be applied to arbitrary spaces x
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@, y
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ if there exist an association measure between instances of x
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@ and instances of y
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ such as a distance function, similarity function or a probability measure.
given an instance x in the input space x
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@, a reference set {y <dig>  y <dig>  ... yn} of entities in y
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@  and an underlying association measure, we associate with the instance x a position in a high dimensional space, where every coordinate is associated with one member of the reference set and its value is the similarity with that particular reference object.
i.e., we map x to a vector of dimension n in the host space
x→x=⋮s).
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgybawcqghsgirtcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8hwaiabg2da9maabmaabaqbaeqabmqaaaqaaiabdofatjaaykw7daqadaqaaiabdifayjabcycasiabdmfaznaabaaaleaacqaixaqmaeqaaagccagloagaayzkaaaabagaeso7i0eabagaem4uam1aaewaaeaacqwgybawcqggsaalcqwgzbqwdawgaawcbagaemoba4gabeaaaogaayjkaiaawmcaaaaaaiaawicacaglpaaacqgguaglcawljagaaczcamaabmaabagaegymaedacagloagaayzkaaaaaa@54ca@
this simple representation leads to the definition of a new distance or similarity measure among samples based on their vectorial representation, and when the reference set is identical to the input space , an iterative application of this representation can be used to form hierarchical clustering over the input samples  <cit> .
in this paper we demonstrate the application of this method to the problem of homology detection between distantly related proteins.
one might observe the resemblance of our method with pairwise kernels and covariance kernels mentioned in the 'background' section.
however, it is the processing of the feature vectors and the choice of the metric, as is laid out next, which are the crucial ingredients that differentiate our method from the previous studies.
as exemplified in this paper, under the proper transformations the distance-profile representation has mathematical and statistical interpretations that have other implications, and it is these transformations that deem this method very effective for homology detection, database search and clustering.
the reference set
remotely related proteins usually share little sequence similarity, however, they are expected to have similar structures.
therefore, as a reference set for our experiments we chose a non-redundant structure library consisting of domain structures that represent the current protein structure space.
the set is derived from the scop database  <cit> , release  <dig> .
specifically, we used the genetic domain sequence dataset that we downloaded from the astral webpage  <cit> .
the dataset is obtained from  <dig>  entries in the protein data bank   <cit>  and contains only protein domains with less than 40% identity between pairs of sequences.
our library consists of  <dig>  distinct scop domains covering in total  <dig> folds,  <dig> superfamilies, and  <dig>  families.
for notation purpose, we denote this library of template proteins by scop-db.
the association measure
we rely on "structure-aided" sequence alignment to bridge the gap between the sequence space and structure space.
given the library of structures y
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ = {y <dig>  y <dig>  y <dig>  ..., yn}, every protein sequence p is mapped to a structure-specific n-dimensional feature vector, as is described above, where the association measure s is the similarity score of the sequence-structure alignment between the sequence p and the template structure yi, computed with the fugue threading algorithm  <cit>  .
from this point on we discuss the application of the distance-profile representation with threading-based association measures.
however, we note that the methods described in this paper can be used to process feature vectors using other association measures.
in the 'discussion' section we show that a similar approach applied to sequence-profile alignment scores also produces a considerable improvement in detecting remote homologies.
processing feature vectors: pvalue conversion and normalization
the choice of the underlying association function s can have a drastic impact on the effectiveness of the representation and we tested several variations.
the score association measure
a possible choice is obviously the score reported by the algorithm that compares entities of x
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@ with entities of y
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@.
.
we denote feature vectors that are based on the score association measure by pscore.
the pvalue association measure
if the association measure is distributed over a wide range, the most significant scores will inevitably shadow other numerically less important but still significant matches, thus reducing the sensitivity of the representation.
this is the case with most types of similarity scores, including the threading zscores assigned by the fugue program.
to address this problem we convert the zscores to their underlying cumulative distribution function  value, where the amplitude of outlier zscores is reduced to within a reasonable range.
as was shown in  <cit> , the zscores of local alignment scores follow the extreme value distribution , see figure  <dig>  whose cumulative function f takes the form
f = prob = e-φ     where    φ = e-λ.
based on this background distribution we replace the original zscores with a new association measure such that s' = f) where s is the similarity zscore reported by fugue.
with this transformation, all coordinates are bounded between  <dig> and  <dig>  with high zscores transformed to values close to  <dig>  note that the pvalue of a given zscore x is pvalue =  <dig> - f. we denote feature vectors that are based on the f association measure by ppvalue.
it should also be noted that in practice f =  <dig> - pvalue =  <dig> for large x because of machine precision limitations.
therefore, the pvalues that are associated to significant zscores  are approximated by their empirical distribution, thus allowing distinction between a pair of highly significant yet numerically disparate zscores, e.g.
<dig> versus  <dig>
the probability association measure
the third variation we tested is based on a simple normalization of each feature vector to form a probability distribution.
this transformation enables us to explore distance measures that are suited for probability vectors, as described in section 'metrics and score functions'.
indeed, in this representation, the normalized vector entries can be considered as the coefficients of a mixture model where the components models are the protein structures, each one inducing a different probability distribution over the protein sequence space.
this interpretation emphasizes the similarity with covariance methods which also resort to a probabilistic representation of different protein families as described in the 'background' section.
we denote feature vectors that are based on this association measure by pprob.
reducing noise: sparse feature vectors
our reference set is composed of proteins that belong to different protein families and folds .
within that data set no two proteins share more than 40% sequence identity.
therefore, for a given query protein we expect to observe only a few significant similarity values in the vector p. that is, the entries that correspond to the structural templates of protein families that are related to the query.
in other words, the feature vectors contain many entries that are essentially random and meaningless.
these random numbers will contribute to the differences between feature vectors, thus masking possibly significant similarities.
to reduce noise due to unrelated proteins we eliminate all entries with zscore below a certain threshold τ, or pvalue above a certain threshold τ', to reflect the fact that the corresponding sequence-structure pair is considered irrelevant  the parameter τ is optimized to maximize performance, as described in section 'parameter optimization'.
note that entries with low zscores that are filtered in this step  remain zero under the transformation to the cdf pvalue as described above.
the processed feature vector is denoted by p^score
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaatcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegab8huayaajawaawbaasqabeaacqwgzbwccqwgjbwycqwgvbwbcqwgybgccqwglbqzaaaaaa@3f2d@.
the noise reduction is applied to the original feature vectors and is followed by the pvalue conversion and the normalization to yield new feature vectors ppvalue and pprob, respectively.
to illustrate the impact of our procedures on the distance profiles, let us consider the example of two closely related proteins d1qmva_ and d1hd2a_  that belong to family c. <dig> .
<dig> under the scop denomination.
the sequences were threaded against the scop library of structural domains, and feature vectors were compiled from the zscores reported by fugue.
in table  <dig> we report the 2163th up to the 2169th entries of their original feature vectors as well as their transformations after noise reduction, pvalue conversion and normalization.
as this example demonstrates, the zscore entries are noisy and spread over a wide numerical range.
for instance, the 2167th entry of both vectors correspond to their threading score versus the structure of d1prxa_ , another protein that is in the same scop family c. <dig> .
<dig>  while the zscore reaches  <dig>  for d1qmva_, it is only  <dig>  for d1hd2a_.
these large differences will inevitably result in large distances between the feature vectors despite the fact that they have significant zscore values in the same positions.
the pvalue conversion and normalization  resolve this problem by rescaling scores to within a fixed interval.
p^score
metrics and score functions
under the distance-profile representation, the similarity  between two protein sequences p and p' is defined as the similarity  of their corresponding feature vectors
s = f
the function f can be a similarity function or a distance function and we considered several different variants.
we tested the l <dig> norm  and the l <dig> norm .
for probability distributions we also tested the jensen-shannon  measure of divergence  <cit> .
given two probability distributions p and q, for every  <dig> ≤ λ ≤  <dig>  their λ-jensen-shannon divergence is defined as
dλjs=λdkl+dkl
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgebardaqhaawcbagaeq4udwgabagaemosaokaem4uamfaaogaei4was1exlmbbxgbcf2cpn2qvrwzqf2zlnharygvljhzh5wyagabbiaa=bhacqgg8bafcqgg8bafcawfxbgaeiyxa0laeyypa0jaeq4udwmaemiraq0aawbaasqabeaacqwglbwscqwgmbataagccqggbbwwcawfwbgaeiifawnaeiifawnaa8ncaiabc2fadjabgucariabcicaoiabigdaxiabgkhitiabeu7asjabcmcapiabdseaenaacaaaleqabagaem4saskaemitaweaaogaei4waslaa8xcaiabcyha8jabcyha8jaa=jhacqggdbqxaaa@629d@
where dkl  is the kullback-leibler  divergence  <cit>  defined as dkl=∑ipilog⁡2piqi
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgebardaahaawcbeqaaiabduealjabdyeambaakiabcufabnxvp5wqsxmqhnxajn0bkvguhdwzzbqegyvzyrwyufgaiqqacawfwbgaeiifawnaeiifawnaa8xcaiabc2fadjabg2da9maaqababagaemicaa3aasbaasqaaiabdmgapbqabagccyggsbabcqggvbwbcqggnbwzdawgaawcbagaegomaidabeaakmaalaaabagaemicaa3aasbaasqaaiabdmgapbqabaaakeaacqwgxbqcdawgaawcbagaemyaakgabeaaaaaabagaemyaakgabeqdcqghris5aaaa@549a@ and r = λp + q can be considered as the most likely common source distribution of both distributions p and q, with λ as a prior weight .
unlike the kullback-leibler measure, the js measure is symmetric and bounded.
it ranges between  <dig> and  <dig>  where the divergence for identical distributions is  <dig>  this measure has been used successfully in  <cit>  to detect subtle similarities between statistical models of protein families and in  <cit>  for automatic domain prediction from sequence information.
as an alternative approach to assess the similarity of a pair of proteins based on their distance-profile representation we propose the pvalue-distance  function.
this function assesses the distance between two proteins by estimating the probability to observe a random protein with a feature vector inside the volume delimited by their two feature vectors.
the smaller the volume is, the more similar are the two vectors.
the function operates on the pvalues used to form the feature vectors ppvalue.
given two feature vectors p and q that correspond to proteins p and q, we consider one coordinate i at a time and estimate the total probability mass of samples whose i-th feature is bounded between the feature values pi and qi as is illustrated in figure 2a.
since each representative in the reference set induces a complex high-dimensional distribution over the protein sequence space, the one-dimensional pvalue measure pi can only serve to approximate a certain perimeter in the sequence space of sequences that are as similar or more similar to the i-th source than the protein p. therefore, we use the least significant pvalue of pi and qi as an upper bound estimator of the volume of relevant instances, as illustrated in figure 2b.
the total volume is computed by taking the product over all coordinates.
formally, consider the two pvalue feature vectors p1pvalue=
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaaieqacqwfqbaudaqhaawcbiqaacqccqwfxaqmaeaacqwfwbaccqwf2bgdcqwfhbqycqwfsbabcqwf1bqdcqwflbqzaagccqgh9aqpcqggoaakcqwgwbacdaqhaawcbagaegymaedabagaegymaedaaogaesojgskaemicaa3aa0baasqaaiabd6gaubqaaiabigdaxaaakiabcmcapaaa@4336@ and p2pvalue=
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaaieqacqwfqbaudaqhaawcbagae8nmaidabagae8hcaanae8ndaynae8xyaemae8hbawmae8xdaunae8xzaugaaogaeyypa0jaeiikagiaemicaa3aa0baasqaaiabigdaxaqaaiabikdayaaakiablaciljabdchawnaadaaaleaacqwgubgbaeaacqaiyagmaagccqggpaqkaaa@4288@ that are obtained by mapping each zscore zi to its pvalue pi using the evd background distribution as described in section 'processing feature vectors'.
their pvalue distance is defined as
pd=∏i=1lmax⁡.
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgqbaucqwgebarcqggoaaktcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8huamaabaaaleaacawfxaaabeaakiabcycasiaa=bfadawgaawcbagaa8nmaaqabagccqggpaqkcqgh9aqpdaqewaqaaigbc2gatjabcggahjabciha4naabmaabagaemicaa3aa0baasqaaiabdmgapbqaaiabigdaxaaakiabcycasiabdchawnaadaaaleaacqwgpbqaaeaacqaiyagmaaaakiaawicacaglpaaaasqaaiabdmgapjabg2da9iabigdaxaqaaiabdyeambqdcqghpis1aogaeiola4iaaczcaiaaxmaadaqadaqaaiabiodazagaayjkaiaawmcaaaaa@59f8@
in practice, the pd score is evaluated through its logarithm:
−log⁡pd=−∑i=1llog⁡max⁡
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqghsislcyggsbabcqggvbwbcqggnbwzcqwgqbaucqwgebarcqggoaaktcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8huamaabaaaleaacawfxaaabeaakiabcycasiaa=bfadawgaawcbagaa8nmaaqabagccqggpaqkcqgh9aqpcqghsisldaaewaqaaigbcygasjabc+gavjabceganjgbc2gatjabcggahjabciha4bwcbagaemyaakmaeyypa0jaegymaedabagaemitaweaniabgghildgcdaqadaqaaiabdchawnaadaaaleaacqwgpbqaaeaacqaixaqmaagccqggsaalcqwgwbacdaqhaawcbagaemyaakgabagaegomaidaaagccagloagaayzkaagaaczcaiaaxmaadaqadaqaaiabisda0agaayjkaiaawmcaaaaa@633d@
is used directly to define the feature values, as opposed to f =  <dig> - pvalue that was used before when compiling the feature vectors ppvalue.
however, to simplify notation we also refer to these feature vectors as ppvalue.)
to distinguish all the measures discussed in this section from the association measures discussed in section 'processing feature vectors', we refer to all of them from now on as distance metrics, although they are not necessarily metrics or distance functions.
discussion
dataset preparation
we use the scop classification of protein structures  <cit>  as our benchmark.
the scop database is built mostly based on manual analysis of protein structures and is characterized by a hierarchy with four main levels: class, fold, superfamily and family.
proteins that belong to the same family display significant sequence similarity that indicates homology.
at the next level , families are grouped into superfamilies based on structural similarity and weak sequence similarity .
proteins that belong to different families within the same superfamily are considered remotely related.
it is this level that has been used in many studies to evaluate sequence comparison algorithms .
the challenge is to automatically detect similarities between families within the same superfamily, that were established manually by the scop experts.
to determine the optimal parameters for the distance-profile representation and compare its performance to other algorithms, we split the library scop-db into a training set and a test set.
since our purpose is to test the ability to find remotely related proteins at the superfamily and fold levels, we first discard all proteins that have fewer than  <dig> remote homologs in scop-db .
from the remaining  <dig>  sequences we randomly select  <dig> for the training set, and the rest  are compiled into the test set.
performance indices
to evaluate the performance of a given method for a specific query protein we compare the protein against scop-db, sort the results and assess the correlation of the sorted list with established homology relations.
in our experiments we consider two proteins to be related  if they belong to the same scop superfamily.
all other pairs are treated as negatives.
we also consider a more relaxed definition, where proteins are deemed related if they belong to the same scop fold.
a popular measure of performance used in signal detection and classification is the rock measure  <cit> .
this is the cumulative count of positive samples detected until k negative samples are met in the sorted list of results.
we use four different indices to assess performance, all are variations on commonly used sensitivity and accuracy measures.
these indices measure the ability of a given algorithm to recognize different levels of structural similarity between protein sequences and within neighborhoods of varying sizes:
• the roc <dig> superfamily index .
• the roc1-fold index .
• the top-superfamily-superfamily index .
• the top-fold-fold index .
given the sorted list of results for a query protein p, the roc1-s index totals the number of proteins in the same superfamily as p that are observed from the top of the sorted list until the first false match  appears.
likewise, the roc1-f index is defined by counting the number of proteins in the same fold as p from the top of the sorted list until the first match that involves two proteins with different folds.
the last two indices are characterized by the following generic definition: the top-x-y index for a protein p counts the total number of proteins sharing the same y scop denomination among the nx closest sequences of p, where nx is the total number of sequences in the library that have the same x scop denomination as p itself .
self-similarity is ignored in the assessment of all performance indices.
note that all these indices are closely related to sensitivity measures at different levels, however, the relevant neighborhood is calibrated on a per-superfamily/fold basis.
and while the two roc indices stop as soon as one false match is encountered, the top-x-y indices credit a method that detects many true positives at the top even if mixed with a few false positives.
therefore, a method yielding a lower roc <dig> index but higher tss  should be still considered successful since it clusters the query close to a larger number of related objects.
to obtain the overall performance of a method with respect to a set of queries, we simply take the sum of all their corresponding performance indices as the global result.
i.e.
given a query set q = {q <dig>  ..., qn}, the performance of a method m, using index i is
i=∑i=1ni
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgjbqscqggoaakcqwgnbqtcqggsaaltcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8xuaiabcmcapiabg2da9maaqahabagaemysakkaeiikagiaemyta0kaeiilawiaemycae3aasbaasqaaiabdmgapbqabagccqggpaqkasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaubqdcqghris5aaaa@4ca6@
where i is the performance of the method m for the protein qi  is the tff performance of fugue on protein qi).
normalized performance indices
the global performance indices might be affected by the specific make up of the query set, since superfamilies and folds vary greatly in size.
in order to reduce a potential bias due to large superfamilies/folds that perform very well, we use also normalized performance indices.
to compute these, we divide each index by its upper bound, i.e.
the total number of proteins in the scop-db library that are classified to the same superfamily/fold as the query .
for example, for a query protein q that belongs to a fold f of size nf the normalized tff measure is given by
tffn  = tff /
this ratio is essentially the sensitivity of the method m on the query q, over a match list of size nf.
the size of the relevant match list changes with each query.
the resulting ratios are then averaged at the superfamily level so as to obtain a representative average performance index per protein superfamily that is bounded between  <dig> and  <dig>  finally, the final index is computed by averaging over all the representative indices.
i.e.
given a query set q = {q <dig>  ..., qn} that are classified to k different superfamilies f <dig>  ..., fk with ni queries in superfamily fi, then the overall performance of a method m, using the normalized index in is given by
in=1k∑i=1k1ni∑q∈fiin
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgjbqsdaahaawcbeqaaiabd6eaobaakiabcicaoiabd2eanjabcycasmxvp5wqsxmqhnxajn0bkvguhdwzzbqegyvzyrwyufgaiqqacawfrbgaeiykakiaeyypa0zaasaaaeaacqaixaqmaeaacqwgrbwaaawaaabcaeaadawcaaqaaiabigdaxaqaaiabd6gaunaabaaaleaacqwgpbqaaeqaaaaakmaaqafabagaemysak0aawbaasqabeaacqwgobgtaagccqggoaakcqwgnbqtcqggsaalcqwgxbqccqggpaqkasqaaiabdghaxjabgigiolabdaeagnaabaaameaacqwgpbqaaeqaaawcbeqdcqghris5aawcbagaemyaakmaeyypa0jaegymaedabagaem4aasganiabgghildaaaa@5bd6@
parameter optimization
our method depends on three parameters: the noise reduction level , the association measure and the distance metric.
we consider all possible combinations among five zscore cutoff values , three association measures that are pscore , ppvalue  and pprob , and four distance metrics: l <dig>  l <dig>  the js divergence measure and the new pvalue-distance  measure.
note that the js measure is only applicable to normalized vectors since it requires the input vector to represent a probability distribution and the pd measure is only applicable to the pvalue vectors.
to find the best parameters we first establish the feature vectors for each sequence in scop-db.
each combination of an association function  and a noise threshold τleads to a different set of feature vectors.
next, we compute the distance between the feature vector of each training sequence and the vectors of all sequences in scop-db, using one of the distance metrics of section 'metrics and score functions'.
each combination of feature vectors and a distance metric results in a different set of "match lists".
these sets are then evaluated using the performance indices described above.
the results are reported in table  <dig>  for clarity, the best combination of parameters is printed in boldface for each index.
to determine the optimal set of parameters, we first examine the effect of the association function.
the results are unanimous with all five performance indices: the pvalue association measure achieves the best performance, followed by the prob association measure.
however, the pvalue association measure is only effective when coupled with the pd distance metric, while the prob association measure seems to produce good results with all distance metrics and especially with l <dig> and the js divergence measure.
as for the distance metric, its influence depends on the association function.
the pd measure is applicable only to the pvalue vectors but it produces excellent results, much better than the traditional l <dig> and l <dig> metrics.
under the prob association measure, li and js metrics produce the best results while l <dig> leads to significantly worse performance.
with the two other association measures l <dig> and l <dig> metrics yield similar results.
finally, the optimal value of τis approximately around  <dig>  for most combinations.
in conclusion, these results suggest that the best performance is achieved with the pvalue association measure, the pvalue-distance  metric and a zscore cutoff threshold τ=  <dig> .
the same conclusions are reached when using the normalized performance indices.
it should be noted that although the prob association measure is not as good as the pvalue measure , it still produces very good performance overall , further justifying the statistical interpretation of our representation and its equivalence with the coefficients of a mixture model over independent sources .
performance comparison
we compare the performance of our algorithm against several existing algorithms, namely fugue  <cit> , blast  <cit>  and psiblast  <cit> .
table  <dig> reports the results for all algorithms based on the training sequences.
the dp algorithm was run with the optimal parameters that were determined in the previous section.
with blast, we simply compare the query sequence with all sequences in scop-db.
with fugue, we thread the query sequence into each one of the structural templates of the proteins in scop-db.
for reference, we also list the results obtained with the structure comparison algorithm urms  <cit> .
the urms results provide a rough upper bound on the expected performance since the algorithm is directly using the structural information which underlies many of the homology relationships in scop.
as table  <dig> shows, fugue improves the roc1-s and roc1-f indices by  <dig> and 9% over psiblast while the tss and tff indices are increased by a magnitude of  <dig> to 60%.
the distance-profile method dp-fugue improves over psiblast by more than 60% on all indices.
with respect to fugue, it increases by  <dig> and 94% the roc1-s, roc1-f indices and about 30% for both the tss and tff indices.
this margin of improvement over fugue is also maintained over the test set .
quantitatively, the roc1-s and roc1-f are improved by about 90% and the tss, tff indices by about 42%.
this is a substantial improvement that is larger than the relative improvement of psiblast with respect to blast or that of fugue with respect to psiblast, thus indicating that the statistical fingerprints of the distance-profile representation encode more information and are more sensitive than a direct comparison of the objects they operate on.
the distance-profile representation over sequence-profile metrics
to test the effectiveness of the distance-profile method on other types of input we applied it to feature vectors that were generated with psiblast, a sequence to profile alignment algorithm  <cit> .
the feature values are set to the log  of the similarity score, as reported by psiblast after four iterations, unless the program converged before .
the psiblast evalue-based feature vectors are processed in a similar fashion to the fugue zscore-based feature vectors.
each evalue e is mapped to its corresponding pvalue pvalue =  <dig> - exp as in  <cit>  and the value of the corresponding feature is defined as  <dig> - pvalue = exp.
if the evalue is greater than a given threshold τ' then we reset the value of the feature.
finally, the normalization converts the resulting feature vectors to probability distributions.
the parameters are optimized using a similar procedure to the one described in section 'parameter optimization'.
the optimal parameters are sought among the combinations of  <dig> evalue cutoff thresholds , two association measures , pprob ) and three possible metrics .
in this case, the best combination based on the training set is .
the effect of multiple sequence alignment on the performance
all our experiments were performed in a single-query mode.
i.e.
in each test case a single query sequence is compared against the database.
however, there are multiple reports  <cit>  that suggest that significant performance gain can be obtained when using a multiple sequence alignment  or a sequence profile as a query.
to test the effect of msa on the performance we had the change our experimental setup.
we tested the impact of the new setting on psiblast and fugue based on  <dig> scop families that were randomly chosen from all families for which the performance of psiblast and fugue was poor.
for each family we generated a msa of all sequences in the family using clustalw  <cit> .
each msa was also converted to a position specific scoring matrix .
these msa were used as queries for fugue  and the profiles as input for psiblast, in search for related sequences in scop-db.
to fairly compare the results of psiblast and fugue in the msa mode to the dp method we had to run our method under a similar setup.
the "msa" mode of the dp method utilizes the information from all the sequences in a protein family in the same spirit a msa does so, by combining the distance profiles associated to each member of the scop family.
for each sequence in scop-db, we take the average of its distance versus each member of the family in question in order to compute the "family-specific" distances with respect to scop-db.
in table  <dig>  we summarize for each of the scop families the performance of fugue, psiblast and dp-fugue under the msa-query mode.
family members are not counted since they were already used to build the msa.
the adjusted indices thus indicate how many remote homologs are discovered in the msa-query mode.
for comparison we also report the average performance under the single-query mode.
as the results demonstrate, the msa mode improves over the standard single mode, and in most cases our method performs better than fugue and psiblast, in particular in terms of the tss index .
it should be noted that when we analyzed fugue in a similar manner to dp-fugue  the results improved over the msa mode of fugue, but not as much as dp-fugue in msa mode.
we should comment that the msa setup differs from our original idea of using the dp representation to perform unsupervised clustering of objects based on their distance profile.
in the unsupervised learning mode we do not have information on the family association of each sequence, and therefore it is difficult to define the exact set of related sequences from which to generate a multiple sequence alignment.
superfamily and fold prediction with the distance-profile method
we tested the power of our method on a new set of protein sequences that were added to scop after we compiled our benchmark.
our goal was to test if the method can classify new sequences to their correct class.
the new set consists of proteins in release  <dig>  of scop that were not included in our scop-db dataset  and either belong to new families within existing superfamilies, new superfamilies within known folds or completely new folds.
for instance, the family b.
<dig> .
<dig> did not exist in the scop  <dig>  database.
this family is part of the b.
<dig>  superfamily that in release  <dig>  contains the families b.
<dig> .
<dig>  b.
<dig> .
<dig>  b.
<dig> .
<dig> and a total of  <dig> representatives in our reference set.
in total we found  <dig> sequences belonging to  <dig> new families within known superfamilies,  <dig> sequences associated to  <dig> new superfamilies within known folds and  <dig> sequences in  <dig> new folds, all with less than 40% identity between pairs of sequences.
each one of these new sequences was compared against all the sequences in scop-db using all of the methods evaluated in this paper, and the matches were sorted based on the score or distance, as before.
to apply the distance-profile method the sequences were first processed and mapped to feature vectors as described in section 'results'.
CONCLUSIONS
we study a new method for remote homology detection that utilizes global information on the proximity of entities in the protein space.
our method relies on the distance-profile representation of proteins and protein families that maps each query protein to a high-dimensional feature space, where the coordinates are determined by some association measures with respect to a reference set.
these vectors are then processed and transformed to sparse feature vectors that are treated as statistical fingerprints of the query proteins.
we experimented with several different types of association measures and demonstrated how an adequate choice of distance metric combined with a proper transformation of the feature vectors through noise reduction, pvalue conversion and normalization can greatly increase the performance of homology recognition  compared to the existing approaches.
interestingly, excellent performance is obtained with normalized feature vectors that correspond to probability distributions.
the success of the distance-profile method in general and especially when using probability distributions suggests a relation to mixture models  <cit> .
specifically, one can consider this representation as the coefficients of a mixture model or of a functional expansion, similar to the taylor polynomial expansion.
given a set of basis functions such as polynomial functions one can span the complete space of continuous well-behaved functions with the right coefficients.
the same principle applies here as our reference set essentially defines a set of basis functions.
in statistical terms, each element of the reference set induces a different probability distribution over the protein sequence space.
in our experiments the reference set is composed of protein structures, each one can be perceived as a different generative model.
the likelihood of generating a sequence according to a model can be estimated by computing the probability that the sequence will fold into the corresponding structure, as measured with the pvalue association measure over the threading similarity score.
although these probability distributions  do not necessarily meet the requirement of orthogonality to be considered "basis functions", a sufficiently diverged set of proteins is expected to have the desired properties.
it has yet to be defined more precisely what sufficiently diverged means and the minimal required diversity.
one intriguing aspect that has not been fully addressed is the interaction between the association function, the distance metric and the zscore cutoff value.
in some cases the coupling is not surprising.
for example, when the prob association function is used, the l <dig> metric clearly underperforms compared to l <dig> and js metrics, as expected, since the vectors compared correspond to probability distributions.
with the other association measures, l <dig> and l <dig> perform similarly.
study of the theoretical aspect of this phenomenon will help understand how to take further advantage of these feature vectors to cluster the protein sequences more accurately.
a word of caution is in order here regarding the evaluation.
while scop is considered the gold standard, it is not perfect and often one can find mis-classifications  <cit> .
while it is hard to estimate the exact rate of errors, it is unlikely that they exceed thousands and we do not anticipate the results to change drastically even if these mis-classification were corrected.
we should also mention that the dp representation is not effective for detailed, atom-resolution prediction of 3d structure or for site-specific functional annotation, since it cannot produce alignments.
another weakness is that the distance-profile representation and the new pvalue-distance measure may fail to distinguish two proteins if they have almost identical "preferences" for the known structures but different preferences for other, unknown structures that are yet to be determined.
however, given the current size of the protein structure space, it is expected that for most proteins the available structural information  is sufficient to estimate their proximity.
indeed, only 20% of the new scop  <dig>  sequences were assigned to new folds, clearly, as more structures are determined and integrated into the reference set, the distance-profile representation is expected to improve.
one potential contribution of this work is the possibility of combining the transformations described in section 'processing feature vectors' to the feature vectors used by existing kernel methods.
these techniques can effectively reduce noise and increase the accuracy of classification of the feature space.
in addition, since the feature vectors are typically sparse after noise reduction, an efficient computation of the kernel function can be implemented in a high-dimensional feature space.
finally, a major advantage of the distance-profile representation is in its great flexibility.
the underlying association measure can be based on sequence, structure, predicted function, threading, or any other similarity measure.
clearly, more distinctive association measures will create better representations.
indeed, the fugue zscore is clearly a better choice than the psiblast evalue since fugue exploits sequence-structure alignment information rather than just sequence alignment information.
if the association measure can report a significance value  that emphasizes extremes and pinpoint the interesting cases, the statistical measure will be preferred over the raw score.
this is especially useful when the raw score is meaningless by itself.
in these cases one needs a yardstick or a scale to tell what is close and what is far and the statistical estimates provide such a scale.
nevertheless, it is important to note that the distance-profile representation and the induced similarity measure are quite robust and work well even with raw association scores, noisy or corrupted data, and weak signal-to-noise ratio  <cit> .
all our data, including the fugue results, the psiblast results and the feature vectors are available at  <cit> .
authors' contributions
ck implemented the model, ran experiments, compared to other models, analyzed the result sets and wrote parts of the manuscript.
gy conceived of the study, designed the model and the experiments, analyzed results and drafted the manuscript.
appendix
the sequence-structure association measure
historically, sequence-structure threading  <cit>  was proposed as an alternative approach to predict the structural fold of polypeptide chains.
in contrast to ab initio strategies that exploit secondary structure prediction, energy minimization and molecular dynamics to predict the structure of a protein sequence, sequence-structure threading consists of finding native-like folding structure for a query protein from a database of known structures.
its motivation originates from the observation that proteins adopt a limited number of spatial architectures and that larger proteins are frequently composed of modules that can be found in other proteins.
to perform sequence-structure threading of a query sequence, the process typically starts by obtaining a set of structural conformations from a database of known structures.
the amino acid sequence of the query protein is aligned to each conformation in search of an alignment that would produce the minimal total energy .
the most likely candidate conformations are the ones yielding the lowest energy.
if the energy values are significantly low compared for example to those obtained for shuffled sequences, then these structural conformations can be considered as compatible with the query sequence.
many different approaches and implementations of threading algorithms have been proposed in the past  <cit> .
the exact details of the alignment algorithm and the computation of the total energy vary from one method to another.
unfortunately, most of them are not publicly available to allow an extensive comparison of sequences and structures.
of the few that are available, we chose fugue for our study.
fugue  <cit>  is a sequence-structure alignment algorithm that uses environment-specific substitution tables and structure-dependent gap penalties to evaluate the alignment score.
it switches between local and global alignment based on the ratio between the length of the query sequence and that of the structural profile.
previous experimental results have shown that fugue outperforms other methods in fold recognition such as psiblast  <cit> , sam-psiblast  <cit> , hmmer-psiblast  <cit> , threader  <cit>  and genthreader  <cit> .
it is worth mentioning that fugue should be considered as a structure-based sequence alignment algorithm rather than a sequence-structure alignment algorithm per se, since it does not involve the definition and the minimization of any energy function to measure the goodness of fit of the query sequence to the template structure.
however, its use of substitution tables and structure-dependent parameters provides additional information which is unavailable to pure sequence-based methods.
in fugue, the compatibility of each sequence-structure pair is assessed through the zscore, which measures the departure of the observed threading score value from its mean, normalized by the standard deviation  does not necessarily equal to s. actually, for most protein pairs the equality s = s does not hold, as different protein structures have different "sequence capacities".
these capacities affect the ability of an arbitrary sequence to conform with the given structure, and therefore also the probability that the structure will be energetically favorable for the given sequence.
however, the asymmetry may be a fundamental feature of the protein space that we may want to preserve and study later on in our analysis.
the statistical significance of the pd measure
we computed the distribution of pvalue-distances  between pairs of feature vectors ppvalue of unrelated protein sequences.
the distribution is a complex one, and features multiple modes .
each mode corresponds to the occurrence of one additional term in the summation contributing to the final value of the pd measure as described in eq , i.e.
the two feature vectors share one additional entry where the pvalues are both significant.
one may characterize the pd measure as the sum of a random number of evd random variables.
unfortunately, analysis of such a distribution is generally intractable and therefore we can only estimate the significance level of our pd measure based on the empirical distribution.
in figure 6b, we plot the distribution of the pd measure over its full range  in log scale.
we observe that the frequency of occurrence of large pd values  decreases exponentially, i.e.
linearly in log scale .
this phenomenon can be explained by examining again the definition of the pd measure given in .
if we consider a zscore as a random variable, its associated pvalue is a random variable uniformly distributed between  <dig> and  <dig>  based on the assumption that pi1
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgwbacdaqhaawcbagaemyaakgabagaegymaedaaaaa@308f@ and pi2
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgwbacdaqhaawcbagaemyaakgabagaegomaidaaaaa@3091@ are independent , max follows a triangular distribution and -log max is an exponential random variable.
therefore, -log pd can be viewed as a sum of exponential random variables.
from the statistical literature, we know that the sum of k independent and identically distributed exponential random variables with parameter α can be modeled by the gamma function.
fg=xk−1e−x/ααkΓ
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgmbgzdawgaawcbagaem4raceabeaakiabcicaoiabdiha4jabcuda7iabdugarjabcycasiabeg7ahjabcmcapiabg2da9maalaaabagaemieag3aawbaasqabeaacqwgrbwacqghsislcqaixaqmaagccqwglbqzdaahaawcbeqaaiabgkhitiabdiha4jabc+caviabeg7ahbaaaoqaaiabeg7ahnaacaaaleqabagaem4aasgaaogaeu4kdckaeiikagiaem4aasmaeiykakcaaiaaxmaacawljawaaewaaeaacqai1aqnaiaawicacaglpaaaaaa@4f41@
for large x, we have
log⁡fg=ε−xα+log⁡x∝−xα
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacyggsbabcqggvbwbcqggnbwzcqwgmbgzdawgaawcbagaem4raceabeaakiabcicaoiabdiha4jabcuda7iabdugarjabcycasiabeg7ahjabcmcapiabg2da9iabew7aljabgkhitmaalaaabagaemieaghabagaeqysdegaaiabgucariabcicaoiabdugarjabgkhitiabigdaxiabcmcapigbcygasjabc+gavjabceganjabdiha4jabg2hi1kabgkhitmaalaaabagaemieaghabagaeqysdegaaiaaxmaacawljawaaewaaeaacqai2agnaiaawicacaglpaaaaaa@56fa@
where ε is an additive constant.
hence, log fg approximately decreases with x in a linear fashion.
in our case, clearly the summands in  are not independent of each other since the reference set is composed of groups of related sequences.
nonetheless, one may expect that the dependency is not too strong because these sequences share less than 40% sequence identity.
the plot indeed suggests that the distribution of the pd measure follows this trend.
examples of homology detection
tables  <dig> and  <dig> list the closest neighbors of the protein queries d2tgf__  and d1hdoa_   with each one of the five competing methods.
as these demonstrate, a significantly larger number of proteins that are biologically related to the query sequence are placed at the top of the neighbor list with the distance-profile method.
for example, the protein domain g. <dig> .
<dig>  belongs to the superfamily g. <dig>  which contains  <dig> entries in the scop-db database.
both psiblast and blast detect  <dig> true positives  before encountering the first false positive  d. <dig> .
<dig>  , whereas dp-psiblast extends the roc1-s index to  <dig>  fugue starts with  <dig> tp at the top of the sorted list and our dp-fugue method further improves the index to  <dig> tp.
the differences for the protein domain c. <dig> .
<dig>  are even more substantial, with blast, psiblast and dp-psiblast reporting only two tp before the first fp, fugue reporting  <dig> tp, while dp-fugue reporting  <dig> tp, thus significantly enhancing the clustering of the members of the superfamily c. <dig> .
we observe that the performance of the dp method depends on the configuration of the sorted list obtained using the initial association measure.
our method works best when some true positives can be found among the top ones on the list, even if proceeded by or mixed with false positives; it refines the results by clustering even closer the similar elements while pushing further away the false positives.
our method does not improve the results in the case of c. <dig> .
<dig> .
however, we note that this is a difficult case of homology detection since there are more than  <dig> members in the superfamily c. <dig>  while all methods detect only a very few true positives at the top of the sorted list.
there are several cases where fugue lists a fp at the top of the list but a couple of tps are among the closest ones.
in these cases, dp can enhance the mapping and improve over fugue, as is also demonstarted in figure  <dig>  however, when there is only one tp at the top of the list, our method does not always improve over fugue.
this is most difficult when the top true positive match is only marginally higher than the first false positive.

 the ongoing sequencing efforts continue to discover the sequences of many new proteins, whose function is unknown. currently, protein databases contain the sequences of about, proteins, of which more than half are partially or completely uncharacterized. typically, proteins are analyzed by searching for homologous proteins that have already been characterized. homology establishes the evolutionary relationship among different organisms, and the biological properties of uncharacterized proteins can often be inferred from those of homologous proteins. however, detecting homology between proteins can be a difficult task. our ability to detect subtle similarities between proteins depends strongly on the representations we employ for proteins. sequence and structure are two possible representations of proteins that hinge directly on molecular information. the essential difference between the representation of a protein as a sequence of amino acids and its representation as a 3d structure traditionally dictated different methodologies, different similarity or distance measures and different comparison algorithms. the power of these representations in detecting remote homologies differ markedly. despite extensive efforts, current methods for sequence analysis often fail to detect remote homologies for sequences that have diverged greatly. in contrast, structure is often conserved more than sequence, and detecting structural similarity may help infer function beyond what is possible with sequence analysis. however, structural information is sparse and available for only a small part of the protein space. one may argue that the weakness of sequence based methods is rooted in the underlying representation of proteins, the model used for comparison and/or the comparison algorithm, since in principle, according to the central dogma of molecular biology, all the information that is needed to form the 3d structure is encoded in the sequence. indeed, in recent years better sequence-based methods were developed. these methods utilize the information in groups of related sequences to build specific statistical models associated to different groups of proteins that can be used to search and detect subtle similarities with remotely related proteins. such generative models assume a statistical source that generates instances according to some underlying distributions, and model the process that generates samples and the corresponding distributions. when seeking a new similarity measure for proteins that departs from sequence and structure, a natural question is what is the "correct" encoding of proteins? several works studied the mathematical representation of protein sequences based on sequence properties such as amino acid composition or chemical features. however, these representations had limited success, since they did not capture the essence of proteins as ordered sequences of amino acids. recently, alternative representations of protein sequences based on the so-called kernel methods were proposed. these methods are drawn from the field of machine learning and strive to find an adequate mapping of the protein space onto the euclidean space where classification techniques such as support vector machines or artificial neural networks can be applied. under the kernel representation, each protein is typically mapped to a vector in a feature space, and the resulting vector is termed feature vector. subsequently, an inner product is defined in the feature space in order to estimate the similarity among different proteins. a major advantage of the kernel methods is that with an adequate choice of the kernel function, the feature vectors need not be computed explicitly in order to evaluate the similarity relationships. in addition, the users may build a specific feature space such that the kernel function directly estimates these relationships. however, string kernels do not easily lend themselves to this property, and therefore they need to be computed explicitly. the main difference between the different kernel methods reside in the definition of feature elements which are either related to the parameters of some generative process for each group of related proteins or some measure of similarity among the protein sequences. for instance, the svm-fisher algorithm uses the fisher kernel which is based on hidden markov models. the components of the feature vector are the derivatives of the log-likelihood score of the sequence with respect to the parameters of a hmm that has been trained for a particular protein family. tsuda et. al. implemented another representation based on marginalized and joint kernels and showed that the fisher kernel is in fact a special case of marginalized kernel. they also experimented with the marginalized count kernels of different orders, that are similar to the spectrum kernel which was first introduced by. the spectrum kernel is evaluated by counting the number of times each possible k-long subsequence of amino acids occurs in one given protein. the marginalized count kernel takes into account both the observed frequency of different subsequences and the context. the mismatch-spectrum kernel is a generalization of the spectrum kernel that considers also mutation probabilities between k-mers which differ by no more than m characters. the homology kernel is another biologically motivated sequence embedding process that measures the similarity between two proteins by taking into account their respective groups of homologous sequences. it can be thought of as an extension of the mismatch-spectrum kernel by adding a wildcard character and distinguishing the mismatch penalty between two substrings depending on whether the sequences are grouped together or not. the covariance kernel is another type of kernel that uses a framework similar to the one employed by our method. the covariance kernel approach is probabilistic and much work is focused on the implementation of the generative models. in, the covariance kernel is based on the mutual information kernel which measures the similarity between data samples and a certain generative process. the generative process is characterized by a mediator distribution defined between the prior and the posterior distribution. on the other hand, focuses on the representation of biological sequences using the probabilistic suffix tree as the generative model for different groups of related proteins. the proposed kernel generates a feature vector for protein sequences, where each feature corresponds to a different generative model and its value is the likelihood of the sequence based on that model. finally, we mention another related work that uses the notion of pairwise kernel. under this framework, each protein is represented by a vector that consists of pairwise sequence similarities with respect to the set of input sequences. it is also worth mentioning the many related studies in the field of natural language processing and text analysis. for example, an approach that in some ways is similar to the pairwise and covariance kernels and in other ways is related to the spectrum kernel approach, is used in to represent verbs and nouns in english texts, with nouns represented as frequency vectors over the set of verbs and vice versa. the nouns and verbs are then clustered based on this representation. studies that attempted to devise automatic methods for text categorization and web-page classification often use similar techniques, where the text is represented as a histogram vector over a vocabulary of words. here we study a general framework of protein representation called the distance-profile representation, that utilizes the global information in the protein space in search of statistical regularities. the representation draws on an association measure between input samples and can use existing measures of similarity, distance or probability. this representation induces a new measure of similarity for all protein pairs based on their vectorial representations. our representation is closely related to the covariance and pairwise kernels described above. however, it is the estimation of pvalues through statistical modeling of the background process, coupled with the transformation to probability distributions, the noise reduction protocols and the choice of the distance function that result in a substantial impact on the performance, and we demonstrate how an adequate choice of the score transformation and the distance metric achieves a considerable improvement in detection of remote homologies. this paper is organized as follows. we first introduce the notion of distance-profile. we describe how to process the feature vectors through noise reduction, and pvalue transformation followed by normalization. we compare the performance of our new method against several standard algorithms by testing them on a large set of protein families.  the distance-profile representation our goal is to seek a faithful representation of the protein space that will reflect evolutionary distances even if undetectable by means of existing methods of comparison. we explore a technique based on the distance-profile technique described in and its derivative as applied to protein sequences in. the power of the representation stems from its ability to recover structure in noisy data and boost weak signals. the distance-profile representation is simple and can be applied to arbitrary spaces x mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@, y mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ if there exist an association measure between instances of x mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@ and instances of y mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ such as a distance function, similarity function or a probability measure. given an instance x in the input space x mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@, a reference set {y y... yn} of entities in y mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ and an underlying association measure, we associate with the instance x a position in a high dimensional space, where every coordinate is associated with one member of the reference set and its value is the similarity with that particular reference object. i.e., we map x to a vector of dimension n in the host space x→x=⋮s).      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgybawcqghsgirtcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8hwaiabg2da9maabmaabaqbaeqabmqaaaqaaiabdofatjaaykw7daqadaqaaiabdifayjabcycasiabdmfaznaabaaaleaacqaixaqmaeqaaagccagloagaayzkaaaabagaeso7i0eabagaem4uam1aaewaaeaacqwgybawcqggsaalcqwgzbqwdawgaawcbagaemoba4gabeaaaogaayjkaiaawmcaaaaaaiaawicacaglpaaacqgguaglcawljagaaczcamaabmaabagaegymaedacagloagaayzkaaaaaa@54ca@ this simple representation leads to the definition of a new distance or similarity measure among samples based on their vectorial representation, and when the reference set is identical to the input space, an iterative application of this representation can be used to form hierarchical clustering over the input samples. in this paper we demonstrate the application of this method to the problem of homology detection between distantly related proteins. one might observe the resemblance of our method with pairwise kernels and covariance kernels mentioned in the'background' section. however, it is the processing of the feature vectors and the choice of the metric, as is laid out next, which are the crucial ingredients that differentiate our method from the previous studies. as exemplified in this paper, under the proper transformations the distance-profile representation has mathematical and statistical interpretations that have other implications, and it is these transformations that deem this method very effective for homology detection, database search and clustering. the reference set remotely related proteins usually share little sequence similarity, however, they are expected to have similar structures. therefore, as a reference set for our experiments we chose a non-redundant structure library consisting of domain structures that represent the current protein structure space. the set is derived from the scop database, release. specifically, we used the genetic domain sequence dataset that we downloaded from the astral webpage. the dataset is obtained from entries in the protein data bank and contains only protein domains with less than 40% identity between pairs of sequences. our library consists of distinct scop domains covering in total folds, superfamilies, and families. for notation purpose, we denote this library of template proteins by scop-db. the association measure we rely on "structure-aided" sequence alignment to bridge the gap between the sequence space and structure space. given the library of structures y mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@ = {y y y..., yn}, every protein sequence p is mapped to a structure-specific n-dimensional feature vector, as is described above, where the association measure s is the similarity score of the sequence-structure alignment between the sequence p and the template structure yi, computed with the fugue threading algorithm. from this point on we discuss the application of the distance-profile representation with threading-based association measures. however, we note that the methods described in this paper can be used to process feature vectors using other association measures. in the'discussion' section we show that a similar approach applied to sequence-profile alignment scores also produces a considerable improvement in detecting remote homologies. processing feature vectors: pvalue conversion and normalization the choice of the underlying association function s can have a drastic impact on the effectiveness of the representation and we tested several variations. the score association measure a possible choice is obviously the score reported by the algorithm that compares entities of x mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfybaaaa@3973@ with entities of y mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamxvp5wqsxmqhnxajn0bkvguhdwzzbqegm0b1jxaljhiov2daebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacawfzbaaaa@3974@.. we denote feature vectors that are based on the score association measure by pscore. the pvalue association measure if the association measure is distributed over a wide range, the most significant scores will inevitably shadow other numerically less important but still significant matches, thus reducing the sensitivity of the representation. this is the case with most types of similarity scores, including the threading zscores assigned by the fugue program. to address this problem we convert the zscores to their underlying cumulative distribution function value, where the amplitude of outlier zscores is reduced to within a reasonable range. as was shown in, the zscores of local alignment scores follow the extreme value distribution, see figure whose cumulative function f takes the form f = prob = e-φ     where    φ = e-λ.     based on this background distribution we replace the original zscores with a new association measure such that s' = f) where s is the similarity zscore reported by fugue. with this transformation, all coordinates are bounded between and with high zscores transformed to values close to note that the pvalue of a given zscore x is pvalue = - f. we denote feature vectors that are based on the f association measure by ppvalue. it should also be noted that in practice f = - pvalue = for large x because of machine precision limitations. therefore, the pvalues that are associated to significant zscores are approximated by their empirical distribution, thus allowing distinction between a pair of highly significant yet numerically disparate zscores, e.g. versus the probability association measure the third variation we tested is based on a simple normalization of each feature vector to form a probability distribution. this transformation enables us to explore distance measures that are suited for probability vectors, as described in section'metrics and score functions'. indeed, in this representation, the normalized vector entries can be considered as the coefficients of a mixture model where the components models are the protein structures, each one inducing a different probability distribution over the protein sequence space. this interpretation emphasizes the similarity with covariance methods which also resort to a probabilistic representation of different protein families as described in the'background' section. we denote feature vectors that are based on this association measure by pprob. reducing noise: sparse feature vectors our reference set is composed of proteins that belong to different protein families and folds. within that data set no two proteins share more than 40% sequence identity. therefore, for a given query protein we expect to observe only a few significant similarity values in the vector p. that is, the entries that correspond to the structural templates of protein families that are related to the query. in other words, the feature vectors contain many entries that are essentially random and meaningless. these random numbers will contribute to the differences between feature vectors, thus masking possibly significant similarities. to reduce noise due to unrelated proteins we eliminate all entries with zscore below a certain threshold τ, or pvalue above a certain threshold τ', to reflect the fact that the corresponding sequence-structure pair is considered irrelevant the parameter τ is optimized to maximize performance, as described in section'parameter optimization'. note that entries with low zscores that are filtered in this step remain zero under the transformation to the cdf pvalue as described above. the processed feature vector is denoted by p^score mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaatcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegab8huayaajawaawbaasqabeaacqwgzbwccqwgjbwycqwgvbwbcqwgybgccqwglbqzaaaaaa@3f2d@. the noise reduction is applied to the original feature vectors and is followed by the pvalue conversion and the normalization to yield new feature vectors ppvalue and pprob, respectively. to illustrate the impact of our procedures on the distance profiles, let us consider the example of two closely related proteins d1qmva_ and d1hd2a_ that belong to family c.. under the scop denomination. the sequences were threaded against the scop library of structural domains, and feature vectors were compiled from the zscores reported by fugue. in table we report the 2163th up to the 2169th entries of their original feature vectors as well as their transformations after noise reduction, pvalue conversion and normalization. as this example demonstrates, the zscore entries are noisy and spread over a wide numerical range. for instance, the 2167th entry of both vectors correspond to their threading score versus the structure of d1prxa_, another protein that is in the same scop family c.. while the zscore reaches for d1qmva_, it is only for d1hd2a_. these large differences will inevitably result in large distances between the feature vectors despite the fact that they have significant zscore values in the same positions. the pvalue conversion and normalization resolve this problem by rescaling scores to within a fixed interval. p^score metrics and score functions under the distance-profile representation, the similarity between two protein sequences p and p' is defined as the similarity of their corresponding feature vectors s = f the function f can be a similarity function or a distance function and we considered several different variants. we tested the l norm and the l norm. for probability distributions we also tested the jensen-shannon measure of divergence. given two probability distributions p and q, for every ≤ λ ≤ their λ-jensen-shannon divergence is defined as dλjs=λdkl+dkl mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgebardaqhaawcbagaeq4udwgabagaemosaokaem4uamfaaogaei4was1exlmbbxgbcf2cpn2qvrwzqf2zlnharygvljhzh5wyagabbiaa=bhacqgg8bafcqgg8bafcawfxbgaeiyxa0laeyypa0jaeq4udwmaemiraq0aawbaasqabeaacqwglbwscqwgmbataagccqggbbwwcawfwbgaeiifawnaeiifawnaa8ncaiabc2fadjabgucariabcicaoiabigdaxiabgkhitiabeu7asjabcmcapiabdseaenaacaaaleqabagaem4saskaemitaweaaogaei4waslaa8xcaiabcyha8jabcyha8jaa=jhacqggdbqxaaa@629d@ where dkl is the kullback-leibler divergence defined as dkl=∑ipilog⁡2piqi mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgebardaahaawcbeqaaiabduealjabdyeambaakiabcufabnxvp5wqsxmqhnxajn0bkvguhdwzzbqegyvzyrwyufgaiqqacawfwbgaeiifawnaeiifawnaa8xcaiabc2fadjabg2da9maaqababagaemicaa3aasbaasqaaiabdmgapbqabagccyggsbabcqggvbwbcqggnbwzdawgaawcbagaegomaidabeaakmaalaaabagaemicaa3aasbaasqaaiabdmgapbqabaaakeaacqwgxbqcdawgaawcbagaemyaakgabeaaaaaabagaemyaakgabeqdcqghris5aaaa@549a@ and r = λp + q can be considered as the most likely common source distribution of both distributions p and q, with λ as a prior weight. unlike the kullback-leibler measure, the js measure is symmetric and bounded. it ranges between and where the divergence for identical distributions is this measure has been used successfully in to detect subtle similarities between statistical models of protein families and in for automatic domain prediction from sequence information. as an alternative approach to assess the similarity of a pair of proteins based on their distance-profile representation we propose the pvalue-distance function. this function assesses the distance between two proteins by estimating the probability to observe a random protein with a feature vector inside the volume delimited by their two feature vectors. the smaller the volume is, the more similar are the two vectors. the function operates on the pvalues used to form the feature vectors ppvalue. given two feature vectors p and q that correspond to proteins p and q, we consider one coordinate i at a time and estimate the total probability mass of samples whose i-th feature is bounded between the feature values pi and qi as is illustrated in figure 2a. since each representative in the reference set induces a complex high-dimensional distribution over the protein sequence space, the one-dimensional pvalue measure pi can only serve to approximate a certain perimeter in the sequence space of sequences that are as similar or more similar to the i-th source than the protein p. therefore, we use the least significant pvalue of pi and qi as an upper bound estimator of the volume of relevant instances, as illustrated in figure 2b. the total volume is computed by taking the product over all coordinates. formally, consider the two pvalue feature vectors p1pvalue= mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaaieqacqwfqbaudaqhaawcbiqaacqccqwfxaqmaeaacqwfwbaccqwf2bgdcqwfhbqycqwfsbabcqwf1bqdcqwflbqzaagccqgh9aqpcqggoaakcqwgwbacdaqhaawcbagaegymaedabagaegymaedaaogaesojgskaemicaa3aa0baasqaaiabd6gaubqaaiabigdaxaaakiabcmcapaaa@4336@ and p2pvalue= mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaaieqacqwfqbaudaqhaawcbagae8nmaidabagae8hcaanae8ndaynae8xyaemae8hbawmae8xdaunae8xzaugaaogaeyypa0jaeiikagiaemicaa3aa0baasqaaiabigdaxaqaaiabikdayaaakiablaciljabdchawnaadaaaleaacqwgubgbaeaacqaiyagmaagccqggpaqkaaa@4288@ that are obtained by mapping each zscore zi to its pvalue pi using the evd background distribution as described in section'processing feature vectors'. their pvalue distance is defined as pd=∏i=1lmax⁡.      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgqbaucqwgebarcqggoaaktcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8huamaabaaaleaacawfxaaabeaakiabcycasiaa=bfadawgaawcbagaa8nmaaqabagccqggpaqkcqgh9aqpdaqewaqaaigbc2gatjabcggahjabciha4naabmaabagaemicaa3aa0baasqaaiabdmgapbqaaiabigdaxaaakiabcycasiabdchawnaadaaaleaacqwgpbqaaeaacqaiyagmaaaakiaawicacaglpaaaasqaaiabdmgapjabg2da9iabigdaxaqaaiabdyeambqdcqghpis1aogaeiola4iaaczcaiaaxmaadaqadaqaaiabiodazagaayjkaiaawmcaaaaa@59f8@ in practice, the pd score is evaluated through its logarithm: −log⁡pd=−∑i=1llog⁡max⁡      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqghsislcyggsbabcqggvbwbcqggnbwzcqwgqbaucqwgebarcqggoaaktcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8huamaabaaaleaacawfxaaabeaakiabcycasiaa=bfadawgaawcbagaa8nmaaqabagccqggpaqkcqgh9aqpcqghsisldaaewaqaaigbcygasjabc+gavjabceganjgbc2gatjabcggahjabciha4bwcbagaemyaakmaeyypa0jaegymaedabagaemitaweaniabgghildgcdaqadaqaaiabdchawnaadaaaleaacqwgpbqaaeaacqaixaqmaagccqggsaalcqwgwbacdaqhaawcbagaemyaakgabagaegomaidaaagccagloagaayzkaagaaczcaiaaxmaadaqadaqaaiabisda0agaayjkaiaawmcaaaaa@633d@ is used directly to define the feature values, as opposed to f = - pvalue that was used before when compiling the feature vectors ppvalue. however, to simplify notation we also refer to these feature vectors as ppvalue.) to distinguish all the measures discussed in this section from the association measures discussed in section'processing feature vectors', we refer to all of them from now on as distance metrics, although they are not necessarily metrics or distance functions. discussion dataset preparation we use the scop classification of protein structures as our benchmark. the scop database is built mostly based on manual analysis of protein structures and is characterized by a hierarchy with four main levels: class, fold, superfamily and family. proteins that belong to the same family display significant sequence similarity that indicates homology. at the next level, families are grouped into superfamilies based on structural similarity and weak sequence similarity. proteins that belong to different families within the same superfamily are considered remotely related. it is this level that has been used in many studies to evaluate sequence comparison algorithms. the challenge is to automatically detect similarities between families within the same superfamily, that were established manually by the scop experts. to determine the optimal parameters for the distance-profile representation and compare its performance to other algorithms, we split the library scop-db into a training set and a test set. since our purpose is to test the ability to find remotely related proteins at the superfamily and fold levels, we first discard all proteins that have fewer than remote homologs in scop-db. from the remaining sequences we randomly select for the training set, and the rest are compiled into the test set. performance indices to evaluate the performance of a given method for a specific query protein we compare the protein against scop-db, sort the results and assess the correlation of the sorted list with established homology relations. in our experiments we consider two proteins to be related if they belong to the same scop superfamily. all other pairs are treated as negatives. we also consider a more relaxed definition, where proteins are deemed related if they belong to the same scop fold. a popular measure of performance used in signal detection and classification is the rock measure. this is the cumulative count of positive samples detected until k negative samples are met in the sorted list of results. we use four different indices to assess performance, all are variations on commonly used sensitivity and accuracy measures. these indices measure the ability of a given algorithm to recognize different levels of structural similarity between protein sequences and within neighborhoods of varying sizes: • the roc superfamily index. • the roc1-fold index. • the top-superfamily-superfamily index. • the top-fold-fold index. given the sorted list of results for a query protein p, the roc1-s index totals the number of proteins in the same superfamily as p that are observed from the top of the sorted list until the first false match appears. likewise, the roc1-f index is defined by counting the number of proteins in the same fold as p from the top of the sorted list until the first match that involves two proteins with different folds. the last two indices are characterized by the following generic definition: the top-x-y index for a protein p counts the total number of proteins sharing the same y scop denomination among the nx closest sequences of p, where nx is the total number of sequences in the library that have the same x scop denomination as p itself. self-similarity is ignored in the assessment of all performance indices. note that all these indices are closely related to sensitivity measures at different levels, however, the relevant neighborhood is calibrated on a per-superfamily/fold basis. and while the two roc indices stop as soon as one false match is encountered, the top-x-y indices credit a method that detects many true positives at the top even if mixed with a few false positives. therefore, a method yielding a lower roc index but higher tss should be still considered successful since it clusters the query close to a larger number of related objects. to obtain the overall performance of a method with respect to a set of queries, we simply take the sum of all their corresponding performance indices as the global result. i.e. given a query set q = {q..., qn}, the performance of a method m, using index i is i=∑i=1ni mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgjbqscqggoaakcqwgnbqtcqggsaaltcvaufebsjuyzl2yd9gzlbvynv2caehbwvmckfmbhbaceegaa8xuaiabcmcapiabg2da9maaqahabagaemysakkaeiikagiaemyta0kaeiilawiaemycae3aasbaasqaaiabdmgapbqabagccqggpaqkasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaubqdcqghris5aaaa@4ca6@ where i is the performance of the method m for the protein qi is the tff performance of fugue on protein qi). normalized performance indices the global performance indices might be affected by the specific make up of the query set, since superfamilies and folds vary greatly in size. in order to reduce a potential bias due to large superfamilies/folds that perform very well, we use also normalized performance indices. to compute these, we divide each index by its upper bound, i.e. the total number of proteins in the scop-db library that are classified to the same superfamily/fold as the query. for example, for a query protein q that belongs to a fold f of size nf the normalized tff measure is given by tffn = tff / this ratio is essentially the sensitivity of the method m on the query q, over a match list of size nf. the size of the relevant match list changes with each query. the resulting ratios are then averaged at the superfamily level so as to obtain a representative average performance index per protein superfamily that is bounded between and finally, the final index is computed by averaging over all the representative indices. i.e. given a query set q = {q..., qn} that are classified to k different superfamilies f..., fk with ni queries in superfamily fi, then the overall performance of a method m, using the normalized index in is given by in=1k∑i=1k1ni∑q∈fiin mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgjbqsdaahaawcbeqaaiabd6eaobaakiabcicaoiabd2eanjabcycasmxvp5wqsxmqhnxajn0bkvguhdwzzbqegyvzyrwyufgaiqqacawfrbgaeiykakiaeyypa0zaasaaaeaacqaixaqmaeaacqwgrbwaaawaaabcaeaadawcaaqaaiabigdaxaqaaiabd6gaunaabaaaleaacqwgpbqaaeqaaaaakmaaqafabagaemysak0aawbaasqabeaacqwgobgtaagccqggoaakcqwgnbqtcqggsaalcqwgxbqccqggpaqkasqaaiabdghaxjabgigiolabdaeagnaabaaameaacqwgpbqaaeqaaawcbeqdcqghris5aawcbagaemyaakmaeyypa0jaegymaedabagaem4aasganiabgghildaaaa@5bd6@ parameter optimization our method depends on three parameters: the noise reduction level, the association measure and the distance metric. we consider all possible combinations among five zscore cutoff values, three association measures that are pscore, ppvalue and pprob, and four distance metrics: l l the js divergence measure and the new pvalue-distance measure. note that the js measure is only applicable to normalized vectors since it requires the input vector to represent a probability distribution and the pd measure is only applicable to the pvalue vectors. to find the best parameters we first establish the feature vectors for each sequence in scop-db. each combination of an association function and a noise threshold τleads to a different set of feature vectors. next, we compute the distance between the feature vector of each training sequence and the vectors of all sequences in scop-db, using one of the distance metrics of section'metrics and score functions'. each combination of feature vectors and a distance metric results in a different set of "match lists". these sets are then evaluated using the performance indices described above. the results are reported in table for clarity, the best combination of parameters is printed in boldface for each index. to determine the optimal set of parameters, we first examine the effect of the association function. the results are unanimous with all five performance indices: the pvalue association measure achieves the best performance, followed by the prob association measure. however, the pvalue association measure is only effective when coupled with the pd distance metric, while the prob association measure seems to produce good results with all distance metrics and especially with l and the js divergence measure. as for the distance metric, its influence depends on the association function. the pd measure is applicable only to the pvalue vectors but it produces excellent results, much better than the traditional l and l metrics. under the prob association measure, li and js metrics produce the best results while l leads to significantly worse performance. with the two other association measures l and l metrics yield similar results. finally, the optimal value of τis approximately around for most combinations. in conclusion, these results suggest that the best performance is achieved with the pvalue association measure, the pvalue-distance metric and a zscore cutoff threshold τ=. the same conclusions are reached when using the normalized performance indices. it should be noted that although the prob association measure is not as good as the pvalue measure, it still produces very good performance overall, further justifying the statistical interpretation of our representation and its equivalence with the coefficients of a mixture model over independent sources. performance comparison we compare the performance of our algorithm against several existing algorithms, namely fugue, blast and psiblast. table reports the results for all algorithms based on the training sequences. the dp algorithm was run with the optimal parameters that were determined in the previous section. with blast, we simply compare the query sequence with all sequences in scop-db. with fugue, we thread the query sequence into each one of the structural templates of the proteins in scop-db. for reference, we also list the results obtained with the structure comparison algorithm urms. the urms results provide a rough upper bound on the expected performance since the algorithm is directly using the structural information which underlies many of the homology relationships in scop. as table shows, fugue improves the roc1-s and roc1-f indices by and 9% over psiblast while the tss and tff indices are increased by a magnitude of to 60%. the distance-profile method dp-fugue improves over psiblast by more than 60% on all indices. with respect to fugue, it increases by and 94% the roc1-s, roc1-f indices and about 30% for both the tss and tff indices. this margin of improvement over fugue is also maintained over the test set. quantitatively, the roc1-s and roc1-f are improved by about 90% and the tss, tff indices by about 42%. this is a substantial improvement that is larger than the relative improvement of psiblast with respect to blast or that of fugue with respect to psiblast, thus indicating that the statistical fingerprints of the distance-profile representation encode more information and are more sensitive than a direct comparison of the objects they operate on. the distance-profile representation over sequence-profile metrics to test the effectiveness of the distance-profile method on other types of input we applied it to feature vectors that were generated with psiblast, a sequence to profile alignment algorithm. the feature values are set to the log of the similarity score, as reported by psiblast after four iterations, unless the program converged before. the psiblast evalue-based feature vectors are processed in a similar fashion to the fugue zscore-based feature vectors. each evalue e is mapped to its corresponding pvalue pvalue = - exp as in and the value of the corresponding feature is defined as - pvalue = exp. if the evalue is greater than a given threshold τ' then we reset the value of the feature. finally, the normalization converts the resulting feature vectors to probability distributions. the parameters are optimized using a similar procedure to the one described in section'parameter optimization'. the optimal parameters are sought among the combinations of evalue cutoff thresholds, two association measures, pprob ) and three possible metrics. in this case, the best combination based on the training set is. the effect of multiple sequence alignment on the performance all our experiments were performed in a single-query mode. i.e. in each test case a single query sequence is compared against the database. however, there are multiple reports that suggest that significant performance gain can be obtained when using a multiple sequence alignment or a sequence profile as a query. to test the effect of msa on the performance we had the change our experimental setup. we tested the impact of the new setting on psiblast and fugue based on scop families that were randomly chosen from all families for which the performance of psiblast and fugue was poor. for each family we generated a msa of all sequences in the family using clustalw. each msa was also converted to a position specific scoring matrix. these msa were used as queries for fugue and the profiles as input for psiblast, in search for related sequences in scop-db. to fairly compare the results of psiblast and fugue in the msa mode to the dp method we had to run our method under a similar setup. the "msa" mode of the dp method utilizes the information from all the sequences in a protein family in the same spirit a msa does so, by combining the distance profiles associated to each member of the scop family. for each sequence in scop-db, we take the average of its distance versus each member of the family in question in order to compute the "family-specific" distances with respect to scop-db. in table we summarize for each of the scop families the performance of fugue, psiblast and dp-fugue under the msa-query mode. family members are not counted since they were already used to build the msa. the adjusted indices thus indicate how many remote homologs are discovered in the msa-query mode. for comparison we also report the average performance under the single-query mode. as the results demonstrate, the msa mode improves over the standard single mode, and in most cases our method performs better than fugue and psiblast, in particular in terms of the tss index. it should be noted that when we analyzed fugue in a similar manner to dp-fugue the results improved over the msa mode of fugue, but not as much as dp-fugue in msa mode. we should comment that the msa setup differs from our original idea of using the dp representation to perform unsupervised clustering of objects based on their distance profile. in the unsupervised learning mode we do not have information on the family association of each sequence, and therefore it is difficult to define the exact set of related sequences from which to generate a multiple sequence alignment. superfamily and fold prediction with the distance-profile method we tested the power of our method on a new set of protein sequences that were added to scop after we compiled our benchmark. our goal was to test if the method can classify new sequences to their correct class. the new set consists of proteins in release of scop that were not included in our scop-db dataset and either belong to new families within existing superfamilies, new superfamilies within known folds or completely new folds. for instance, the family b.. did not exist in the scop database. this family is part of the b. superfamily that in release contains the families b.. b.. b.. and a total of representatives in our reference set. in total we found sequences belonging to new families within known superfamilies, sequences associated to new superfamilies within known folds and sequences in new folds, all with less than 40% identity between pairs of sequences. each one of these new sequences was compared against all the sequences in scop-db using all of the methods evaluated in this paper, and the matches were sorted based on the score or distance, as before. to apply the distance-profile method the sequences were first processed and mapped to feature vectors as described in section'results'.  we study a new method for remote homology detection that utilizes global information on the proximity of entities in the protein space. our method relies on the distance-profile representation of proteins and protein families that maps each query protein to a high-dimensional feature space, where the coordinates are determined by some association measures with respect to a reference set. these vectors are then processed and transformed to sparse feature vectors that are treated as statistical fingerprints of the query proteins. we experimented with several different types of association measures and demonstrated how an adequate choice of distance metric combined with a proper transformation of the feature vectors through noise reduction, pvalue conversion and normalization can greatly increase the performance of homology recognition compared to the existing approaches. interestingly, excellent performance is obtained with normalized feature vectors that correspond to probability distributions. the success of the distance-profile method in general and especially when using probability distributions suggests a relation to mixture models. specifically, one can consider this representation as the coefficients of a mixture model or of a functional expansion, similar to the taylor polynomial expansion. given a set of basis functions such as polynomial functions one can span the complete space of continuous well-behaved functions with the right coefficients. the same principle applies here as our reference set essentially defines a set of basis functions. in statistical terms, each element of the reference set induces a different probability distribution over the protein sequence space. in our experiments the reference set is composed of protein structures, each one can be perceived as a different generative model. the likelihood of generating a sequence according to a model can be estimated by computing the probability that the sequence will fold into the corresponding structure, as measured with the pvalue association measure over the threading similarity score. although these probability distributions do not necessarily meet the requirement of orthogonality to be considered "basis functions", a sufficiently diverged set of proteins is expected to have the desired properties. it has yet to be defined more precisely what sufficiently diverged means and the minimal required diversity. one intriguing aspect that has not been fully addressed is the interaction between the association function, the distance metric and the zscore cutoff value. in some cases the coupling is not surprising. for example, when the prob association function is used, the l metric clearly underperforms compared to l and js metrics, as expected, since the vectors compared correspond to probability distributions. with the other association measures, l and l perform similarly. study of the theoretical aspect of this phenomenon will help understand how to take further advantage of these feature vectors to cluster the protein sequences more accurately. a word of caution is in order here regarding the evaluation. while scop is considered the gold standard, it is not perfect and often one can find mis-classifications. while it is hard to estimate the exact rate of errors, it is unlikely that they exceed thousands and we do not anticipate the results to change drastically even if these mis-classification were corrected. we should also mention that the dp representation is not effective for detailed, atom-resolution prediction of 3d structure or for site-specific functional annotation, since it cannot produce alignments. another weakness is that the distance-profile representation and the new pvalue-distance measure may fail to distinguish two proteins if they have almost identical "preferences" for the known structures but different preferences for other, unknown structures that are yet to be determined. however, given the current size of the protein structure space, it is expected that for most proteins the available structural information is sufficient to estimate their proximity. indeed, only 20% of the new scop sequences were assigned to new folds, clearly, as more structures are determined and integrated into the reference set, the distance-profile representation is expected to improve. one potential contribution of this work is the possibility of combining the transformations described in section'processing feature vectors' to the feature vectors used by existing kernel methods. these techniques can effectively reduce noise and increase the accuracy of classification of the feature space. in addition, since the feature vectors are typically sparse after noise reduction, an efficient computation of the kernel function can be implemented in a high-dimensional feature space. finally, a major advantage of the distance-profile representation is in its great flexibility. the underlying association measure can be based on sequence, structure, predicted function, threading, or any other similarity measure. clearly, more distinctive association measures will create better representations. indeed, the fugue zscore is clearly a better choice than the psiblast evalue since fugue exploits sequence-structure alignment information rather than just sequence alignment information. if the association measure can report a significance value that emphasizes extremes and pinpoint the interesting cases, the statistical measure will be preferred over the raw score. this is especially useful when the raw score is meaningless by itself. in these cases one needs a yardstick or a scale to tell what is close and what is far and the statistical estimates provide such a scale. nevertheless, it is important to note that the distance-profile representation and the induced similarity measure are quite robust and work well even with raw association scores, noisy or corrupted data, and weak signal-to-noise ratio. all our data, including the fugue results, the psiblast results and the feature vectors are available at. authors' contributions ck implemented the model, ran experiments, compared to other models, analyzed the result sets and wrote parts of the manuscript. gy conceived of the study, designed the model and the experiments, analyzed results and drafted the manuscript. appendix the sequence-structure association measure historically, sequence-structure threading was proposed as an alternative approach to predict the structural fold of polypeptide chains. in contrast to ab initio strategies that exploit secondary structure prediction, energy minimization and molecular dynamics to predict the structure of a protein sequence, sequence-structure threading consists of finding native-like folding structure for a query protein from a database of known structures. its motivation originates from the observation that proteins adopt a limited number of spatial architectures and that larger proteins are frequently composed of modules that can be found in other proteins. to perform sequence-structure threading of a query sequence, the process typically starts by obtaining a set of structural conformations from a database of known structures. the amino acid sequence of the query protein is aligned to each conformation in search of an alignment that would produce the minimal total energy. the most likely candidate conformations are the ones yielding the lowest energy. if the energy values are significantly low compared for example to those obtained for shuffled sequences, then these structural conformations can be considered as compatible with the query sequence. many different approaches and implementations of threading algorithms have been proposed in the past. the exact details of the alignment algorithm and the computation of the total energy vary from one method to another. unfortunately, most of them are not publicly available to allow an extensive comparison of sequences and structures. of the few that are available, we chose fugue for our study. fugue is a sequence-structure alignment algorithm that uses environment-specific substitution tables and structure-dependent gap penalties to evaluate the alignment score. it switches between local and global alignment based on the ratio between the length of the query sequence and that of the structural profile. previous experimental results have shown that fugue outperforms other methods in fold recognition such as psiblast, sam-psiblast, hmmer-psiblast, threader and genthreader. it is worth mentioning that fugue should be considered as a structure-based sequence alignment algorithm rather than a sequence-structure alignment algorithm per se, since it does not involve the definition and the minimization of any energy function to measure the goodness of fit of the query sequence to the template structure. however, its use of substitution tables and structure-dependent parameters provides additional information which is unavailable to pure sequence-based methods. in fugue, the compatibility of each sequence-structure pair is assessed through the zscore, which measures the departure of the observed threading score value from its mean, normalized by the standard deviation does not necessarily equal to s. actually, for most protein pairs the equality s = s does not hold, as different protein structures have different "sequence capacities". these capacities affect the ability of an arbitrary sequence to conform with the given structure, and therefore also the probability that the structure will be energetically favorable for the given sequence. however, the asymmetry may be a fundamental feature of the protein space that we may want to preserve and study later on in our analysis. the statistical significance of the pd measure we computed the distribution of pvalue-distances between pairs of feature vectors ppvalue of unrelated protein sequences. the distribution is a complex one, and features multiple modes. each mode corresponds to the occurrence of one additional term in the summation contributing to the final value of the pd measure as described in eq, i.e. the two feature vectors share one additional entry where the pvalues are both significant. one may characterize the pd measure as the sum of a random number of evd random variables. unfortunately, analysis of such a distribution is generally intractable and therefore we can only estimate the significance level of our pd measure based on the empirical distribution. in figure 6b, we plot the distribution of the pd measure over its full range in log scale. we observe that the frequency of occurrence of large pd values decreases exponentially, i.e. linearly in log scale. this phenomenon can be explained by examining again the definition of the pd measure given in. if we consider a zscore as a random variable, its associated pvalue is a random variable uniformly distributed between and based on the assumption that pi1 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgwbacdaqhaawcbagaemyaakgabagaegymaedaaaaa@308f@ and pi2 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgwbacdaqhaawcbagaemyaakgabagaegomaidaaaaa@3091@ are independent, max follows a triangular distribution and -log max is an exponential random variable. therefore, -log pd can be viewed as a sum of exponential random variables. from the statistical literature, we know that the sum of k independent and identically distributed exponential random variables with parameter α can be modeled by the gamma function. fg=xk−1e−x/ααkΓ      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacqwgmbgzdawgaawcbagaem4raceabeaakiabcicaoiabdiha4jabcuda7iabdugarjabcycasiabeg7ahjabcmcapiabg2da9maalaaabagaemieag3aawbaasqabeaacqwgrbwacqghsislcqaixaqmaagccqwglbqzdaahaawcbeqaaiabgkhitiabdiha4jabc+caviabeg7ahbaaaoqaaiabeg7ahnaacaaaleqabagaem4aasgaaogaeu4kdckaeiikagiaem4aasmaeiykakcaaiaaxmaacawljawaaewaaeaacqai1aqnaiaawicacaglpaaaaaa@4f41@ for large x, we have log⁡fg=ε−xα+log⁡x∝−xα      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqacigacagaaeqabaqabegadaaakeaacyggsbabcqggvbwbcqggnbwzcqwgmbgzdawgaawcbagaem4raceabeaakiabcicaoiabdiha4jabcuda7iabdugarjabcycasiabeg7ahjabcmcapiabg2da9iabew7aljabgkhitmaalaaabagaemieaghabagaeqysdegaaiabgucariabcicaoiabdugarjabgkhitiabigdaxiabcmcapigbcygasjabc+gavjabceganjabdiha4jabg2hi1kabgkhitmaalaaabagaemieaghabagaeqysdegaaiaaxmaacawljawaaewaaeaacqai2agnaiaawicacaglpaaaaaa@56fa@ where ε is an additive constant. hence, log fg approximately decreases with x in a linear fashion. in our case, clearly the summands in are not independent of each other since the reference set is composed of groups of related sequences. nonetheless, one may expect that the dependency is not too strong because these sequences share less than 40% sequence identity. the plot indeed suggests that the distribution of the pd measure follows this trend. examples of homology detection tables and list the closest neighbors of the protein queries d2tgf__ and d1hdoa_ with each one of the five competing methods. as these demonstrate, a significantly larger number of proteins that are biologically related to the query sequence are placed at the top of the neighbor list with the distance-profile method. for example, the protein domain g.. belongs to the superfamily g. which contains entries in the scop-db database. both psiblast and blast detect true positives before encountering the first false positive d.., whereas dp-psiblast extends the roc1-s index to fugue starts with tp at the top of the sorted list and our dp-fugue method further improves the index to tp. the differences for the protein domain c.. are even more substantial, with blast, psiblast and dp-psiblast reporting only two tp before the first fp, fugue reporting tp, while dp-fugue reporting tp, thus significantly enhancing the clustering of the members of the superfamily c.. we observe that the performance of the dp method depends on the configuration of the sorted list obtained using the initial association measure. our method works best when some true positives can be found among the top ones on the list, even if proceeded by or mixed with false positives; it refines the results by clustering even closer the similar elements while pushing further away the false positives. our method does not improve the results in the case of c... however, we note that this is a difficult case of homology detection since there are more than members in the superfamily c. while all methods detect only a very few true positives at the top of the sorted list. there are several cases where fugue lists a fp at the top of the list but a couple of tps are among the closest ones. in these cases, dp can enhance the mapping and improve over fugue, as is also demonstarted in figure however, when there is only one tp at the top of the list, our method does not always improve over fugue. this is most difficult when the top true positive match is only marginally higher than the first false positive. 
these vectors are then processed and transformed to sparse feature vectors that are treated as statistical fingerprints of the query proteins. detecting homology between remotely related protein families is an important problem in computational biology since the biological properties of uncharacterized proteins can often be inferred from those of homologous proteins. we describe an algorithm that improves over the state of the art in homology detection by utilizing global information on the proximity of entities in the protein space. our method relies on a vectorial representation of proteins and protein families and uses structure-specific association measures between proteins and template structures to form a high-dimensional feature vector for each query protein. however, these methods do not exploit collective aspects of the protein space and the computed scores are often noisy and frequently fail to recognize distantly related protein families.
 detecting homology between remotely related protein families is an important problem in computational biology since the biological properties of uncharacterized proteins can often be inferred from those of homologous proteins. many existing approaches address this problem by measuring the similarity between proteins through sequence or structural alignment. however, these methods do not exploit collective aspects of the protein space and the computed scores are often noisy and frequently fail to recognize distantly related protein families.  we describe an algorithm that improves over the state of the art in homology detection by utilizing global information on the proximity of entities in the protein space. our method relies on a vectorial representation of proteins and protein families and uses structure-specific association measures between proteins and template structures to form a high-dimensional feature vector for each query protein. these vectors are then processed and transformed to sparse feature vectors that are treated as statistical fingerprints of the query proteins. the new representation induces a new metric between proteins measured by the statistical difference between their corresponding probability distributions.  using several performance measures we show that the new tool considerably improves the performance in recognizing distant homologies compared to existing approaches such as psiblast and fugue. 