BACKGROUND
the statistical significance of a local alignment score between two sequences of amino-acid letters can be assessed by analyzing background distribution of the alignment scores between random sequences.
for smith-waterman alignments  <cit>  lacking gaps, it has been well established that the background score distribution is approximately gumbel  <cit> , specified by two analytically computable parameters λ and k  <cit> .
assessing score statistics for profile-based alignments is much more challenging problem.
in order to quickly estimate the significance of a database match, the hmmer method  pre-computes extreme value distribution parameters for each hidden markov model in the profile library.
these model dependent parameters are calculated by aligning and scoring a given hmm against thousands of real or random sequences.
psi-blast estimates score significance "on the fly", by reconstructing residue scores within each profile column to the same scale as the scores specified in the blosum <dig> matrix  <cit> .
the assumption is that, after rescaling, the background distribution of psi-blast scores will be the same as the distribution of the gapped blast scores.
many experiments suggest that this hypothesis is valid and that the rescaling technique yields accurate p-values.
the assessment of statistical significance of profile-profile scores is still an unsolved problem.
in lieu of a rigorous analytical theory, many profile-profile algorithms resort to z-score statistics  <cit> .
for sequence only methods, the z-value of an alignment score between two sequences is computed by comparing the first sequence with randomly shuffled versions of the second sequence.
an advantage of z-values is that they eliminate the sequence length and compositional bias, since the shuffling of a sequence preserves these two variables.
however, there are certain disadvantages to using raw z-scores to rank the significance of the alignment scores.
first, the z-score statistics makes a false assumption about the gaussian form of the underlying score distribution.
a reader interested in the magnitude of the error introduced by this assumption in referred to  <cit> .
second, z-scores do not provide the probability that an alignment score could be obtained by chance.
nevertheless, the z-values can be made very useful for computing accurate p-values via a "change of variable" technique  <cit> .
more specifically, it has been shown that if the raw alignment scores follow a standard gumbel law, then the p-values of associated z-scores are free of sequence length and amino acid composition biases  <cit> .
since the only drawback of this approach is the computational expense associated with random simulations, it would be very interesting to see whether the "change of variable" approach can be used in other settings.
recently, an interesting approach to alignment score normalization has been described that uses so-called shared amount of information  between the amino-acid <cit> .
the model proposed in  <cit>  is unique since it is derived from the reliability theory applied to sequences of amino-acids.
to date the studies on score normalization for local profile-profile alignments have been limited to some specific alignment scoring schemes.
for example, an explicit generalization of techniques implemented in psi-blast has been successfully used in the compass algorithm  <cit> .
however, the method described in sadreyev et al.
works only in the context of the compass scoring function.
the statistical significance of alignment scores produced by the lama method is estimated using an approach based on fisher's combining method  <cit> .
in hhsearch  <cit> , the profile specific parameters were computed by comparing each profile to the set of profiles built for the representative sequences in the scop database  <cit>  .
the alignment scores obtained by prof_sim  <cit> , structfast <cit> , and uni-fold  <cit>  were also shown to follow the extreme value distribution, but the distribution parameters in these methods must be pre-calculated using computationally expensive curve-fitting procedure.
this approach is commonly referred to as the "direct method".
in the "direct method", thousands of optimal alignment scores between real or random profiles are usually needed for moderately accurate estimates of the distribution parameters.
on the other hand, profile-profile methods are computationally very expensive, making the direct method too slow for parameter estimation, in particular for deriving the score statistics "on the fly" for each given pair of profiles.
here, we study a generalization of the well known island method  <cit>  to score normalization problem for profile-profile alignments.
the island method uses the scores of local alignment "islands" obtained by a simple modification of the dynamic programming matrix.
since multiple island scores can be computed from a single path graph, the island method has a distinct speed advantage over the direct method.
methods
the statistical theory
the statistical significance of an alignment score is usually expressed by the score's p-value.
the p-value of a score x is defined as the probability of obtaining a score of at least x purely by chance, given the probabilistic models for the sequences and the alignment scoring scheme.
for a pair of random sequences of lengths m and n, the expected number of locally optimal gapless sub-alignments with score of at least x is approximately poisson distributed with mean value e given by
the analytically computable parameters λ and k depend on the background probabilities of amino-acid letters and the residue-residue substitution scores specified in the mutation matrix.
the equation  <dig> implies that the p-value of a score x is
there is plenty of evidence suggesting that equation  <dig> still holds for alignments with gaps  <cit> , as well as for profile-sequence and profile-profile alignments <cit> .
however, for these methods, λ and k must be estimated from random simulations rather than computed analytically  <cit> .
we note that precise estimates of λ are particularly important since the p-value is a doubly exponential function of λ. we also note that, in contrast to local alignment scores, the scores of global sequence-sequence alignments are shown to approximately follow a three-parameter gamma distribution function <cit> .
for global alignment statistics, the computational complexity is still an open problem.
need for composition-based statistics for profile-profile alignments
for alignment methods that use substitution matrices and residue type information , it has been well established that λ and k depend, not only upon the alignment scoring system, but also upon the frequencies of amino-acid letters in the sequences being aligned.
in these methods, λ can vary more than 10% from one sequence pair to another, due entirely to change in sequence amino-acid composition  <cit> .
the variation in λ is much larger for profile-profile methods.
figure  <dig> shows the histogram of estimates of λ for  <dig> pairs of profiles selected at random from the set of profiles constructed for representative sequences in the fssp database  <cit> .
for each pair of profiles, λ is computed by repeatedly shuffling the columns  in both profiles and fitting statistical parameters to optimal local alignment scores between profiles' shuffles.
as seen in figure  <dig>  for some alignment methods, the difference in λ between pairs of profiles reaches an order of magnitude.
on the other hand, for marginally significant alignment scores between average length profiles, even a relatively small change in λ of 10% results in over  <dig> fold change in the estimated e-value .
this implies that e-values computed for profile-profile scores using any fixed λ are unreliable, establishing a need for computing the statistical parameters independently, for each given pair of profiles.
island statistics
to circumvent the computational expense associated with random simulations for sequence-sequence methods, olsen et al.
proposed using the scores of the so-called "alignment islands"  <cit> .
an alignment island is a region in the dynamic programming matrix corresponding to positively scoring segments in two sequences.
more precisely, an island is a collection of locally optimal alignments that start at the same cell  in the path graph  <cit> .
the score of an island is defined as the highest score among all local alignment scores for that island.
since the accuracy of equation  <dig> increases with increasing values of x, accurate estimates of λ and k can be obtained by considering islands i with sufficiently high peak scores σ .
assuming continuity of alignment scores, the maximum likelihood estimate of λ is
where rc denotes the set of islands i such that σ  ≥ c <cit> .
the standard error in  is , where λ denotes the asymptotic parameter .
the maximum likelihood estimate of k is
where m and n are the lengths of the random sequences used in each island comparison and b is the total number of sequence comparisons performed to generate the islands <cit> .
we note that the island method is similar to the "declumping" method of waterman and vingron <cit> , but is much faster, because, unlike clumps, the islands and their scores can be collected with a minor modification of the smith-waterman algorithm  <cit> .
several applications have recently been developed that incorporate island statistics for score normalization, including ctx-blast  <cit> , consequences <cit> , and cis  <cit> .
an added benefit of the island statistics  is flexibility in choosing the scoring system.
in order to be amenable to island statistics, the only requirement a method needs to satisfy is that that the alignments it generates stay in the local regime, i.e.
that the distribution of alignment scores between random sequences  is approximately gumbel.
therefore, since the procedure for computing statistical parameters does not change with changes to the scoring function, one can entirely focus on improvements to the scoring scheme.
this is important, because incorporating additional information into the alignment process, such as, for example, the compositionally adjusted background frequencies  <cit>  or protein secondary structure information  <cit>  is known to significantly increase sensitivity of an alignment method <cit> .
RESULTS
the island statistics for profile-profile alignments
the alignment score significance can be assessed using either real or random profiles  <cit> .
we use random profiles to avoid bias in the results toward any particular group of proteins.
a random profile of length n is obtained by sampling n profile columns at random from the collection of profiles computed for ~ <dig>  representative sequences from the fssp database .
the database of fssp profiles is generated by running three psi-blast iterations on each fssp sequence and parsing amino-acid letter frequencies from the corresponding psi-blast checkpoint files.
we study the applicability of the island statistics on four popular and well tested profile-profile scoring schemes: jensenshannon , crossproduct , weightedlogodds , and multinomial .
the definition of each scoring function is given in the appendix.
the column-column scores in all four methods are scaled  so that the alignment score distributions have similar parameters.
since the island statistics applies only to methods for which the background distribution of optimal alignment scores is approximately gumbel, we first verify that the algorithms in our study belong to this category.
figure  <dig> shows the score distributions of  optimal local alignments between the shuffles of random profiles.
as seen in figure  <dig>  for all four profile-profile methods in our study, the best-fit extreme value distribution closely follows the data, with χ <dig> goodness-of-fit p-values ranging from  <dig>  to  <dig> .
to establish a link between the statistics of peak island scores and optimal alignment scores, we compare, for a range of cutoff values c, the observed number of islands with scores ≥ c with the expected number of such islands computed from the best-fit extreme-value distribution.
the expected number of islands is defined as , where  and  are parameters obtained with the direct method.
more specifically,  and  are the maximum likelihood estimates of parameters in equation  <dig>  obtained from the scores of  optimal local alignments between profile shuffles.
for more on the maximum likelihood estimates of statistical parameters, the reader is referred to  <cit> .
as seen in figure  <dig>  there is strong agreement in the expected and observed counts of the island peak scores beyond the small score regime, independent of the scoring system employed and the lengths of the profiles.
an analysis of real  profiles demonstrates an equally strong correlation between two statistics for high scoring islands.
the two statistics obviously differ for low scoring islands .
as argued before  <cit>  the low scoring islands often correspond to ungapped alignments of only few profile positions, and therefore, the scores of those islands follow a different distribution, namely the distribution of gapless alignment scores.
the plots in figure  <dig> show faster decay in the number of islands with score ≥ c for profiles of size  <dig> compared to profiles of size  <dig> ×  <dig>  we note that the apparent λ for each comparison in figure  <dig> is equal to -k, where k denotes the slope of the set of data points.
for sequence only alignments, this dependence of the apparent λ on sequence length is due to the "edge effect", which arises because the length of the longest island, and hence its associated score, is limited by the lengths of the sequences  <cit> .
thus, if the variance in slopes for profile-profile methods seen in figure  <dig> is also due to the edge effect, one would expect to observe larger difference in slopes for methods that generate longer alignments.
indeed, our analysis of alignments generated by four methods in our study demonstrates that the variance in λ for small and large comparisons seen in figure  <dig> scales proportionally with average alignment length generated by each method .
the "edge effect" may be corrected for by allowing the islands to extend beyond the ends of the sequences  <cit> .
for sequence only methods, this is done by embedding each n × n comparison within a lager comparison with a border of length b and then collecting only the islands anchored within the central n × n region  <cit> .
we tested a similar technique for computing profile-pair specific asymptotic parameters from small size comparisons.
we note that our procedure is slightly different from the procedure described in  <cit>  because it treats the boundary and the central region separately.
more specifically, to account for compositional bias in the profiles, only the scores in the central n × n square are shuffled and the boundary is filled in with scores chosen at random from the central region.
figure  <dig> shows the asymptotic distribution of island scores obtained from a comparison of size  <dig> ×  <dig> surrounded by a border of size  <dig>
to assess the accuracy of the island method, we  compute, for each island score cutoff c, the estimates of λ and k using equations  <dig> and  <dig>  table  <dig> gives the island estimates of λ and k for a single pair of random profiles of lengths  <dig>  using the weightedlogodds scoring function.
similar results were obtained with the other three scoring functions .
the estimates of λ and k and the standard error  in  for a pair of random profiles obtained with the island method  from  <dig>  comparisons of size  <dig> ×  <dig> using the weightedlogodds scoring scheme.
the parameters estimated with the direct method are  =  <dig> ,  =  <dig> .
to better illustrate the dependence of the island estimate of λ on the cutoff value c, we plot the values  from table  <dig> in figure  <dig>  as seen in figure  <dig>  the value of  decreases with increasing island cutoff score c, until it reaches the value of  <dig>   at c =  <dig> and then randomly oscillates around this point.
speed vs. accuracy
there are two types of errors that can occur when computing the statistical parameters using random simulations.
the first error, called "bias", represents the difference between the estimated and "true" statistical parameters.
the second error is the standard error, which, unlike the bias, can be controlled by the number of data points used in parameter estimation.
more specifically, the standard error in  is 1/ for the island method and  <dig> / for the direct method  <cit> , where r denotes the number of data points, i.e.
the number of island scores above the cutoff and the number of optimal alignment scores, respectively.
both direct and island method suffer from bias in the estimates of the statistical parameters.
as seen in figure  <dig>  the bias of the island method is closely related to the island cutoff score.
similarly, the direct method tends to overestimate λ due to the nonexistence of an optimal alignment score threshold.
the maximum likelihood estimates of distribution parameters obtained with the direct method most strongly depend on the low scoring data points, because of the steep decrease of the left tail of the extreme value distribution.
therefore, the extent of bias for the direct method is proportional to the fraction of low scoring optimal alignments used for parameter estimation.
we note that the biases of the direct and island method can be computed  for local alignments of single sequences, due to availability of experimentally verified "best estimate" of the asymptotic λ  <cit> .
using the "best estimate" of λ as the reference point, altschul and co-workers were able to find a threshold island score that eliminates all cutoff-based bias for large size comparisons of random sequences.
by considering only the islands with peak scores over the threshold, they computed accurate, sequence length specific parameter estimates of λ, and used these estimates as gold standards to assess the extent of bias for both methods  <cit> .
unfortunately, it would be difficult to perform a similar experiment in our setting because of the dependence of statistical parameters on profiles' composition and because of the computational complexity of profile-profile methods.
thus, instead of comparing the bias side-by-side, we focus our attention on measuring the difference between the island and direct method estimates of λ and on comparing the computational efficiencies of two methods.
the speed advantage of the island method is due to its ability to generate multiple data points in a single comparison of two shuffled profiles.
however, the average number of islands per pair of shuffled profiles does not directly translate into the speed advantage of the island method.
first, for the same standard error in , the island method needs to generate 64% more data points than the direct method.
second, a single comparison of two profiles with the island method is computationally more expensive than the same comparison with the direct method, since the island method needs to keep track of the islands and their peak scores.
our implementation of the dynamic programming engine for the island method is ~ <dig>  times slower than the procedure that only returns an optimal alignment score.
taking those two factors into consideration, the total speed advantage of the island method is about ac/ <dig> , where ac denotes the average number of island with peak scores ≥ c collected in a single comparison of two shuffled profiles.
we note that our results are identical to previously reported results for sequence-sequence alignments  <cit> .
we emphasize that the speed advantage of island method also depends on the scoring scheme used in a profile-profile method.
figure  <dig> shows the relationship between the speed-advantage of the island method and the discrepancy in estimates of λ obtained with two methods.
as seen in figure  <dig>  for the same speed-up, the difference in the estimates of λ obtained by two methods is smaller for large size comparisons.
this is expected, because, for two equal size collections of top scoring islands, the average island score for a large size comparison exceeds the average island score for small size comparison, resulting in overall more accurate parameter estimates.
to compute the actual running times of two methods, we tested both programs on an intel xeon  <dig>  ghz cpu computer with  <dig> gb of ram.
table  <dig> gives the relationship between the running time of the island method and percent deviation of the island estimates of λ from the estimates obtained with the direct method .
as seen in table  <dig>  for a typical comparison of size  <dig> ×  <dig>  the island method using the jensenshannon scoring function needs about  <dig> seconds to obtain an estimate of λ within 4% of the direct method estimate .
to achieve the same standard error in , the direct method requires ~ <dig>  minutes, corresponding to a 20-fold speed advantage of the island method.
when compared to the direct method, the efficiency of the island method further increases with increasing lengths of the profiles.
for instance, for the same 4% difference in the estimates of λ and comparisons of size  <dig> ×  <dig>  the island method is  <dig> times faster than the direct method .
for 2% difference in λ, the island method is  <dig> times faster for comparisons of size  <dig> ×  <dig> and  <dig> times faster for comparisons of size  <dig> ×  <dig>  we note that increased computational efficiency on large profiles makes the island method particularly useful, since using the direct method to compute the parameters "on the fly" for large size comparisons would be computationally prohibitive.
the actual running time of the island method and the  difference in the island estimates of λ from the values obtained with the direct method.
the results are averaged over  <dig> pairs of random profiles.
the standard error in each estimate of λ for both methods is  <dig> %.
the running time of the direct method is ~ <dig>  minutes for comparisons of size  <dig> ×  <dig> and ~ <dig> minutes for comparisons of size  <dig> ×  <dig>
we emphasize that, by using the direct method estimates as reference points, we do not argue that these estimates are more accurate than the estimates obtained with the island method.
in fact, the results of a similar analysis for sequence-only methods  <cit>  suggest that, for comparisons of size ~ <dig> ×  <dig>  the bias of the direct method would be about three times larger than the bias of the island method, for the same standard error in .
previous studies of the island statistics for sequence-sequence alignments addressed the speed-accuracy tradeoff by optimizing the island score cutoff c. for the blosum <dig> matrix and gap opening and extension penalties of  <dig> and  <dig>  respectively, the cutoff value of c =  <dig> was found appropriate  <cit> .
olsen and co-workers suggested the cutoff value of c =  <dig> ·max{sab}, where sab is the score for matching amino acid letters a and b, specified in the substitution matrix  <cit> .
a slightly different interpretation of the results in table  <dig> suggests an alternative approach to controlling speed and accuracy tradeoff for an arbitrary profile-profile scoring scheme and a range of profile lengths.
for example, for a pair of profiles of lengths  <dig>  the jensenshannon scoring scheme, and the standard error of  <dig> %, the island estimate of λ that is within 4% of the direct method estimate of λ can be obtained by running the island method for ~ <dig> seconds and computing λ using the top scoring  <dig>  islands .
we used our in-house computer cluster to directly compare the performance of the island and the direct method in identifying the relationships between the sequences in the lindahl test set  <cit> .
the lindahl test set is composed of  <dig> pairs of proteins classified in three groups according to scop <cit>  hierarchy.
the accuracy of an alignment method in the lindahl benchmark is defined as its ability to place a correct member of the scop group  on the top of its ranked list.
the results of our test, presented in table  <dig>  show no significant difference in fold recognition sensitivity between the two methods.
the performance of the island method in the lindahl benchmark for fold recognition.
we show the difference in the percentage of the relationships identified by the island and the direct method  in the first and the top five ranks, at each scop level .
in this analysis we used the multinomial scoring system.
similar results were obtained with the other three scoring schemes .
CONCLUSIONS
by utilizing the information present in protein families, profile-profile alignment algorithms are often able to detect extremely week relationships between protein sequences, as evidenced by the large scale benchmarking experiments such as casp  <cit> , cafasp  <cit> , and livebench  <cit> .
however, estimating the score statistics for profile-profile alignments is a challenging problem.
the background distribution of profile-profile alignment scores is constrained by profiles' composition and hence the distribution parameters must be estimated independently, for each given pair of profiles.
we study the applicability of the well known "island method" to profile-profile score normalization.
in the island method, the statistical parameters are computed based upon the top scoring islands that can be collected using a simple modification of the smith-waterman algorithm.
since multiple high scoring islands can be extracted from a single path graph, the island method has a distinct speed advantage over the direct method.
for some widely used profile-profile scoring schemes, the speed advantage of the island method exceeds an order of magnitude for comparable accuracy in parameter estimates.
for larger profiles, a significant speed advantage of the island statistics comes with almost perfect accuracy.
this is important, since using the direct method as the only other alternative to compute the parameters "on the fly" for large size comparisons is computationally prohibitive.
appendix
the jensenshannon score  <cit>  between probability distributions q <dig> and q <dig> is defined as
where j = djs  is the jenson-shannon divergence between q <dig> and q <dig> and s = djs  is the jenson-shannon divergence between the "most likely common source distribution" r for q <dig> and q <dig> and the "overall" distribution of  <dig> amino acid letters b. the distribution r is defined as
the jenson-shannon divergence is given by
where dkl is the kullback-leibler divergence
the crossproduct scoring function  <cit>  multiplies the products of the amino-acid target frequencies by the corresponding elements sab of the blosum <dig> substitution matrix
the weightedlogodds  <cit>  and the multinomial  <cit>  scoring functions use the effective amino-acid counts when scoring a pair of profile positions.
more specifically, the score for matching q <dig> and q <dig> is given as
where  and  are the "effective counts" for the amino acid k observed at two profiles' columns and bk is the background probability of k. in the weightedlogodds function, the parameters c <dig> and c <dig> are set to
in the multinomial scoring function, both c <dig> and c <dig> are set to  <dig>

 the statistical significance of a local alignment score between two sequences of amino-acid letters can be assessed by analyzing background distribution of the alignment scores between random sequences. for smith-waterman alignments lacking gaps, it has been well established that the background score distribution is approximately gumbel, specified by two analytically computable parameters λ and k. assessing score statistics for profile-based alignments is much more challenging problem. in order to quickly estimate the significance of a database match, the hmmer method pre-computes extreme value distribution parameters for each hidden markov model in the profile library. these model dependent parameters are calculated by aligning and scoring a given hmm against thousands of real or random sequences. psi-blast estimates score significance "on the fly", by reconstructing residue scores within each profile column to the same scale as the scores specified in the blosum matrix. the assumption is that, after rescaling, the background distribution of psi-blast scores will be the same as the distribution of the gapped blast scores. many experiments suggest that this hypothesis is valid and that the rescaling technique yields accurate p-values. the assessment of statistical significance of profile-profile scores is still an unsolved problem. in lieu of a rigorous analytical theory, many profile-profile algorithms resort to z-score statistics. for sequence only methods, the z-value of an alignment score between two sequences is computed by comparing the first sequence with randomly shuffled versions of the second sequence. an advantage of z-values is that they eliminate the sequence length and compositional bias, since the shuffling of a sequence preserves these two variables. however, there are certain disadvantages to using raw z-scores to rank the significance of the alignment scores. first, the z-score statistics makes a false assumption about the gaussian form of the underlying score distribution. a reader interested in the magnitude of the error introduced by this assumption in referred to. second, z-scores do not provide the probability that an alignment score could be obtained by chance. nevertheless, the z-values can be made very useful for computing accurate p-values via a "change of variable" technique. more specifically, it has been shown that if the raw alignment scores follow a standard gumbel law, then the p-values of associated z-scores are free of sequence length and amino acid composition biases. since the only drawback of this approach is the computational expense associated with random simulations, it would be very interesting to see whether the "change of variable" approach can be used in other settings. recently, an interesting approach to alignment score normalization has been described that uses so-called shared amount of information between the amino-acid. the model proposed in is unique since it is derived from the reliability theory applied to sequences of amino-acids. to date the studies on score normalization for local profile-profile alignments have been limited to some specific alignment scoring schemes. for example, an explicit generalization of techniques implemented in psi-blast has been successfully used in the compass algorithm. however, the method described in sadreyev et al. works only in the context of the compass scoring function. the statistical significance of alignment scores produced by the lama method is estimated using an approach based on fisher's combining method. in hhsearch, the profile specific parameters were computed by comparing each profile to the set of profiles built for the representative sequences in the scop database. the alignment scores obtained by prof_sim, structfast, and uni-fold were also shown to follow the extreme value distribution, but the distribution parameters in these methods must be pre-calculated using computationally expensive curve-fitting procedure. this approach is commonly referred to as the "direct method". in the "direct method", thousands of optimal alignment scores between real or random profiles are usually needed for moderately accurate estimates of the distribution parameters. on the other hand, profile-profile methods are computationally very expensive, making the direct method too slow for parameter estimation, in particular for deriving the score statistics "on the fly" for each given pair of profiles. here, we study a generalization of the well known island method to score normalization problem for profile-profile alignments. the island method uses the scores of local alignment "islands" obtained by a simple modification of the dynamic programming matrix. since multiple island scores can be computed from a single path graph, the island method has a distinct speed advantage over the direct method. methods the statistical theory the statistical significance of an alignment score is usually expressed by the score's p-value. the p-value of a score x is defined as the probability of obtaining a score of at least x purely by chance, given the probabilistic models for the sequences and the alignment scoring scheme. for a pair of random sequences of lengths m and n, the expected number of locally optimal gapless sub-alignments with score of at least x is approximately poisson distributed with mean value e given by the analytically computable parameters λ and k depend on the background probabilities of amino-acid letters and the residue-residue substitution scores specified in the mutation matrix. the equation implies that the p-value of a score x is there is plenty of evidence suggesting that equation still holds for alignments with gaps, as well as for profile-sequence and profile-profile alignments. however, for these methods, λ and k must be estimated from random simulations rather than computed analytically. we note that precise estimates of λ are particularly important since the p-value is a doubly exponential function of λ. we also note that, in contrast to local alignment scores, the scores of global sequence-sequence alignments are shown to approximately follow a three-parameter gamma distribution function. for global alignment statistics, the computational complexity is still an open problem. need for composition-based statistics for profile-profile alignments for alignment methods that use substitution matrices and residue type information, it has been well established that λ and k depend, not only upon the alignment scoring system, but also upon the frequencies of amino-acid letters in the sequences being aligned. in these methods, λ can vary more than 10% from one sequence pair to another, due entirely to change in sequence amino-acid composition. the variation in λ is much larger for profile-profile methods. figure shows the histogram of estimates of λ for pairs of profiles selected at random from the set of profiles constructed for representative sequences in the fssp database. for each pair of profiles, λ is computed by repeatedly shuffling the columns in both profiles and fitting statistical parameters to optimal local alignment scores between profiles' shuffles. as seen in figure for some alignment methods, the difference in λ between pairs of profiles reaches an order of magnitude. on the other hand, for marginally significant alignment scores between average length profiles, even a relatively small change in λ of 10% results in over fold change in the estimated e-value. this implies that e-values computed for profile-profile scores using any fixed λ are unreliable, establishing a need for computing the statistical parameters independently, for each given pair of profiles. island statistics to circumvent the computational expense associated with random simulations for sequence-sequence methods, olsen et al. proposed using the scores of the so-called "alignment islands". an alignment island is a region in the dynamic programming matrix corresponding to positively scoring segments in two sequences. more precisely, an island is a collection of locally optimal alignments that start at the same cell in the path graph. the score of an island is defined as the highest score among all local alignment scores for that island. since the accuracy of equation increases with increasing values of x, accurate estimates of λ and k can be obtained by considering islands i with sufficiently high peak scores σ. assuming continuity of alignment scores, the maximum likelihood estimate of λ is where rc denotes the set of islands i such that σ ≥ c. the standard error in is, where λ denotes the asymptotic parameter. the maximum likelihood estimate of k is where m and n are the lengths of the random sequences used in each island comparison and b is the total number of sequence comparisons performed to generate the islands. we note that the island method is similar to the "declumping" method of waterman and vingron, but is much faster, because, unlike clumps, the islands and their scores can be collected with a minor modification of the smith-waterman algorithm. several applications have recently been developed that incorporate island statistics for score normalization, including ctx-blast, consequences, and cis. an added benefit of the island statistics is flexibility in choosing the scoring system. in order to be amenable to island statistics, the only requirement a method needs to satisfy is that that the alignments it generates stay in the local regime, i.e. that the distribution of alignment scores between random sequences is approximately gumbel. therefore, since the procedure for computing statistical parameters does not change with changes to the scoring function, one can entirely focus on improvements to the scoring scheme. this is important, because incorporating additional information into the alignment process, such as, for example, the compositionally adjusted background frequencies or protein secondary structure information is known to significantly increase sensitivity of an alignment method.  the island statistics for profile-profile alignments the alignment score significance can be assessed using either real or random profiles. we use random profiles to avoid bias in the results toward any particular group of proteins. a random profile of length n is obtained by sampling n profile columns at random from the collection of profiles computed for ~ representative sequences from the fssp database. the database of fssp profiles is generated by running three psi-blast iterations on each fssp sequence and parsing amino-acid letter frequencies from the corresponding psi-blast checkpoint files. we study the applicability of the island statistics on four popular and well tested profile-profile scoring schemes: jensenshannon, crossproduct, weightedlogodds, and multinomial. the definition of each scoring function is given in the appendix. the column-column scores in all four methods are scaled so that the alignment score distributions have similar parameters. since the island statistics applies only to methods for which the background distribution of optimal alignment scores is approximately gumbel, we first verify that the algorithms in our study belong to this category. figure shows the score distributions of optimal local alignments between the shuffles of random profiles. as seen in figure for all four profile-profile methods in our study, the best-fit extreme value distribution closely follows the data, with χ goodness-of-fit p-values ranging from to. to establish a link between the statistics of peak island scores and optimal alignment scores, we compare, for a range of cutoff values c, the observed number of islands with scores ≥ c with the expected number of such islands computed from the best-fit extreme-value distribution. the expected number of islands is defined as, where and are parameters obtained with the direct method. more specifically, and are the maximum likelihood estimates of parameters in equation obtained from the scores of optimal local alignments between profile shuffles. for more on the maximum likelihood estimates of statistical parameters, the reader is referred to. as seen in figure there is strong agreement in the expected and observed counts of the island peak scores beyond the small score regime, independent of the scoring system employed and the lengths of the profiles. an analysis of real profiles demonstrates an equally strong correlation between two statistics for high scoring islands. the two statistics obviously differ for low scoring islands. as argued before the low scoring islands often correspond to ungapped alignments of only few profile positions, and therefore, the scores of those islands follow a different distribution, namely the distribution of gapless alignment scores. the plots in figure show faster decay in the number of islands with score ≥ c for profiles of size compared to profiles of size × we note that the apparent λ for each comparison in figure is equal to -k, where k denotes the slope of the set of data points. for sequence only alignments, this dependence of the apparent λ on sequence length is due to the "edge effect", which arises because the length of the longest island, and hence its associated score, is limited by the lengths of the sequences. thus, if the variance in slopes for profile-profile methods seen in figure is also due to the edge effect, one would expect to observe larger difference in slopes for methods that generate longer alignments. indeed, our analysis of alignments generated by four methods in our study demonstrates that the variance in λ for small and large comparisons seen in figure scales proportionally with average alignment length generated by each method. the "edge effect" may be corrected for by allowing the islands to extend beyond the ends of the sequences. for sequence only methods, this is done by embedding each n × n comparison within a lager comparison with a border of length b and then collecting only the islands anchored within the central n × n region. we tested a similar technique for computing profile-pair specific asymptotic parameters from small size comparisons. we note that our procedure is slightly different from the procedure described in because it treats the boundary and the central region separately. more specifically, to account for compositional bias in the profiles, only the scores in the central n × n square are shuffled and the boundary is filled in with scores chosen at random from the central region. figure shows the asymptotic distribution of island scores obtained from a comparison of size × surrounded by a border of size to assess the accuracy of the island method, we compute, for each island score cutoff c, the estimates of λ and k using equations and table gives the island estimates of λ and k for a single pair of random profiles of lengths using the weightedlogodds scoring function. similar results were obtained with the other three scoring functions. the estimates of λ and k and the standard error in for a pair of random profiles obtained with the island method from comparisons of size × using the weightedlogodds scoring scheme. the parameters estimated with the direct method are =, =. to better illustrate the dependence of the island estimate of λ on the cutoff value c, we plot the values from table in figure as seen in figure the value of decreases with increasing island cutoff score c, until it reaches the value of at c = and then randomly oscillates around this point. speed vs. accuracy there are two types of errors that can occur when computing the statistical parameters using random simulations. the first error, called "bias", represents the difference between the estimated and "true" statistical parameters. the second error is the standard error, which, unlike the bias, can be controlled by the number of data points used in parameter estimation. more specifically, the standard error in is 1/ for the island method and / for the direct method, where r denotes the number of data points, i.e. the number of island scores above the cutoff and the number of optimal alignment scores, respectively. both direct and island method suffer from bias in the estimates of the statistical parameters. as seen in figure the bias of the island method is closely related to the island cutoff score. similarly, the direct method tends to overestimate λ due to the nonexistence of an optimal alignment score threshold. the maximum likelihood estimates of distribution parameters obtained with the direct method most strongly depend on the low scoring data points, because of the steep decrease of the left tail of the extreme value distribution. therefore, the extent of bias for the direct method is proportional to the fraction of low scoring optimal alignments used for parameter estimation. we note that the biases of the direct and island method can be computed for local alignments of single sequences, due to availability of experimentally verified "best estimate" of the asymptotic λ. using the "best estimate" of λ as the reference point, altschul and co-workers were able to find a threshold island score that eliminates all cutoff-based bias for large size comparisons of random sequences. by considering only the islands with peak scores over the threshold, they computed accurate, sequence length specific parameter estimates of λ, and used these estimates as gold standards to assess the extent of bias for both methods. unfortunately, it would be difficult to perform a similar experiment in our setting because of the dependence of statistical parameters on profiles' composition and because of the computational complexity of profile-profile methods. thus, instead of comparing the bias side-by-side, we focus our attention on measuring the difference between the island and direct method estimates of λ and on comparing the computational efficiencies of two methods. the speed advantage of the island method is due to its ability to generate multiple data points in a single comparison of two shuffled profiles. however, the average number of islands per pair of shuffled profiles does not directly translate into the speed advantage of the island method. first, for the same standard error in, the island method needs to generate 64% more data points than the direct method. second, a single comparison of two profiles with the island method is computationally more expensive than the same comparison with the direct method, since the island method needs to keep track of the islands and their peak scores. our implementation of the dynamic programming engine for the island method is ~ times slower than the procedure that only returns an optimal alignment score. taking those two factors into consideration, the total speed advantage of the island method is about ac/, where ac denotes the average number of island with peak scores ≥ c collected in a single comparison of two shuffled profiles. we note that our results are identical to previously reported results for sequence-sequence alignments. we emphasize that the speed advantage of island method also depends on the scoring scheme used in a profile-profile method. figure shows the relationship between the speed-advantage of the island method and the discrepancy in estimates of λ obtained with two methods. as seen in figure for the same speed-up, the difference in the estimates of λ obtained by two methods is smaller for large size comparisons. this is expected, because, for two equal size collections of top scoring islands, the average island score for a large size comparison exceeds the average island score for small size comparison, resulting in overall more accurate parameter estimates. to compute the actual running times of two methods, we tested both programs on an intel xeon ghz cpu computer with gb of ram. table gives the relationship between the running time of the island method and percent deviation of the island estimates of λ from the estimates obtained with the direct method. as seen in table for a typical comparison of size × the island method using the jensenshannon scoring function needs about seconds to obtain an estimate of λ within 4% of the direct method estimate. to achieve the same standard error in, the direct method requires ~ minutes, corresponding to a 20-fold speed advantage of the island method. when compared to the direct method, the efficiency of the island method further increases with increasing lengths of the profiles. for instance, for the same 4% difference in the estimates of λ and comparisons of size × the island method is times faster than the direct method. for 2% difference in λ, the island method is times faster for comparisons of size × and times faster for comparisons of size × we note that increased computational efficiency on large profiles makes the island method particularly useful, since using the direct method to compute the parameters "on the fly" for large size comparisons would be computationally prohibitive. the actual running time of the island method and the difference in the island estimates of λ from the values obtained with the direct method. the results are averaged over pairs of random profiles. the standard error in each estimate of λ for both methods is %. the running time of the direct method is ~ minutes for comparisons of size × and ~ minutes for comparisons of size × we emphasize that, by using the direct method estimates as reference points, we do not argue that these estimates are more accurate than the estimates obtained with the island method. in fact, the results of a similar analysis for sequence-only methods suggest that, for comparisons of size ~ × the bias of the direct method would be about three times larger than the bias of the island method, for the same standard error in. previous studies of the island statistics for sequence-sequence alignments addressed the speed-accuracy tradeoff by optimizing the island score cutoff c. for the blosum matrix and gap opening and extension penalties of and respectively, the cutoff value of c = was found appropriate. olsen and co-workers suggested the cutoff value of c = ·max{sab}, where sab is the score for matching amino acid letters a and b, specified in the substitution matrix. a slightly different interpretation of the results in table suggests an alternative approach to controlling speed and accuracy tradeoff for an arbitrary profile-profile scoring scheme and a range of profile lengths. for example, for a pair of profiles of lengths the jensenshannon scoring scheme, and the standard error of %, the island estimate of λ that is within 4% of the direct method estimate of λ can be obtained by running the island method for ~ seconds and computing λ using the top scoring islands. we used our in-house computer cluster to directly compare the performance of the island and the direct method in identifying the relationships between the sequences in the lindahl test set. the lindahl test set is composed of pairs of proteins classified in three groups according to scop hierarchy. the accuracy of an alignment method in the lindahl benchmark is defined as its ability to place a correct member of the scop group on the top of its ranked list. the results of our test, presented in table show no significant difference in fold recognition sensitivity between the two methods. the performance of the island method in the lindahl benchmark for fold recognition. we show the difference in the percentage of the relationships identified by the island and the direct method in the first and the top five ranks, at each scop level. in this analysis we used the multinomial scoring system. similar results were obtained with the other three scoring schemes.  by utilizing the information present in protein families, profile-profile alignment algorithms are often able to detect extremely week relationships between protein sequences, as evidenced by the large scale benchmarking experiments such as casp, cafasp, and livebench. however, estimating the score statistics for profile-profile alignments is a challenging problem. the background distribution of profile-profile alignment scores is constrained by profiles' composition and hence the distribution parameters must be estimated independently, for each given pair of profiles. we study the applicability of the well known "island method" to profile-profile score normalization. in the island method, the statistical parameters are computed based upon the top scoring islands that can be collected using a simple modification of the smith-waterman algorithm. since multiple high scoring islands can be extracted from a single path graph, the island method has a distinct speed advantage over the direct method. for some widely used profile-profile scoring schemes, the speed advantage of the island method exceeds an order of magnitude for comparable accuracy in parameter estimates. for larger profiles, a significant speed advantage of the island statistics comes with almost perfect accuracy. this is important, since using the direct method as the only other alternative to compute the parameters "on the fly" for large size comparisons is computationally prohibitive. appendix the jensenshannon score between probability distributions q and q is defined as where j = djs is the jenson-shannon divergence between q and q and s = djs is the jenson-shannon divergence between the "most likely common source distribution" r for q and q and the "overall" distribution of amino acid letters b. the distribution r is defined as the jenson-shannon divergence is given by where dkl is the kullback-leibler divergence the crossproduct scoring function multiplies the products of the amino-acid target frequencies by the corresponding elements sab of the blosum substitution matrix the weightedlogodds and the multinomial scoring functions use the effective amino-acid counts when scoring a pair of profile positions. more specifically, the score for matching q and q is given as where and are the "effective counts" for the amino acid k observed at two profiles' columns and bk is the background probability of k. in the weightedlogodds function, the parameters c and c are set to in the multinomial scoring function, both c and c are set to 
we also show that accurate estimates of statistical parameters can be obtained using the "island statistics" for profile-profile alignments. the island statistics can be generalized to profile-profile alignments to provide an efficient method for the alignment score normalization. since multiple island scores can be extracted from a single comparison of two profiles, the island method has a clear speed advantage over the direct shuffling method for comparable accuracy in parameter estimates. however, estimating distribution parameters by random simulations turns out to be computationally very expensive. many experiments suggest that the distribution of local profile-profile alignment scores is of the gumbel form. we demonstrate that the background distribution of profile-profile alignment scores heavily depends on profiles' composition and thus the distribution parameters must be estimated independently, for each pair of profiles of interest. in the last decade, a significant improvement in detecting remote similarity between protein sequences has been made by utilizing alignment profiles in place of amino-acid strings.
 in the last decade, a significant improvement in detecting remote similarity between protein sequences has been made by utilizing alignment profiles in place of amino-acid strings. unfortunately, no analytical theory is available for estimating the significance of a gapped alignment of two profiles. many experiments suggest that the distribution of local profile-profile alignment scores is of the gumbel form. however, estimating distribution parameters by random simulations turns out to be computationally very expensive.  we demonstrate that the background distribution of profile-profile alignment scores heavily depends on profiles' composition and thus the distribution parameters must be estimated independently, for each pair of profiles of interest. we also show that accurate estimates of statistical parameters can be obtained using the "island statistics" for profile-profile alignments.  the island statistics can be generalized to profile-profile alignments to provide an efficient method for the alignment score normalization. since multiple island scores can be extracted from a single comparison of two profiles, the island method has a clear speed advantage over the direct shuffling method for comparable accuracy in parameter estimates. 