BACKGROUND
knowledge of positions that coevolve in biological sequences can be applied to predict structures of rnas  <cit>  and proteins  <cit> ; to predict intermolecular interactions  <cit> ; to identify functionally important regions of molecules  <cit> ; and to identify energetic pathways through molecules  <cit> .
coevolutionary analyses have frequently been performed on one or a few protein families.
however, just as the adaptive evolution database  <cit>  allows proteome-wide studies of evolutionary rates, proteome-wide studies of coevolution could also be could performed if sufficiently fast and well-characterized methods for detecting coevolution were available.
as biological sequences are the product of an evolutionary process, it intuitively makes sense that the accuracy of analyses of the historical processes affecting them will be improved by explicit representation of those historical processes.
incorporation of phylogenetic information has benefited diverse classes of bioinformatics algorithms, including multiple sequence alignment  <cit> , comparison of microbial communities  <cit> , and functional annotation of genes  <cit> .
accordingly, incorporation of phylogenetic knowledge to control for patterns in biological sequence data that arise from ancestry is regarded as essential for coevolutionary analyses and best achieved by directly incorporating the phylogeny in the metric  <cit> .
many coevolution algorithms  have explicitly attempted to control for phylogeny , while others  have implicitly assumed a star phylogeny .
drawbacks have been identified for both approaches.
likelihood based tree-aware methods have the disadvantage of being sensitive to model mis-specification, a property common to all likelihood methods, and generally have a much longer compute time than tree-ignorant methods.
tree-ignorant methods are thought to have decreased specificity due to confounding of correlations arising from selective pressure with correlations arising from shared ancestry represented by the phylogeny  <cit> .
past evaluations of the effect of tree topology on the performance of coevolution algorithms have used simulated data, and have confirmed that non-star tree topologies can cause false positives  <cit> .
clearly, controlling for shared ancestry is essential but approaches that do so without explicitly representing the phylogenetic tree are possible.
we hypothesized a tree-ignorant statistic can be informative if it is compared to a distribution of the same statistic with the same embedded ancestry but variable in coevolution.
in this case, the shared ancestry origin of correlated evolution dominates the background distribution.
a greater magnitude of correlated evolution than this background is thus evidence of coevolution.
an additional consideration for estimating coevolution is that encoding protein alignments with reduced-state amino acid alphabets reduces computational complexity, and may also increase statistical power  <cit> .
in a reduced-state alphabet, the twenty amino acids are collapsed to a smaller number of states.
for example, a three-state 'charge' alphabet can be achieved by treating his, lys, and arg as the 'positively charged' state; asp and glu as the 'negatively charged' state; and, all other residues as the 'uncharged' state.
the recoding chosen for a group of sequences constitutes an explicit hypothesis concerning the primary biochemical property subjected to coevolutionary pressures by natural selection.
the motivation for choosing to recode sequences stems from the bias-variance trade-off, where statistical models with fewer parameters have lower variance  but more bias.
a coevolution algorithm applied to sequences with fewer states should therefore have more power to identify pairs of positions which coevolve as a result of the physicochemical property being modeled  because variability within each state is hidden.
information is lost in recoding to a reduced-state alphabet, so the power for detecting coevolution arising from other properties of amino acid residues  decreases.
the sensitivity of inference concerning coevolution to the encoding choice is unclear.
evaluations of coevolution algorithms on simulated data elucidate the strengths and limitations of the algorithms, but are forced to rely on simplifying assumptions about the biological systems being modeled.
evaluations on biological data are therefore important for understanding how an algorithm will perform under more realistic circumstances.
biologically relevant evaluations are difficult however, because we have little knowledge of when sequence positions truly coevolve, and therefore do not have a good idea of what the true positives are.
different approaches have been employed to define coevolutionary positive-controls.
individual cases of coevolution are directly supported by observation of variants known to cause disease in one species in another species  <cit> .
this class of variant has been reported for both rna and protein coding genes and does exhibit strong statistical evidence for coevolution  <cit> .
the suitability of this class of variation for examining the properties of coevolution, however, is low for both practical and biological reasons: the number of cases for which there is sufficient data from related species is low; and, the identification of these variants as pathological suggests the selection coefficients operating on them is very strong and thus may not be representative of the strength of selection responsible for most coevolution.
an alternative approach has been to focus on candidate molecular-structure influences likely to be subjected to natural selection.
past evaluations on  rna alignments have treated base pairs as positive controls and all other pairs as negative controls  <cit> .
these have been useful for comparing algorithms on rna, but it is not clear that performance on rna alignments translates well to performance on protein alignments because interactions between residues in proteins are generally more complex.
protein gold standards have been designed to evaluate a method's ability to identify residue contacts in tertiary structure by defining residues pairs within a certain cβ distance in a representative crystal structure as positive controls, and all other pairs as negative controls  <cit> .
the set of residue pairs within a small cβ distance in tertiary structure in a representative crystal structure is recognized as a coarse criteria because it is not clear that close physical proximity is an essential precondition for coevolution  <cit> , and because a single crystal structure may not accurately describe the tertiary contacts in all sequences in the alignment.
to complement residue-contact-based comparisons, we present a novel secondary-structure-based method for comparing coevolution methods where the known periodic stabilizing interactions between stacked residues in protein alpha helices are taken as positive controls.
double-mutant studies of protein alpha helices have shown that stacked residues in alpha helices interact to stabilize the helix  <cit> .
statistical analyses support these results by showing that the interactions are present in diverse families of alpha helices  <cit> .
stabilization is thought to result from ionic interaction, aromatic-aromatic interaction, or hydrogen bonding between stacked side chains.
although there has been discussion on the validity of these studies  <cit> , biophysical and statistical analyses continue to support the case for stabilizing interactions.
these interactions occur between the stacked positions in the alpha helix, or the positions separated by three residues in primary structure  , and to a lesser extent between positions separated by two residues , corresponding to the  <dig>  residue per turn periodicity of the alpha helix.
since interactions between stacked residues appear important for alpha helix stability, we argue that positions should coevolve to conserve these interactions.
methods for detecting coevolution in proteins should therefore identify stacked residues in alpha helices, as illustrated in  <cit>  providing a positive control for coevolution detection algorithms.
we emphasize that we are not presenting the coevolution algorithms that we test as methods for detecting alpha helices from sequence data, but rather exploiting the known regular structure of the helix as a gold standard for detecting coevolution: methods for detecting coevolution should, at minimum, be able to recapture these regularities.
we report an assessment of the hypothesis that appropriately transformed tree-ignorant metrics have similar statistical power to tree-aware approaches by performing a systematic comparison of nine coevolution algorithms.
five of the algorithms – mutual information , normalized mutual information   <cit> , resampled mutual information  , statistical coupling analysis   <cit> , and corrected mutual information   <cit>  – use multiple sequence alignments but no phylogenetic trees.
the other four methods – lnlcorr  <cit> , ancestral states   <cit> , the generalized continuous-time markov process coevolutionary algorithm   <cit> , and comap  <cit>  – use multiple sequence alignments and phylogenetic trees.
we additionally considered including the method described in  <cit> , but opted to include nmi and mip instead since they are expected to perform better than the former .
the algorithms were compared by application to real  protein sequence alignments.
in a secondary study, our alignments are recoded in  <dig> different reduced-state amino acid alphabets to evaluate the utility of amino acid alphabets which model different chemical properties, and to test the hypothesis that alphabets with fewer states are generally better for detecting coevolution.
RESULTS
five tree-ignorant methods and four tree-aware methods for detecting coevolving positions were compared on four multiple sequence alignments using the full amino acid alphabet and, when applicable,  <dig> reduced amino acid alphabets.
two of the alignments, tetrapod myoglobin  and chordate myosin rod , represent mostly alpha helical protein sequences and thus our positive controls.
the other two alignments are matched negative controls generated by shuffling the order of positions in each observed alignment to remove all structural information.
the statistical significance of coevolution metrics between alignment columns separated by a specified distance was determined using the t-test transformation .
applying a coevolution algorithm to an alignment results in a 'coevolution matrix,' where each position in the lower triangle contains a pairwise coevolutionary score.
each coevolution matrix, constructed based on a combination of method, alignment, and alphabet, was evaluated to determine to what degree the combination allowed detection of the periodicity of the alpha helix.
the distribution of scores from  positions in a coevolution matrix were compared with the distribution of all other scores in the same matrix using a two-sample t-test.
significant p-values at n =  <dig> or n =  <dig> were taken as evidence of a method's ability to detect coevolution, as these are the stacked positions in alpha helices which are expected to coevolve to retain alpha helix stability.
although the coevolutionary scores are not directly comparable between the methods, the t-test transformation standardizes the metrics, allowing evaluation of the relative performance of each method.
we note here that although the distance matrix structure of the result matrices violates the independence clause of the t-test, we validated the robustness of results using a non-parametric matrix permutation test .
tree-aware versus tree-ignorant methods
the tree-ignorant methods are more capable of detecting coevolutionary signal at  and  in myoglobin than the tree-aware methods .
there is no statistically significant difference in performance between the tree-aware methods on myoglobin or the myoglobin negative control .
between the tree-ignorant methods, there is a statistically significant performance difference at  in favor of mip, nmi, and sca ; and at  in favor of nmi and sca .
mi incurred more type  <dig> error than the other methods .
χ <dig> goodness-of-fit tests comparing all applicable tree-aware and all tree-ignorant methods for detecting alpha helix periodicity at separations of  and , using all reduced-state amino acid alphabets, where applicable.
some of the methods  were not run on myosin , causing different numbers of runs on the myosin versus the myoglobin data sets.
additionally, the reduced-state alphabets were not applicable to all tree-aware methods, causing the sum of the p-value counts to differ for the tree-aware versus tree-ignorant methods.
bolded rows highlight statistically significant χ <dig> results, indicating a difference between the tree-aware and tree-ignorant populations.
bold counts in these rows highlight which class of methods achieved the higher ratio of significant to insignificant scores.
counts are calculated including both the empirically determined best and worst sca cutoffs to illustrate the effect of this free parameter on method performance, and with the empirically validated optimal ε =  <dig>  value for gctmpca.
the data suggest that tree-ignorant methods perform better on the myoglobin alignment , and there is no statistically significant difference in the classes on the myosin rod domain alignment except when using the empirically determined worst sca cutoff choice, when the tree-aware methods perform better .
the myoglobin  and myosin  negative controls suggest that there is no significant difference in the type  <dig> error incurred by the classes of methods.
α =  <dig> .
χ <dig> goodness-of-fit tests comparing the performance of tree-aware methods for detecting alpha helix periodicity at  and .
counts are calculated for gctmpca with the empirically validated optimal ε =  <dig> .
in most cases, there is no statistically significant difference in performance between the tree-aware methods with the single exception being  in myosin, where as and comap out-perform lnlcorr <dig>  data is not presented on the myosin alignment for tree-aware methods which proved too computationally intensive to be practical.
counts in table  <dig> can be directly compared with counts in table  <dig>  α =  <dig> .
χ <dig> goodness-of-fit tests comparing the performance of tree-ignorant methods for detecting alpha helix periodicity at  and .
bolded rows highlight statistically significant χ <dig> results, indicating a difference between the methods.
bold counts in these rows highlight which method achieved the highest ratio of significant to insignificant scores.
counts are calculated using the empirically determined optimal sca cutoff for each positive control data point.
sca cutoff is  <dig>  for a-b row  <dig>   <dig>  for a-b row  <dig>   <dig>  for c-d row  <dig>  and  <dig>  for c-d row  <dig>  α =  <dig> .
in myosin, there is no significant difference in the performance of the tree-aware and tree-ignorant methods at  or  after sca cutoff optimization, but before sca optimization the tree-aware algorithms achieve better performance at  .
the absence of a significant difference could reflect either real properties of the methods, or arise from reduced statistical power of this particular comparison.
there is more variability in the branch lengths in the myosin data set , suggesting the possibility that as the relationships between sequences becomes more variable, accounting for those relationships becomes more important.
however, the statistical power of the method comparisons are not identical between the myoglobin and myosin cases.
due to the computational intensity of gctmpca and lnlcorr <dig>  these methods were not practical to run on the myosin alignment and tree.
as a result, the myosin case has a reduced number of observations compared with that for myoglobin which will reduce the statistical power to identify differences between the method classes.
comparing lnlcorr <dig>  comap, and as on myosin shows that there is no statistically significant difference in these methods at   but that as and comap outperform lnlcorr <dig> at  .
of the tree-ignorant methods, there was a statistically significant difference in the performance of the individual methods , and mi achieved the highest ratio of significant to insignificant scores, and fared well in terms of type  <dig> error .
on the myosin negative control, mip achieved significantly more false positives than the other methods .
the ability of mi to out-perform all of the other methods, including the tree-aware methods, is extremely surprising.
the tree-aware and tree-ignorant methods were additionally evaluated on their ability to identify individual coevolving pairs by comparing area under the curve  scores for precision and recall  for each method, alphabet combination .
on the myoglobin data set, the tree-ignorant methods achieved higher auc scores for precision and recall than the tree-aware methods.
on the myosin alignment, the tree-ignorant methods achieved higher auc scores for recall than the tree-aware methods, but the highest precision scores appear similar between the two classes of methods.
on the myoglobin negative control, the tree-ignorant methods achieved higher auc scores for precision and recall, suggesting more false positives for the tree-ignorant methods.
on the myosin negative control, precision appears similar between the two classes, while the tree-ignorant methods appear to have achieved higher recall, indicating more false positives.
because the negative controls are a shuffled version of the original alignments, the total hits count is the same for the positive and negative control coevolution matrices for a given method, alphabet combination .
due to the difficulty of defining positives and negatives , the precision, recall, and f-measure values for the negative controls are less meaningful than for the positive control, but are provided for completeness.
precision and recall results are summarized via f-measure in figure  <dig>  which presents the f-measure aucs achieved by each method with each alphabet.
the median f-measure aucs appear higher for the tree-ignorant methods in both positive and negative controls.
precision, recall, f-measure, total hits, and auc data for all method, alphabet combinations are provided .
alphabet reduction
to evaluate the effect of the size and type of reduced-state alphabets on algorithm performance, each alignment was recoded with  <dig> reduced-state alphabets.
coevolution algorithms were applied to each recoded alignment in addition to the original  alignments.
the  <dig> 'atchley-factor' alphabets are based on five metrics  presented in  <cit> , and are used primarily to evaluate the effect of alphabet size.
the  <dig> 'rationally-designed' alphabets were developed based more canonical amino acid metrics, and are used primarily to evaluate the effect of alphabet type.
alphabet names describe the alphabet type  followed by alphabet size .
for example, a1_ <dig> refers to the a1-based alphabet with four states, and charge_ <dig> refers to the charge-based alphabet with three states.
alphabet definitions are presented in table  <dig>
the data illustrate markedly different results with different alphabet definitions, both in terms of number of states and amino acid property modeled.
the effect of alphabet size
in the myoglobin alignment , there is no clear relationship between performance and number of alphabet states .
the three of thirty-five correlations that are significant after correction for multiple comparisons are positive correlations, suggesting increased performance with more states.
in the negative control  however, the ratio of significant to insignificant correlations is similar.
these data therefore do not strongly support a relationship between alphabet size and method performance.
for each of the five heuristically defined alphabets, kendall correlation coefficients  and corresponding p-values are provided to illustrate the relationship between performance rank and alphabet size.
bolded values highlight p-values =  <dig> , and starred values indicated p-values significant after adjustment for multiple comparisons .
tau range: .
a positive τ value indicates a positive correlation , and a negative τ value indicates a negative correlation .
in the myosin rod alignment  a positive correlation frequently exists between alphabet size and ability to detect alpha helix periodicity , particularly for mi, nmi, and mip.
this suggests that more alphabet states improve performance for these methods on the myosin rod.
seven of the thirty correlation coefficients are significant after correction for multiple comparisons, compared with one of thirty in the negative control .
the effect of alphabet type
the 'rationally-designed' alphabets generally out-perform the atchley-factor alphabets , although the a1-based and a5-based alphabets were frequently among the top performing alphabets.
the charge_* alphabets very commonly yield the most significant p-values at  in both alignments.
as a <dig> and a <dig> are charge and polarity factors, these were expected to perform well.
in myoglobin, of the methods that identified  pairs with statistical significance at α =  <dig> , seventeen of the thirty-five top-performing alphabets were the rationally designed alphabets.
eleven of the eighteen top-performing atchley-factor alphabets were a1- or a5-based.
in myosin, fifteen of the thirty top performing alphabets were rationally designed, and five of the fourteen top-performing atchley-factor alphabets were a1- or a5-based.
one of the top-performing alphabets for mip was the unreduced alphabet .
it is not clear why the a3- and a4-based alphabets performed better in myosin, although these mostly did well with rmi.
rmi exhibits very little variance in p-value based on choice of alphabet , which may make p-value-based ranking less meaningful.
because lnlcorr <dig> and comap use alphabets differently from the other algorithms , the corresponding counts of atchley-factor and 'rationally-designed' alphabets were not included in these computations.
top-performing alphabets for these methods are however presented .
the four-state alphabet based on atchley factor  <dig>  shows up frequently in the top alphabets, and on inspection appears to mirror the decisions that might be made if manually defining an alphabet based on this metric .
these bins mimic natural break-points in this metric, with the exception of q being in bin  <dig>  the generally high performance of coevolution methods working on alignments encoded in a1_ <dig> suggests that it may compliment the use of the more canonical reduced-state alphabets, and that other atchley-factor alphabets defined based on natural breaks in the data may also yield good results.
gctmpca and sca parameters
sca and gctmpca both require a single parameter  from the user.
experimentation with the values of these parameters was incorporated into the analyses, and was found to have a strong effect on method performance.
<cit>  and  <cit>  suggest  <dig>  as an optimal setting for ε. this was empirically validated here by comparing performance for detecting signal at  and  in myoglobin using the full amino acid alphabet and two reduced-state alphabets .
the optimal value for the sca cutoff parameter was empirically found to be variable  and did not match the values obtained as recommended in  <cit> .
when applied to the alignments without alphabet reduction, the recommended steps identify  <dig>  as the optimal value for myosin, and  <dig>  as the optimal value for myoglobin .
the empirically-determined optimal cutoff for detecting coevolutionary signal at  in myosin was  <dig> , and in myoglobin was  <dig> , when no alphabet reduction was applied.
these results suggest that the steps presented in  <cit>  will not always identify the optimal cutoff, and experimentation with the cutoff value should therefore be incorporated into applications of sca.
discussion
tree-aware versus tree-ignorant techniques
tree-ignorant coevolution algorithms matched or out-performed the tree-aware coevolution algorithms for identifying coevolving positions in alpha helices.
with the exception of comap, the tree-aware methods also generally required vastly more compute time than the tree-ignorant methods, despite the slowest of these algorithms  being implemented in c while the other algorithms are predominantly implemented in python .
the c++ implementation of comap was the fastest of the methods.
in some cases, standard mutual information out-performed all other algorithms .
these observations suggest that when transformed in a manner that adjusts for shared ancestry, as demonstrated here, tree-ignorant methods can be more reliable than tree-aware methods.
although consideration of additional genes with substantial sampled lineages may support a convergence in robustness between the two method classes, the computational performance advantage of tree-ignorant methods establishes them as the metric of choice for comprehensive surveys of molecular coevolution.
the ability of tree-ignorant methods, and mi in particular, to out-perform tree-aware methods is a seemingly surprising result given previous demonstrations of high false positives for this method class.
we have argued, and our results demonstrate, the t-test transformation provides sufficient control for the shared ancestry cause of associations.
because every column  in an alignment has the same underlying relationship among the rows , every estimated pairwise coevolution score will have this influence in common.
pairs with a true coevolutionary history will have both that shared ancestry and the additional influence of coevolution, and so should stand out from the non-coevolving pairs.
alphabet size
larger alphabets frequently improve performance of coevolution algorithms  on the myosin data set, but there is no obvious relationship between alphabet size and coevolution algorithm performance on the myoglobin data.
the differences observed on myoglobin and myosin may be explainable by differences in the quantity of input data.
the myosin rod data set has more sequences than the myoglobin data set, and therefore more states to observe when calculating a pairwise coevolution score between two columns.
grouping residues via reduced alphabets is expected to improve statistical performance by providing a clearer picture of the distribution of residue types.
the additional observations  present in the myosin alignment appear sufficient to describe the residue distribution without recoding, and the information loss associated with recoding in fewer states may therefore result in decreased statistical performance.
the lack of a significant positive or negative correlation between alphabet size and statistical performance on myoglobin suggests that  higher-state alphabets are not better, and that a generic benefit associated with fewer-state alphabets may only arise on alignments with less sequences than the myoglobin data.
an alternative explanation for the positive correlation between alphabet size and performance in myosin is that the atchley-factor alphabets are not useful categorizations of the data.
if true, as the number of states increases  they should perform better.
the strongest correlations however are achieved with the a <dig> and a <dig> alphabets, which are the atchley-factor alphabets that are expected to perform the best .
some of the best performances overall were achieved using these alphabets , so this explanation appears unlikely.
much previous work, including  <cit>  which used the same myoglobin alignment and tree, has focused on the assumption that smaller alphabets are generally better.
if true, a negative correlation should exist between alphabet size and method performance.
this is not observed, suggesting that in practice smaller alphabets do not necessarily improve statistical performance.
alphabet type
if probing for coevolution resulting from a specific type of physicochemical interaction, a reduced alphabet which models that physicochemical property in fewer states should increase power.
there is serious risk, however, of losing power by using the incorrect reduced alphabet.
for example, the p-value for identifying signal at  with mi increased  from  <dig>  × 10- <dig> with the charge_ <dig> alphabet, to  <dig>  × 10- <dig> with the size_ <dig> alphabet.
for all methods analyzed on myosin with reduced alphabets – as, mi, nmi, rmi, mip, and sca – the size_ <dig> alphabet always resulted in less significant p-values than the charge_ <dig> alphabet.
this illustrates that recoding with the correct alphabet  will highlight a coevolutionary relationship based on that property, but that recoding with an incorrect alphabet  will obscure the coevolutionary signal.
non-sensical alphabet recoding should destroy the coevolutionary signal.
if the interaction type  is not known ahead of time, using the unreduced alphabet can provide useful results and should be safer than making an uninformed choice of reduced alphabet.
the importance of choosing the 'correct' reduced alphabet is illustrated by variable performance of a single algorithm even when the alphabet choices have the same number of states.
for detecting coevolutionary signal between stacked residues in alpha helices, the reduced alphabets which model charge/polarity perform the best.
these include the four charge_* alphabets  and the alphabets based on atchley factors  <dig> and  <dig>  these would not be the best alphabets if the interactions were based on a different physicochemical property.
the success of charge-based alphabets for identifying stacked positions in alpha helices confirms the previous biochemical and statistical observations, and suggests that alphabet recoding can be applied to probe interaction types.
for example, if a coevolutionary interaction is apparent when working with a size-based alphabet, but disappears when working with a charge-based alphabet, the interaction is likely more related to size than charge.
this is observed when looking at  pairs in the myosin rod using mi with the size_ <dig> and charge_ <dig> alphabets .
coevolution on the basis of side-chain volume between  pairs, which form the set of residues which are presumably closest to one-another in the folded protein, seems likely.
classification of interaction types based on these characteristics is often likely to be overly simplistic, but probing interactions this way may serve as a starting point for more in-depth analysis.
care should be taken however to avoid spurious conclusions arising from multiple comparisons when repeatedly applying a coevolution algorithm to the same alignment recoded with multiple alphabets.
utility of alpha-helical protein alignments for comparing coevolution algorithms
this article presents a comparison of nine coevolution detection methods on two different molecules which are entirely  or almost entirely  alpha helical.
the two alignments are different in terms of number of sequences, diversity of sequences, and sequence length, yet in both cases the algorithms are able to detect  the periodicity of the alpha helix.
the coevolution of stacked residues in protein alpha helices, identifiable computationally and supported by double-mutant studies, makes alignments of alpha helices useful for comparing techniques for detecting coevolution.
unfortunately, we cannot generalize this approach to beta sheets, because the length of the beta strands is highly variable and there is thus no consistent periodic signal expected to be consistent across different proteins.
the charge_his_ <dig> alphabet, where residues are recoded to charged or uncharged with histidine counted as charged, was consistently among the best alphabets for detecting coevolution at  and  in myoglobin.
figure  <dig> reports p-values for ten algorithms for detecting coevolution at , for n of  <dig> through  <dig>  where alignments were recoded in the charge_his_ <dig> alphabet.
these graphs are a useful visualization of the relative performance of different algorithms or parameters because positive and negative controls are built-in.
since myoglobin is composed of non-contiguous alpha helices, a signal should be visible at n =  <dig>  and n =  <dig> , and not at other values of n. we see that most of the methods identify at least one of these with statistical significance, even after bonferroni correction for multiple comparisons.
as appears to yield a false positive at n =  <dig>
long-distance signal in myosin rod
the period of the alpha helix is  <dig> .
direct interactions due to stacking of more distant pairs should therefore occur at multiples of  <dig>  .
instead, we see distant interactions at multiples of  <dig>  .
this suggests that the direct interactions occur locally: we see a signal at  <dig>  not at  <dig>  because it is the result of a series of direct local interactions   <dig> positions apart.
the myosin rod is composed of  <dig> residue homologous units, each composed of four heptad repeats.
these repeat regions could be an alternative explanation for the signal at multiples of seven, but this seems less likely.
following evolution of the myosin rod, it is not clear what would drive coevolution of these units, and because conservation reduces mi for a pair of positions, the common ancestry followed by conservation would have the opposite effect.
the process of coevolution is not well understood and there has been very little conclusive evidence about the forces driving coevolution in proteins.
in the case of alpha helices, it appears that distant coevolutionary relationships are the result of indirect correlations rather than residue stacking.
CONCLUSIONS
the analyses presented here support our conjecture that robust estimation of coevolution hinges on comparison to a null distribution with equivalent shared ancestry, and that this property can be achieved without explicitly including the tree in the coevolution metric.
we demonstrated that transformed tree-ignorant methods detect coevolution with equivalent or better power than tree-aware methods when applied to detect the periodicity of protein alpha helices.
a useful next step would involve confirming these results with other evaluations, perhaps based on identifying positions proximal in tertiary structure or individual pairs of coevolving positions which have been biochemically shown to coevolve.
the robust statistical properties of transformed tree-ignorant metrics coupled with their generally many orders of magnitude faster computational speed opens up new prospects for detection of coevolving residues within and between proteins.
we expect that the application of these methods on a massive scale will provide new insights into the evolution of the structures, functions, and interactions of a wide range of protein families.

 knowledge of positions that coevolve in biological sequences can be applied to predict structures of rnas and proteins; to predict intermolecular interactions; to identify functionally important regions of molecules; and to identify energetic pathways through molecules. coevolutionary analyses have frequently been performed on one or a few protein families. however, just as the adaptive evolution database allows proteome-wide studies of evolutionary rates, proteome-wide studies of coevolution could also be could performed if sufficiently fast and well-characterized methods for detecting coevolution were available. as biological sequences are the product of an evolutionary process, it intuitively makes sense that the accuracy of analyses of the historical processes affecting them will be improved by explicit representation of those historical processes. incorporation of phylogenetic information has benefited diverse classes of bioinformatics algorithms, including multiple sequence alignment, comparison of microbial communities, and functional annotation of genes. accordingly, incorporation of phylogenetic knowledge to control for patterns in biological sequence data that arise from ancestry is regarded as essential for coevolutionary analyses and best achieved by directly incorporating the phylogeny in the metric. many coevolution algorithms have explicitly attempted to control for phylogeny, while others have implicitly assumed a star phylogeny. drawbacks have been identified for both approaches. likelihood based tree-aware methods have the disadvantage of being sensitive to model mis-specification, a property common to all likelihood methods, and generally have a much longer compute time than tree-ignorant methods. tree-ignorant methods are thought to have decreased specificity due to confounding of correlations arising from selective pressure with correlations arising from shared ancestry represented by the phylogeny. past evaluations of the effect of tree topology on the performance of coevolution algorithms have used simulated data, and have confirmed that non-star tree topologies can cause false positives. clearly, controlling for shared ancestry is essential but approaches that do so without explicitly representing the phylogenetic tree are possible. we hypothesized a tree-ignorant statistic can be informative if it is compared to a distribution of the same statistic with the same embedded ancestry but variable in coevolution. in this case, the shared ancestry origin of correlated evolution dominates the background distribution. a greater magnitude of correlated evolution than this background is thus evidence of coevolution. an additional consideration for estimating coevolution is that encoding protein alignments with reduced-state amino acid alphabets reduces computational complexity, and may also increase statistical power. in a reduced-state alphabet, the twenty amino acids are collapsed to a smaller number of states. for example, a three-state'charge' alphabet can be achieved by treating his, lys, and arg as the'positively charged' state; asp and glu as the'negatively charged' state; and, all other residues as the'uncharged' state. the recoding chosen for a group of sequences constitutes an explicit hypothesis concerning the primary biochemical property subjected to coevolutionary pressures by natural selection. the motivation for choosing to recode sequences stems from the bias-variance trade-off, where statistical models with fewer parameters have lower variance but more bias. a coevolution algorithm applied to sequences with fewer states should therefore have more power to identify pairs of positions which coevolve as a result of the physicochemical property being modeled because variability within each state is hidden. information is lost in recoding to a reduced-state alphabet, so the power for detecting coevolution arising from other properties of amino acid residues decreases. the sensitivity of inference concerning coevolution to the encoding choice is unclear. evaluations of coevolution algorithms on simulated data elucidate the strengths and limitations of the algorithms, but are forced to rely on simplifying assumptions about the biological systems being modeled. evaluations on biological data are therefore important for understanding how an algorithm will perform under more realistic circumstances. biologically relevant evaluations are difficult however, because we have little knowledge of when sequence positions truly coevolve, and therefore do not have a good idea of what the true positives are. different approaches have been employed to define coevolutionary positive-controls. individual cases of coevolution are directly supported by observation of variants known to cause disease in one species in another species. this class of variant has been reported for both rna and protein coding genes and does exhibit strong statistical evidence for coevolution. the suitability of this class of variation for examining the properties of coevolution, however, is low for both practical and biological reasons: the number of cases for which there is sufficient data from related species is low; and, the identification of these variants as pathological suggests the selection coefficients operating on them is very strong and thus may not be representative of the strength of selection responsible for most coevolution. an alternative approach has been to focus on candidate molecular-structure influences likely to be subjected to natural selection. past evaluations on rna alignments have treated base pairs as positive controls and all other pairs as negative controls. these have been useful for comparing algorithms on rna, but it is not clear that performance on rna alignments translates well to performance on protein alignments because interactions between residues in proteins are generally more complex. protein gold standards have been designed to evaluate a method's ability to identify residue contacts in tertiary structure by defining residues pairs within a certain cβ distance in a representative crystal structure as positive controls, and all other pairs as negative controls. the set of residue pairs within a small cβ distance in tertiary structure in a representative crystal structure is recognized as a coarse criteria because it is not clear that close physical proximity is an essential precondition for coevolution, and because a single crystal structure may not accurately describe the tertiary contacts in all sequences in the alignment. to complement residue-contact-based comparisons, we present a novel secondary-structure-based method for comparing coevolution methods where the known periodic stabilizing interactions between stacked residues in protein alpha helices are taken as positive controls. double-mutant studies of protein alpha helices have shown that stacked residues in alpha helices interact to stabilize the helix. statistical analyses support these results by showing that the interactions are present in diverse families of alpha helices. stabilization is thought to result from ionic interaction, aromatic-aromatic interaction, or hydrogen bonding between stacked side chains. although there has been discussion on the validity of these studies, biophysical and statistical analyses continue to support the case for stabilizing interactions. these interactions occur between the stacked positions in the alpha helix, or the positions separated by three residues in primary structure, and to a lesser extent between positions separated by two residues, corresponding to the residue per turn periodicity of the alpha helix. since interactions between stacked residues appear important for alpha helix stability, we argue that positions should coevolve to conserve these interactions. methods for detecting coevolution in proteins should therefore identify stacked residues in alpha helices, as illustrated in providing a positive control for coevolution detection algorithms. we emphasize that we are not presenting the coevolution algorithms that we test as methods for detecting alpha helices from sequence data, but rather exploiting the known regular structure of the helix as a gold standard for detecting coevolution: methods for detecting coevolution should, at minimum, be able to recapture these regularities. we report an assessment of the hypothesis that appropriately transformed tree-ignorant metrics have similar statistical power to tree-aware approaches by performing a systematic comparison of nine coevolution algorithms. five of the algorithms – mutual information, normalized mutual information, resampled mutual information, statistical coupling analysis, and corrected mutual information – use multiple sequence alignments but no phylogenetic trees. the other four methods – lnlcorr, ancestral states, the generalized continuous-time markov process coevolutionary algorithm, and comap – use multiple sequence alignments and phylogenetic trees. we additionally considered including the method described in, but opted to include nmi and mip instead since they are expected to perform better than the former. the algorithms were compared by application to real protein sequence alignments. in a secondary study, our alignments are recoded in different reduced-state amino acid alphabets to evaluate the utility of amino acid alphabets which model different chemical properties, and to test the hypothesis that alphabets with fewer states are generally better for detecting coevolution.  five tree-ignorant methods and four tree-aware methods for detecting coevolving positions were compared on four multiple sequence alignments using the full amino acid alphabet and, when applicable, reduced amino acid alphabets. two of the alignments, tetrapod myoglobin and chordate myosin rod, represent mostly alpha helical protein sequences and thus our positive controls. the other two alignments are matched negative controls generated by shuffling the order of positions in each observed alignment to remove all structural information. the statistical significance of coevolution metrics between alignment columns separated by a specified distance was determined using the t-test transformation. applying a coevolution algorithm to an alignment results in a'coevolution matrix,' where each position in the lower triangle contains a pairwise coevolutionary score. each coevolution matrix, constructed based on a combination of method, alignment, and alphabet, was evaluated to determine to what degree the combination allowed detection of the periodicity of the alpha helix. the distribution of scores from positions in a coevolution matrix were compared with the distribution of all other scores in the same matrix using a two-sample t-test. significant p-values at n = or n = were taken as evidence of a method's ability to detect coevolution, as these are the stacked positions in alpha helices which are expected to coevolve to retain alpha helix stability. although the coevolutionary scores are not directly comparable between the methods, the t-test transformation standardizes the metrics, allowing evaluation of the relative performance of each method. we note here that although the distance matrix structure of the result matrices violates the independence clause of the t-test, we validated the robustness of results using a non-parametric matrix permutation test. tree-aware versus tree-ignorant methods the tree-ignorant methods are more capable of detecting coevolutionary signal at and in myoglobin than the tree-aware methods. there is no statistically significant difference in performance between the tree-aware methods on myoglobin or the myoglobin negative control. between the tree-ignorant methods, there is a statistically significant performance difference at in favor of mip, nmi, and sca; and at in favor of nmi and sca. mi incurred more type error than the other methods. χ goodness-of-fit tests comparing all applicable tree-aware and all tree-ignorant methods for detecting alpha helix periodicity at separations of and, using all reduced-state amino acid alphabets, where applicable. some of the methods were not run on myosin, causing different numbers of runs on the myosin versus the myoglobin data sets. additionally, the reduced-state alphabets were not applicable to all tree-aware methods, causing the sum of the p-value counts to differ for the tree-aware versus tree-ignorant methods. bolded rows highlight statistically significant χ results, indicating a difference between the tree-aware and tree-ignorant populations. bold counts in these rows highlight which class of methods achieved the higher ratio of significant to insignificant scores. counts are calculated including both the empirically determined best and worst sca cutoffs to illustrate the effect of this free parameter on method performance, and with the empirically validated optimal ε = value for gctmpca. the data suggest that tree-ignorant methods perform better on the myoglobin alignment, and there is no statistically significant difference in the classes on the myosin rod domain alignment except when using the empirically determined worst sca cutoff choice, when the tree-aware methods perform better. the myoglobin and myosin negative controls suggest that there is no significant difference in the type error incurred by the classes of methods. α =. χ goodness-of-fit tests comparing the performance of tree-aware methods for detecting alpha helix periodicity at and. counts are calculated for gctmpca with the empirically validated optimal ε =. in most cases, there is no statistically significant difference in performance between the tree-aware methods with the single exception being in myosin, where as and comap out-perform lnlcorr data is not presented on the myosin alignment for tree-aware methods which proved too computationally intensive to be practical. counts in table can be directly compared with counts in table α =. χ goodness-of-fit tests comparing the performance of tree-ignorant methods for detecting alpha helix periodicity at and. bolded rows highlight statistically significant χ results, indicating a difference between the methods. bold counts in these rows highlight which method achieved the highest ratio of significant to insignificant scores. counts are calculated using the empirically determined optimal sca cutoff for each positive control data point. sca cutoff is for a-b row for a-b row for c-d row and for c-d row α =. in myosin, there is no significant difference in the performance of the tree-aware and tree-ignorant methods at or after sca cutoff optimization, but before sca optimization the tree-aware algorithms achieve better performance at. the absence of a significant difference could reflect either real properties of the methods, or arise from reduced statistical power of this particular comparison. there is more variability in the branch lengths in the myosin data set, suggesting the possibility that as the relationships between sequences becomes more variable, accounting for those relationships becomes more important. however, the statistical power of the method comparisons are not identical between the myoglobin and myosin cases. due to the computational intensity of gctmpca and lnlcorr these methods were not practical to run on the myosin alignment and tree. as a result, the myosin case has a reduced number of observations compared with that for myoglobin which will reduce the statistical power to identify differences between the method classes. comparing lnlcorr comap, and as on myosin shows that there is no statistically significant difference in these methods at but that as and comap outperform lnlcorr at. of the tree-ignorant methods, there was a statistically significant difference in the performance of the individual methods, and mi achieved the highest ratio of significant to insignificant scores, and fared well in terms of type error. on the myosin negative control, mip achieved significantly more false positives than the other methods. the ability of mi to out-perform all of the other methods, including the tree-aware methods, is extremely surprising. the tree-aware and tree-ignorant methods were additionally evaluated on their ability to identify individual coevolving pairs by comparing area under the curve scores for precision and recall for each method, alphabet combination. on the myoglobin data set, the tree-ignorant methods achieved higher auc scores for precision and recall than the tree-aware methods. on the myosin alignment, the tree-ignorant methods achieved higher auc scores for recall than the tree-aware methods, but the highest precision scores appear similar between the two classes of methods. on the myoglobin negative control, the tree-ignorant methods achieved higher auc scores for precision and recall, suggesting more false positives for the tree-ignorant methods. on the myosin negative control, precision appears similar between the two classes, while the tree-ignorant methods appear to have achieved higher recall, indicating more false positives. because the negative controls are a shuffled version of the original alignments, the total hits count is the same for the positive and negative control coevolution matrices for a given method, alphabet combination. due to the difficulty of defining positives and negatives, the precision, recall, and f-measure values for the negative controls are less meaningful than for the positive control, but are provided for completeness. precision and recall results are summarized via f-measure in figure which presents the f-measure aucs achieved by each method with each alphabet. the median f-measure aucs appear higher for the tree-ignorant methods in both positive and negative controls. precision, recall, f-measure, total hits, and auc data for all method, alphabet combinations are provided. alphabet reduction to evaluate the effect of the size and type of reduced-state alphabets on algorithm performance, each alignment was recoded with reduced-state alphabets. coevolution algorithms were applied to each recoded alignment in addition to the original alignments. the'atchley-factor' alphabets are based on five metrics presented in, and are used primarily to evaluate the effect of alphabet size. the'rationally-designed' alphabets were developed based more canonical amino acid metrics, and are used primarily to evaluate the effect of alphabet type. alphabet names describe the alphabet type followed by alphabet size. for example, a1_ refers to the a1-based alphabet with four states, and charge_ refers to the charge-based alphabet with three states. alphabet definitions are presented in table the data illustrate markedly different results with different alphabet definitions, both in terms of number of states and amino acid property modeled. the effect of alphabet size in the myoglobin alignment, there is no clear relationship between performance and number of alphabet states. the three of thirty-five correlations that are significant after correction for multiple comparisons are positive correlations, suggesting increased performance with more states. in the negative control however, the ratio of significant to insignificant correlations is similar. these data therefore do not strongly support a relationship between alphabet size and method performance. for each of the five heuristically defined alphabets, kendall correlation coefficients and corresponding p-values are provided to illustrate the relationship between performance rank and alphabet size. bolded values highlight p-values =, and starred values indicated p-values significant after adjustment for multiple comparisons. tau range:. a positive τ value indicates a positive correlation, and a negative τ value indicates a negative correlation. in the myosin rod alignment a positive correlation frequently exists between alphabet size and ability to detect alpha helix periodicity, particularly for mi, nmi, and mip. this suggests that more alphabet states improve performance for these methods on the myosin rod. seven of the thirty correlation coefficients are significant after correction for multiple comparisons, compared with one of thirty in the negative control. the effect of alphabet type the'rationally-designed' alphabets generally out-perform the atchley-factor alphabets, although the a1-based and a5-based alphabets were frequently among the top performing alphabets. the charge_* alphabets very commonly yield the most significant p-values at in both alignments. as a and a are charge and polarity factors, these were expected to perform well. in myoglobin, of the methods that identified pairs with statistical significance at α =, seventeen of the thirty-five top-performing alphabets were the rationally designed alphabets. eleven of the eighteen top-performing atchley-factor alphabets were a1- or a5-based. in myosin, fifteen of the thirty top performing alphabets were rationally designed, and five of the fourteen top-performing atchley-factor alphabets were a1- or a5-based. one of the top-performing alphabets for mip was the unreduced alphabet. it is not clear why the a3- and a4-based alphabets performed better in myosin, although these mostly did well with rmi. rmi exhibits very little variance in p-value based on choice of alphabet, which may make p-value-based ranking less meaningful. because lnlcorr and comap use alphabets differently from the other algorithms, the corresponding counts of atchley-factor and'rationally-designed' alphabets were not included in these computations. top-performing alphabets for these methods are however presented. the four-state alphabet based on atchley factor shows up frequently in the top alphabets, and on inspection appears to mirror the decisions that might be made if manually defining an alphabet based on this metric. these bins mimic natural break-points in this metric, with the exception of q being in bin the generally high performance of coevolution methods working on alignments encoded in a1_ suggests that it may compliment the use of the more canonical reduced-state alphabets, and that other atchley-factor alphabets defined based on natural breaks in the data may also yield good results. gctmpca and sca parameters sca and gctmpca both require a single parameter from the user. experimentation with the values of these parameters was incorporated into the analyses, and was found to have a strong effect on method performance. and suggest as an optimal setting for ε. this was empirically validated here by comparing performance for detecting signal at and in myoglobin using the full amino acid alphabet and two reduced-state alphabets. the optimal value for the sca cutoff parameter was empirically found to be variable and did not match the values obtained as recommended in. when applied to the alignments without alphabet reduction, the recommended steps identify as the optimal value for myosin, and as the optimal value for myoglobin. the empirically-determined optimal cutoff for detecting coevolutionary signal at in myosin was, and in myoglobin was, when no alphabet reduction was applied. these results suggest that the steps presented in will not always identify the optimal cutoff, and experimentation with the cutoff value should therefore be incorporated into applications of sca. discussion tree-aware versus tree-ignorant techniques tree-ignorant coevolution algorithms matched or out-performed the tree-aware coevolution algorithms for identifying coevolving positions in alpha helices. with the exception of comap, the tree-aware methods also generally required vastly more compute time than the tree-ignorant methods, despite the slowest of these algorithms being implemented in c while the other algorithms are predominantly implemented in python. the c++ implementation of comap was the fastest of the methods. in some cases, standard mutual information out-performed all other algorithms. these observations suggest that when transformed in a manner that adjusts for shared ancestry, as demonstrated here, tree-ignorant methods can be more reliable than tree-aware methods. although consideration of additional genes with substantial sampled lineages may support a convergence in robustness between the two method classes, the computational performance advantage of tree-ignorant methods establishes them as the metric of choice for comprehensive surveys of molecular coevolution. the ability of tree-ignorant methods, and mi in particular, to out-perform tree-aware methods is a seemingly surprising result given previous demonstrations of high false positives for this method class. we have argued, and our results demonstrate, the t-test transformation provides sufficient control for the shared ancestry cause of associations. because every column in an alignment has the same underlying relationship among the rows, every estimated pairwise coevolution score will have this influence in common. pairs with a true coevolutionary history will have both that shared ancestry and the additional influence of coevolution, and so should stand out from the non-coevolving pairs. alphabet size larger alphabets frequently improve performance of coevolution algorithms on the myosin data set, but there is no obvious relationship between alphabet size and coevolution algorithm performance on the myoglobin data. the differences observed on myoglobin and myosin may be explainable by differences in the quantity of input data. the myosin rod data set has more sequences than the myoglobin data set, and therefore more states to observe when calculating a pairwise coevolution score between two columns. grouping residues via reduced alphabets is expected to improve statistical performance by providing a clearer picture of the distribution of residue types. the additional observations present in the myosin alignment appear sufficient to describe the residue distribution without recoding, and the information loss associated with recoding in fewer states may therefore result in decreased statistical performance. the lack of a significant positive or negative correlation between alphabet size and statistical performance on myoglobin suggests that higher-state alphabets are not better, and that a generic benefit associated with fewer-state alphabets may only arise on alignments with less sequences than the myoglobin data. an alternative explanation for the positive correlation between alphabet size and performance in myosin is that the atchley-factor alphabets are not useful categorizations of the data. if true, as the number of states increases they should perform better. the strongest correlations however are achieved with the a and a alphabets, which are the atchley-factor alphabets that are expected to perform the best. some of the best performances overall were achieved using these alphabets, so this explanation appears unlikely. much previous work, including which used the same myoglobin alignment and tree, has focused on the assumption that smaller alphabets are generally better. if true, a negative correlation should exist between alphabet size and method performance. this is not observed, suggesting that in practice smaller alphabets do not necessarily improve statistical performance. alphabet type if probing for coevolution resulting from a specific type of physicochemical interaction, a reduced alphabet which models that physicochemical property in fewer states should increase power. there is serious risk, however, of losing power by using the incorrect reduced alphabet. for example, the p-value for identifying signal at with mi increased from × 10- with the charge_ alphabet, to × 10- with the size_ alphabet. for all methods analyzed on myosin with reduced alphabets – as, mi, nmi, rmi, mip, and sca – the size_ alphabet always resulted in less significant p-values than the charge_ alphabet. this illustrates that recoding with the correct alphabet will highlight a coevolutionary relationship based on that property, but that recoding with an incorrect alphabet will obscure the coevolutionary signal. non-sensical alphabet recoding should destroy the coevolutionary signal. if the interaction type is not known ahead of time, using the unreduced alphabet can provide useful results and should be safer than making an uninformed choice of reduced alphabet. the importance of choosing the'correct' reduced alphabet is illustrated by variable performance of a single algorithm even when the alphabet choices have the same number of states. for detecting coevolutionary signal between stacked residues in alpha helices, the reduced alphabets which model charge/polarity perform the best. these include the four charge_* alphabets and the alphabets based on atchley factors and these would not be the best alphabets if the interactions were based on a different physicochemical property. the success of charge-based alphabets for identifying stacked positions in alpha helices confirms the previous biochemical and statistical observations, and suggests that alphabet recoding can be applied to probe interaction types. for example, if a coevolutionary interaction is apparent when working with a size-based alphabet, but disappears when working with a charge-based alphabet, the interaction is likely more related to size than charge. this is observed when looking at pairs in the myosin rod using mi with the size_ and charge_ alphabets. coevolution on the basis of side-chain volume between pairs, which form the set of residues which are presumably closest to one-another in the folded protein, seems likely. classification of interaction types based on these characteristics is often likely to be overly simplistic, but probing interactions this way may serve as a starting point for more in-depth analysis. care should be taken however to avoid spurious conclusions arising from multiple comparisons when repeatedly applying a coevolution algorithm to the same alignment recoded with multiple alphabets. utility of alpha-helical protein alignments for comparing coevolution algorithms this article presents a comparison of nine coevolution detection methods on two different molecules which are entirely or almost entirely alpha helical. the two alignments are different in terms of number of sequences, diversity of sequences, and sequence length, yet in both cases the algorithms are able to detect the periodicity of the alpha helix. the coevolution of stacked residues in protein alpha helices, identifiable computationally and supported by double-mutant studies, makes alignments of alpha helices useful for comparing techniques for detecting coevolution. unfortunately, we cannot generalize this approach to beta sheets, because the length of the beta strands is highly variable and there is thus no consistent periodic signal expected to be consistent across different proteins. the charge_his_ alphabet, where residues are recoded to charged or uncharged with histidine counted as charged, was consistently among the best alphabets for detecting coevolution at and in myoglobin. figure reports p-values for ten algorithms for detecting coevolution at, for n of through where alignments were recoded in the charge_his_ alphabet. these graphs are a useful visualization of the relative performance of different algorithms or parameters because positive and negative controls are built-in. since myoglobin is composed of non-contiguous alpha helices, a signal should be visible at n = and n =, and not at other values of n. we see that most of the methods identify at least one of these with statistical significance, even after bonferroni correction for multiple comparisons. as appears to yield a false positive at n = long-distance signal in myosin rod the period of the alpha helix is. direct interactions due to stacking of more distant pairs should therefore occur at multiples of. instead, we see distant interactions at multiples of. this suggests that the direct interactions occur locally: we see a signal at not at because it is the result of a series of direct local interactions positions apart. the myosin rod is composed of residue homologous units, each composed of four heptad repeats. these repeat regions could be an alternative explanation for the signal at multiples of seven, but this seems less likely. following evolution of the myosin rod, it is not clear what would drive coevolution of these units, and because conservation reduces mi for a pair of positions, the common ancestry followed by conservation would have the opposite effect. the process of coevolution is not well understood and there has been very little conclusive evidence about the forces driving coevolution in proteins. in the case of alpha helices, it appears that distant coevolutionary relationships are the result of indirect correlations rather than residue stacking.  the analyses presented here support our conjecture that robust estimation of coevolution hinges on comparison to a null distribution with equivalent shared ancestry, and that this property can be achieved without explicitly including the tree in the coevolution metric. we demonstrated that transformed tree-ignorant methods detect coevolution with equivalent or better power than tree-aware methods when applied to detect the periodicity of protein alpha helices. a useful next step would involve confirming these results with other evaluations, perhaps based on identifying positions proximal in tertiary structure or individual pairs of coevolving positions which have been biochemically shown to coevolve. the robust statistical properties of transformed tree-ignorant metrics coupled with their generally many orders of magnitude faster computational speed opens up new prospects for detection of coevolving residues within and between proteins. we expect that the application of these methods on a massive scale will provide new insights into the evolution of the structures, functions, and interactions of a wide range of protein families. 
using a novel t-test transformation of coevolution metrics, we systematically compared four tree-aware and five tree-ignorant coevolution algorithms, applying them to myoglobin and myosin. the results suggest that t-test transformation of tree-ignorant metrics can be sufficient to control for patterns arising from shared ancestry. we conjectured that by using a null distribution that appropriately controls for the shared-ancestry signal, tree-ignorant methods would exhibit equivalent statistical power to tree-aware methods. we further considered the influence of sequence recoding using reduced-state amino acid alphabets, a common tactic employed in coevolutionary analyses to improve both statistical and computational performance. consistent with our conjecture, the transformed tree-ignorant metrics often outperformed the tree-aware metrics. tree-ignorant methods are frequently orders of magnitude faster, but are widely held to be insufficiently accurate because of a confounding of shared ancestry with coevolution. our examination of the effect of recoding suggested that charge-based alphabets were generally superior for identifying the stabilizing interactions in alpha helices.
 identifying coevolving positions in protein sequences has myriad applications, ranging from understanding and predicting the structure of single molecules to generating proteome-wide predictions of interactions. algorithms for detecting coevolving positions can be classified into two categories: tree-aware, which incorporate knowledge of phylogeny, and tree-ignorant, which do not. tree-ignorant methods are frequently orders of magnitude faster, but are widely held to be insufficiently accurate because of a confounding of shared ancestry with coevolution. we conjectured that by using a null distribution that appropriately controls for the shared-ancestry signal, tree-ignorant methods would exhibit equivalent statistical power to tree-aware methods. using a novel t-test transformation of coevolution metrics, we systematically compared four tree-aware and five tree-ignorant coevolution algorithms, applying them to myoglobin and myosin. we further considered the influence of sequence recoding using reduced-state amino acid alphabets, a common tactic employed in coevolutionary analyses to improve both statistical and computational performance.  consistent with our conjecture, the transformed tree-ignorant metrics often outperformed the tree-aware metrics. our examination of the effect of recoding suggested that charge-based alphabets were generally superior for identifying the stabilizing interactions in alpha helices. performance was not always improved by recoding however, indicating that the choice of alphabet is critical.  the results suggest that t-test transformation of tree-ignorant metrics can be sufficient to control for patterns arising from shared ancestry. 