BACKGROUND
alignment between sequences is useful and ubiquitous in bioinformatics  <cit> .
many of the advances made in the field of bioinformatics can be attributed to advances in alignment of sequences.
the performance of homology-based structural modeling methods in casp over last several years is strongly correlated to the accuracy of the alignment between template and the target  <cit> .
alignments are also routinely generated for effective identification of remote homologues leading to function annotation of newly discovered proteins from genome sequence data  <cit> .
the explosion of sequence data from genome sequencing projects has exposed the limitation of current methods to recognize homologues in the twilight region  and beyond .
it was found quite early that profile methods, such as psi-blast  <cit>  can be more sensitive and accurate than single sequence-based methods.
the starting point for deriving various kinds of profiles such as position specific scoring matrices  and hidden markov models  is an alignment of sequences of homologous proteins or protein domains.
the commonly used profiles are the psi-blast generated pssms derived from query dependent alignments  <cit> , multiple sequence alignment  based position specific gap penalty profiles  <cit>  and hmms  <cit> .
in general, hmms have been shown to be more sensitive than other profile based sequence-profile search methods  <cit> .
this is usually attributed to the ability of hmms to parameterize position specific gaps.
the use of dirichlet mixture priors in estimation of amino acid probabilities in a msa column could also be a reason for the success of hmms  <cit> .
the profile in general is a representation of conservation of amino acids at a given position in the msa  <cit> .
thus, it was believed that aligning two profiles will lead to better sensitivity and alignment accuracy as only the patterns in extent of conservation will be taken into consideration.
various methods have been developed for the alignment of profiles, which differ in the input profile type and also the scoring scheme used for the alignment of columns in the two profiles.
for instance, in the msa derived profile/pssm based profile-profile alignment methods, compass  <cit> , salign  <cit> , coach  <cit> , and others  <cit>  have been shown to give better sensitivity   <cit>  than simple sequence profile search methods such as psi-blast and hmmer <dig>    <cit> .
some of the recent developments using the psi-blast programs such as mulpssm  <cit>  and cascade blast  <cit>  have increased sensitivity of psi-blast methods by a few percentage points, but they may not be suited for homology based structural modeling since they depend on psi-blast for alignments, which has modest alignment accuracy in the midnight region  <cit> .
another recent development  <cit>  has increased the sequence-profile based sensitivity is hmmer <dig>  which has pushed sensitivity at the scop superfamily level to around 30% at 10% error rate.
two recent methods based on hmm - hmm alignment  <cit>  have shown that hmm based profile-profile alignment methods are more sensitive than pssm-pssm alignment methods, although at least one recent development in alignment of msa's  <cit>  seems to give better sensitivity than the hmm based methods at 50% error rate.
the hmm-hmm alignment in a general case is thought of as maximizing the probability of co-occurrence of amino acids along an alignment path between the emission states of the two hmms  <cit> .
this can be achieved by different combinations of pairwise state transitions as described in the profile comparer  method  <cit> .
the most important parameter which determines the sensitivity of a method is the column discrimination score, and both prc  <cit>  and hhsearch  <cit>  use a log sum of odds score for aligning hmm match states .
the alignment accuracy  is generally high  for both methods, even if the alignment length is usually quite low for hmms of distantly related domain families   <cit> .
the increase in both sensitivity and alignment accuracy is also in part due to the use of secondary structure information in the hhsearch alignment procedure and such an increase in remote homology detection rates by the use of secondary structure information has been reported earlier  <cit> .
use of secondary structure information alone  can lead to increase in false positive rate since there could be many proteins with similar sequence of helices and β-strands, but different 3-d topology.
the algorithm presented in this paper takes into account the residue conservation, secondary structure propensity and hydrophobicity of not only the columns being aligned, but also the adjacent columns, thus enabling it to differentiate hmms with similar secondary structure but different topology.
methods
the alignhush procedure has been developed to detect remote homologs more effectively than the currently existing tools without compromising on the alignment accuracy.
the objective of the current work was to develop a generally applicable algorithm without the use of explicit structural information to align two sequence-based hmms.
the sequence conservation information based profiles currently used for remote homology detection are inadequate for detection of very remote homologs since it is known that the sequence conservation is not seen in such cases of remote homology.
the structure is still seen to be conserved and hence use of structural information can lead to an improvement in the remote homology detection  <cit> .
the use of structural information may lead to many relationships being incorrectly found as significant matches in a search since there may not be a robust method to distinguish between related and unrelated sequence of secondary structures.
one way to distinguish such cases would be to find the packing of the secondary structures, but such information can be derived only from an analysis of the 3-d structure.
an approximation to the packing can be derived from the hydrophobicity pattern since it is known that the core of any protein is composed of hydrophobic residues.
such an approach has been shown to improve remote homology detection in sequence-profile alignments recently  <cit> .
thus, in the alignhush procedure a contribution to the score is derived from explicit hydrophobicity calculations which might enable the detection of remote homologues with finer detail.
another fact that has been exploited in the development of the alignhush procedure is the observation that conservation of residues occurs over a stretch of residues.
thus, adding the contribution from neighboring columns should enable better differentiation than by using information from a single column.
in case of a match between homologous patches, the score per column is enhanced but in unrelated patches, it is expected that the effect will be on average cancel out and the score for such patches will remain largely unchanged.
thus, use of neighbor information is expected to increase the separation between the scores for homologous matches and non-homologous matches which should enhance the difference in scores between the unrelated and related profiles.
in the next few sections, the incorporation of these ideas into the algorithm will be described in detail, followed by assessment based on the scop database.
datasets used
the dataset of hmms used in the analysis was obtained from the superfamily database  <cit>  which provides hmms and pssms of scop database.
scop  <dig>   <cit>  has been used throughout the analysis for parametrization.
out of the  <dig>  hmms present in the database corresponding to  <dig> scop families, one hmm has been selected randomly from each family.
this resulted in a total of  <dig> families which will henceforth be called the 'full scop  <dig>  dataset'.
the latest scop database  profiles from superfamily database were also used to determine the sensitivity and specificity.
the hhsearch compatible hmms for the superfamily database  were downloaded from hhsearch website ftp://toolkit.lmb.uni-muenchen.de/hhsearch/databases/.
from a total  <dig> profiles, extraction of single profile per family as performed for scop  <dig>  database lead to a dataset of  <dig> profiles which were used for comparison of the performance of three methods.
the true relationships in this work have been defined as two profiles corresponding to two scop families that belong to the same scop superfamily.
any two profiles belonging to scop families that are present in different classes have been deemed as unrelated .
the scop families belonging to two different folds in the same class are ignored.
in the next section, the procedure used to incorporate additional information to hmms is described.
format of hmms in alignhush procedure
the alignhush procedure uses information which is not present in the hmms generated by hmmer/sam packages.
hence, the input hmm was re-encoded to alignhush format and this is explained in detail in the subsequent sections.
gap penalties
hmmer <dig>  uses the plan <dig> architecture of hmms, which has been well documented .
the architecture results in three 'states' at each 'node' .
the states can be either m , i , or d  states.
each of the match/delete states correspond exactly to one column in the msa from which the hmm is derived.
multiple columns of msa can lead to a single insert state.
the match - match transition probability is close to  <dig> in most nodes.
where the probability of occurrence of inserts is high, the transition from a previous match state to the current insert state is also high.
this leads to a position-specific gap penalty which is one of the reasons why hmms are more accurate and sensitive than pssm-based methods which usually have uniform gap penalties.
the alignment between profiles is usually thought of as optimal match of two conservation patterns.
hence, the information on the probability of insert at a site is important but, the composition of insert states is not important.
thus, the insert emission line is discarded in the hmms for use in alignhush.
scores for emission of amino acids at each match state
the conservation of amino acids at a position in a msa is not sufficient to discriminate between related and unrelated patterns.
thus, to enhance the information content of a column in the msa, information on the hydrophobicity and predicted secondary structure scores are added to a column of the msa.
the hmmer suite of programs stores the match emission probabilities as log odds scores.
these scores are first converted into probabilities using the equations specified in hmmer userguide.
the probabilities are modified and stored as ratios of probability of amino acid to square root of background probability of that amino acid .
the explanation for this unusual step will be made clear when alignment procedure is explained.
since alignhush uses hydrophobicity and secondary structure at each position, these values/features are incorporated as emission probabilities set.
the hydrophobicity of each state is calculated as the product of probabilities of amino acids and the kyte-doolittle hydropathy values  <cit>  for the respective amino acids.
for the generation of secondary structure scores, secondary structures of each of the sequences in the msa have been predicted using psipred  <cit>  and the frequency of occurrence of each of the secondary structures in a column of the msa has been calculated.
since each column in the msa corresponds to either match state or an insert state, the probabilities of secondary structures occurring in a msa column can be transferred to either a match state or an insert state.
the frequencies for each secondary structural state, for every match position is stored and used for calculating the secondary structure based score.
alignment scheme
the alignment of profiles can either be global or local.
most profile-profile methods use local alignments since it is thought that only highly conserved amino acid motifs are conserved across families in a scop superfamily.
this view is appropriate when conservation of amino acids is used as a measure of relatedness.
but, it is known from structural classification databases that even if sequence patterns are not conserved, structure is conserved in such sequence fragments.
since the objective of the alignhush method is to recognize remote homologs it is imperative that the alignment length cover at least the structurally similar core of the two families in consideration.
this can be achieved if local alignments are constructed and parameters are optimized to allow for the local alignment to cover most of the homologous regions.
the viterbi algorithm has been used for local alignments of profile-profile matches, and the equations used closely follows the procedure of hhsearch  <cit>  and are reproduced in this manuscript.
the procedure is briefly described in the next few subsections.
the viterbi procedure breaks down the goal of aligning two profiles into a series of local optimizations.
initially as no alignment is made yet, the score is set to zero.
throughout this section, one of the two profiles is defined as p, which is a profile p with 'n' match states, and the other profile is represented by q  which is the profile q with 'm' match states.
p means the ith column of profile p and p means the ath amino acid in the ith column in profile p. the notation for state transition probabilities is derived on similar lines.
for example, for a state transition from match state at i-1th position in profile p to insert state at ith position in profile p is given as pi- <dig>
the alignment between two profiles is thought of as a pair-hmm following the suggestions made in hhsearch procedure  <cit> .
according to the hhsearch procedure, among the nine pair-hmm states, five states mm, mi, im, dg, and gd are sufficient for describing the profile-profile alignment, where m means 'match', d means delete, g means gap and i means insert in a profile.
the viterbi procedure starts by setting up five matrices for each of the pair-hmm states.
the total score till pi and qj are aligned is given by the variable sij  which is maximized in the viterbi procedure.
the equations for aligning the profiles closely follows the procedure suggested in hhsearch  <cit>  and are given in detail as equations 1a - 1e.
the difference between the hhsearch procedure and alignhush lies in the calculation of the score for alignment of two match positions, which is described below
in the alignhush procedure, the match between the columns consists of three scores, the hydrophobic score, the conservation score and the secondary structure score.
the conservation score is taken from the work of soding on hhsearch  <cit> , and is given as a log-sum of odds score  where ba refers to the background frequency of amino acid 'a'.
the conservation patterns are usually observed in short motifs, and not in isolation, and hence in alignhush procedure, the conservation score is taken over a window of a few columns.
thus the conservation score at position  is the sum of conservation scores over a window.
optimization using sensitivity as a criterion revealed that a window size of  <dig> gives the best results and this has been used throughout the analysis .
the hydrophobic score and the secondary structure score are likewise derived  and the window size for each score is determined separately.
in equation  <dig>  hx and hy refer to the hydrophobicity of a column at position x in first hmm and position y in second hmm.
similarly, the fs term is the frequency of occurrence of secondary structure 's' at position x in first hmm, and likewise for the second hmm .
the lss term in the equation  <dig>  is taken from a substitution table of secondary structural elements that was derived during the alignhush development.
the substitution table was derived by calculating the frequency of substitution of one secondary structure , with another in structural alignment of scop family sequences.
the three scores combined with their respective weightage given to each term gives the final column match score  that is used to calculate the column match score .
in addition to the weights given to the column match score parameters, an additional weightage term is used for gap penalties  which can be expected to give a score better than the score that is observed between two proteins.
if the number is very low, then the alignment score is very significant.
the e-value parameters for local ungapped alignments are well understood, but heuristic measures are used for the case of gapped local alignments.
the assessment of statistical significance in case of hmms is more complicated and several methods have been proposed based on whether the alignment has been generated using viterbi algorithm or the full forward algorithm  <cit> .
in order to decrease the bias due to the length of profile or composition of the profile, a per-family assessment of significance is better suited than an estimation of database specific parameters.
for assessment of statistical significance, the distribution followed by alignment scores of random profiles is required.
an approximation to alignment to random profiles can be obtained by aligning each query hmm to a large randomly selected profile database.
the scores obtained using the random database of profiles is used to fit the e-value parameters and these are used to report e-values in searches.
the definition of homologous and non-homologous families is subjective in several cases, with various classification schemes following different criteria for determining homology.
since the hmms are derived based on a scop based classification, homology as proposed in scop has been used.
thus, if two hmms belong to same scop superfamily, then they are considered homologous.
hmms belonging to the different scop classes were considered clearly non-homologous two hmms belonging to the same scop fold but different scop superfamilies, or two hmms belonging to different folds in the same class are ignored and not evaluated as either true positives or false positives.
the sensitivity is defined as tp/ and error rate as fp/, where tp stands for true positives, fn stands for false negatives and fp stands for false positives.
the comparison of sensitivity has been made with two other methods namely, prc  and hhsearch .
since prc accepts hmms in hmmer format, no conversion of hmm format was needed to search in the scop database of hmms provided by superfamily database.
the hmms  downloaded from the superfamily database were converted into the hhsearch format by using the 'hhmake' program and the predicted secondary structure was added using the hhsearch tool 'addpsipred.pl' in order to use secondary structure scores in hhsearch.
for the latest scop  database, the profiles corresponding to latest scop were downloaded from hhsearch web site in hhsearch compatible format.
the calibration of each of the hmms in the scop <dig>  and the latest scop database was done by searching in the calibration database provided with the respective hhsearch programs.
both prc and hhsearch were used with an e-value of  <dig> as default, and in case of hhsearch, an option to print at least  <dig> hits was used to estimate correctly the number of profiles found as false positives for a query.
assessment of alignment accuracy
the assessment of alignment accuracy especially for remotely related proteins is practically not feasible since the evolutionary history of any protein cannot be determined with high accuracy.
currently, there are no methods available which can provide the evolutionary path through which two proteins might have diverged from an ancestor protein.
the alignment is a statistical approximation to this path and its accuracy cannot as such be measured reliably.
in the absence of such 'gold standard' alignments, careful approximations must be made to derive a set of reference alignments against which the accuracy can be gauged.
at present, the structure based alignments are considered the 'gold standard' especially if manual curation has been made to refine small misaligned regions.
there are several such databases, out of which the balibase database  <cit>  was chosen since it provides alignments based on sequence identity cutoffs , which enables the assessment of alignment accuracy for remotely related proteins.
the balibase database provides manually curated structure-based alignments which have been pruned to ensure that the secondary structure elements align well, and care is also taken to ensure that functional residues are always aligned.
thus, the alignments present in the balibase database are considered as the 'gold standard' of alignments.
the comparison of alignments  generated using alignhush, prc and hhsearch with reference alignments in this database was done and the correctly aligned columns in each case were determined.
the procedure followed was to take the rv <dig>  rv <dig>  rv <dig> and rv <dig> subsets of the balibase  <dig>  database, which give alignment between proteins with less than 30% sequence identity.
there were  <dig> pairs of proteins , which have less than 30% sequence identity and which are also in different scop families in the same scop superfamily.
the sequences of the  <dig> proteins were aligned to its cognate scop family using the hmmalign program in the hmmer suite of programs.
this step might introduce inaccuracies, since the sequence-profile alignment is not 100% accurate.
the profile-profile alignment between two scop families is taken from each of the three methods, and a sequence - sequence alignment of remotely related proteins is generated by combining the two sequence-profile alignments with the profile-profile alignment.
for each test alignment , the region of overlap with the reference alignment was taken and the proportion of correctly aligned residues was calculated .
RESULTS
comparison of alignhush to other hmm profile alignment methods
the plots in figure 1a, show that when using the same query and database, alignhush  performs better than hhsearch and prc at all error rates.
the sensitivity at 5% and 10% error rate for a number of other profile-profile alignment methods is given in table  <dig>  the data in the figure 1a and the table  <dig> demonstrate that the sensitivity of alignhush, especially when all three scoring parameters are used, is slightly higher than all the currently existing methods.
for comparison, the sensitivity of alignhush at 10% error rate is 57%, whereas the sensitivity of hhsearch is 51% and that of prc is 54%.
the comparison of hhsearch and prc to other methods has been made in an independent assessment reported by sadrayev and grishin  <cit>   that reveals that hhsearch and prc perform better than other profile-profile alignment methods.
the definition of true positives in this work is deliberately restricted to families within a scop superfamily since such relationships can be considered evolutionarily related with high confidence.
scop families belonging to different folds could still have homology and hence an assessment of sensitivity and error-rate was performed with families within same fold considered as true positives and the results are similar to that observed in the case of scop superfamily analysis .
the sensitivity values at three levels of error rates for some of the most commonly used profile-profile search methods.
the source of each value is given in the last column.
note that the datasets used and the definitions used for true positives can differ from one source to another and hence the values are not comparable across different sources.
"#": the values given for procain are extracted from fig 2b of wang et al  <cit>  where the definition of true positives and false positives is similar to that used in the current work.
"§": value reported from soding,  <dig>  <cit> .
"*": the values reported with asterisk are for the comparison using the latest scop release.
for hhsearch the value reported is for the latest version of the program.
the use of neighbor information has lead to a significant increase in the sensitivity at all error rates as demonstrated by the plots in figure 1a, which shows an increase of around 20% when such information is used.
the use of secondary structure information has also lead to an increase as can be seen from comparison of alignhush with no secondary structure scoring  and alignhush  in figure 1a.
the use of hydrophobicity information also leads to a modest increase in sensitivity of alignhush procedure.
the major difference between alignhush and the other methods is the use of neighbour information and this parameter has lead to the increase seen in the sensitivity of alignhush.
the assessment of sensitivity of the three methods alignhush, hhsearch and prc was also done for the latest scop database version  <dig>  profiles .
the sensitivity of hhsearch in the latest scop database shows an increase of 2%, alignhush shows an increase of 1% and prc shows a decrease of 1% suggesting that the sensitivity values for each method could vary with changes in the underlying database.
the alignment accuracy of the three methods compared in this paper was calculated as two different values that give slightly different views on the alignment accuracy.
the first value is the 'developer score' which is the ratio between the number of correctly aligned columns  and the alignment region.
the second score is the 'modeler score' that gives the ratio of correctly aligned columns and the length of the reference alignment.
the two values can be thought of loosely as the specificity of the alignment and the sensitivity of correct alignment.
the two alignment accuracy values for each of the three methods tested  are given in figure 1b and 1c.
the average alignment accuracy for the three methods when the developer score is calculated is alignhush , prc  and hhsearch .
the developer score for hhsearch is higher than that of prc or alignhush, but this could be due to the short alignments generated by hhsearch .
the 'modeller score' on the other hand is a measure of how much of the alignable region has been correctly aligned by a method.
thus, the modeler score is of great interest from a user's perspective.
the values for the three methods are alignhush , prc  and hhsearch .
thus, the alignhush procedure compares favorably to the best performing methods as far as alignment accuracy is concerned.
the plots in figure 1d suggest that the length of alignment is usually as long as the length of the query profile in case of alignhush alignments which would be useful for functional and structural studies.
the values obtained for sensitivity at 10% error rate for the three methods studied, are useful as a guide for automated annotation efforts.
for detailed analysis of a few families, it is usually preferable to detect as many remote homologs as possible, which can then be pruned based on additional biological data .
for such efforts, the alignhush procedure can be more useful than hhsearch or prc since it provides better sensitivity at higher error rates .
moreover, from a user perspective, it is always advisable to use as many methods as available to increase the chances of recognizing meaningful remote homologues, since none of the methods recognize all the available remote homologues.
an analysis of the overlap between various methods can thus be indicative of the relative merits and demerits of the use of multiple methods.
such an analysis has been performed in this paper, where the pairwise remote homologs identified between scop families , are considered  at a low e-value threshold of  <dig> for each of the methods.
the most significant point that emerges from the figure is the high degree of overlap between hhsearch and prc results.
on the other hand, the number of hits found unique to alignhush procedure is very large and suggests that the scoring scheme of alignhush is sufficiently different from that of the other two methods.
thus, even though the sensitivity values considered for the whole dataset is marginally better, the biological value added due to the use of alignhush can be enormous as far as remote homology detection is concerned considering the fact that alignhush takes roughly only twice as long as hhsearch to search the same number of profiles .
this point is further illustrated in the next section where a few examples of remote relationships detected using alignhush are presented.
examples of remote relationships discovered using alignhush procedure
in the current analysis, relationships if identified between two scop families belonging to different scop folds  have been considered false positives.
but the structural similarity between proteins involved in many such relationships is striking and has also been mentioned in scop.
one such relationship is between the scop family dna-binding domain of mlu1-box binding protein mbp <dig>  and the family dna-binding protein mj <dig> .
the two families are from different classes but the method suggests similarity between the n-terminal part of mlu1-box binding protein  <dig> and the winged helix fold domain.
seven other families belonging to the winged helix superfamily are also found as hits with significant e-values strengthening the suggestion of homology between the n-terminal fragment of mbp <dig> protein and the winged helix superfamily.
interestingly, scop database mentions that the mbp <dig> family proteins have topological similarity to winged helix domains, but they are in different classes according to scop.
comparison of structures of regions of suggested similarity in two proteins  belonging to the two scop families, was done using dali  <cit>  and the structures are given in figure 3a .
the structures in the figure suggest that there is a significant structural similarity between the proteins.
alignhush, as it is basically sequence-based, suggests that the structural similarity might be due to common evolutionary ancestry.
another example  of structural similarity is between the families nitrilase  and dna double strand break repair nuclease family .
in this case too, scop mentions that the two families , might have topological similarities.
the nitrilase family protein from c.elegans  finds a homolog of known structure with z score of  <dig>  in the dali database.
the structural classification schemes do not provide indication of divergent evolution reliably at the scop fold level or above.
thus, if a method such as alignhush finds a hit to a profile that is present in a different scop fold or scop class, it cannot always be considered a genuine false positive.
the structural similarity and evolutionary signatures might still be present in such proteins, and since the alignment accuracy of the profile-profile methods is high, such cases must be treated manually .
the alignhush procedure can be useful for annotation of families of proteins with as yet unknown function .
the duf <dig> family is an example of a family of proteins with unknown function for which alignhush has enabled a putative functional annotation.
this family has been recognized as related to the d. <dig>   using alignhush with d. <dig> .
<dig> family .
there are multiple families in this superfamily and the active site residues participating in the catalytic function may not be conserved across different families in this scop superfamily.
for example, two proteins with pdb codes 1miv  and 7icq , are both classified into the nucleotidyltransferase superfamily but their active sites are not exactly superposable .
the aspartate residues that bind to mg2+ ion are conserved in the two proteins shown in figure 4a, but the catalytic arginine residue in 1miv is not conserved in the 7icq protein.
thus, the conservation of active site residues is not observed in this scop superfamily although it must be pointed out that each of the proteins in this superfamily binds to a nucleotide and mg2+, and hence the relationship of the duf <dig> family to this scop superfamily suggests that the duf  <dig> family proteins could participate in a nucleotidyl tranferase reaction, but the substrate and the mechanism of catalysis may be different than that in the existing scop families in this superfamily.
the alignment of the duf <dig> proteins with the top hit in the scop superfamily is given in figure 4b, and shows conservation of some residues.
the residues important for binding the mg2+ ion in the scop family are the two aspartate residues marked in the alignment which align with aspartate residues in the duf family and a glutamate residue which has been substituted with an aspartate or a glutamate in most proteins in the duf family and a serine residue in some proteins in the duf family sequences.
thus, it seems likely that the duf <dig> family adopts the same fold as the proteins in the nucleotidyltransferase superfamily and the partial conservation of some residues important for binding the catalytically active metal ion suggests that the proteins in this duf family could participate in a reaction similar to the nucleotidyltransferase reaction.
a more detailed mutagenesis experiments needs to be carried out to explore in detail the role of these proteins of this duf family.
discussion
the method developed has been demonstrated to have better sensitivity than currently existing methods such as hhsearch and prc leading to an increase of around 7% and 3% respectively when assessed using  <dig>  release of scop database.
the increase in sensitivity when the latest scop database is used is 4% and 6% with respect to hhsearch and prc respectively.
the alignment accuracy is also comparable or better than that of hhsearch and prc .
however, there are certain issues which point out that the method developed can in principle have even better performance than it has in its current form.
one of the major improvements can be in statistical evaluation.
currently there are no models analogous to that for local sequence alignments , for profile-profile alignments.
it is difficult to give a theoretical explanation for the gaps present in profile-profile alignments.
does it mean that all sequences in one profile have a tendency to have inserts at that position or does it mean that there are no homologous regions in the other profile?
these issues can be resolved if a detailed model of evolution which goes beyond family level of sequence similarity is generated.
a lot of work in recent years seems to be moving in this direction but a clear answer is yet to emerge.
thus, at present ad hoc methods like curve-fitting need to be done to interpret the alignment scores statistically.
some of the previous works in the area have used e-values derived from psi-blast like calculations  <cit>  and others have devised novel techniques to estimate statistical significance  <cit> .
although it has been demonstrated that the alignment accuracy of alignhush is quite high, it must be pointed out that the results must be carefully scrutinized.
the assessment using balibase reference alignments points out that the alignments bring the topologically equivalent secondary structures in register most of the time, and also align specific residues correctly 50% of the cases studied.
if the balibase alignments are a true representative of the distant relationships existing in the structural universe, then the alignment accuracy estimated in the current work can be extended to all the alignments produced by alignhush.
currently, there is no data to prove that there is a bias in the baiibase alignment datasets, and hence the alignment accuracy values can be taken as truly representative of all the alignments produced by alignhush.
other measures of alignment accuracy such as the gdt_ts score have been proposed and used in earlier work  <cit> .
the gdt_ts score was developed to evaluate the match between a modeled structure and a real structure, and thus cannot handle large inserts and deletions very accurately.
moreover, the structural alignment between divergent proteins cannot be automatically generated with high reliability.
hence the applicability of the gdt_ts scores to remote structural similarities is not proved beyond doubt and hence, these scores have not been used in the current work.
the sensitivity of the developed method is quite high but it could in theory be higher for purely sequence based profiles.
one of the major stumbling blocks in generation of profiles is the low number of sequences present in a family.
for example, close to 90% of families in scop are composed of two or three proteins.
in such a case, estimation of conservation becomes very difficult since almost every position might seem to be conserved.
it is made more difficult if the sequence identity between the few proteins in the family is quite high.
on the other hand, if sequence identity is very low on average in a family, then getting a high quality msa becomes very difficult  <cit> .
so, at present the quality of profiles generated for such divergent families in either scop or pfam databases might be low, and hence these families may not be performing very well in the current assessment.
this is also reflected in the fluctuations in the sensitivity values when using two different databases for all three methods.
CONCLUSIONS
a method for aligning profile hmms of protein sequences has been developed.
the algorithm takes into account three kinds of information from the sequence alignment in addition to conservation of amino acids at a position.
the additional information used are the predicted secondary structure information, hydrophobicity of the aligned residues, and the information present in neighboring columns.
assessment of sensitivity and error-rate in a large database of proteins of know structure , revealed that the sensitivity of our method is more than that of currently existing methods.
the alignments provided by alignhush have comparable accuracy or slightly better accuracy than currently existing methods.
the coverage of alignment on the profiles usually covers almost the entire length of the profile, and thus alignments generated by alignhush can be used for function/structure annotation.
a web-server incorporating the algorithm has been developed and is publicly available at http://crick.mbu.iisc.ernet.in/~alignhush/
competing interests
the authors declare that they have no competing interests.
authors' contributions
ns conceived of the study, and participated in its design and coordination and helped to draft the manuscript.
ok implemented the method and performed the analysis of the results obtained using the method.
both the authors read and approved the final manuscript.
supplementary material
additional file 1
sensitivity at the fold level.
sensitivity and error-rate values with true positives defined as scop families in the same fold.
click here for file
additional file 2
sensitivity using latest scop release.
sensitivity and error-rate values of hhsearch, prc and alignhush using the latest scop release.
click here for file
additional file 3
alignment of two structurally similar families.
sequence alignment of winged helix domain protein  and dna binding mlu <dig> box protein generated using alignhush.
click here for file
additional file 4
alignment of two structurally similar families.
sequence alignment of nit-fhit protein family and dna double strand break repair family generated using alignhush.
click here for file
acknowledgements
this research is supported by the mathematical biology initiative of department of science and technology , new delhi as well as by the department of biotechnology, new delhi.
o.k.
was supported by dst.

 alignment between sequences is useful and ubiquitous in bioinformatics. many of the advances made in the field of bioinformatics can be attributed to advances in alignment of sequences. the performance of homology-based structural modeling methods in casp over last several years is strongly correlated to the accuracy of the alignment between template and the target. alignments are also routinely generated for effective identification of remote homologues leading to function annotation of newly discovered proteins from genome sequence data. the explosion of sequence data from genome sequencing projects has exposed the limitation of current methods to recognize homologues in the twilight region and beyond. it was found quite early that profile methods, such as psi-blast can be more sensitive and accurate than single sequence-based methods. the starting point for deriving various kinds of profiles such as position specific scoring matrices and hidden markov models is an alignment of sequences of homologous proteins or protein domains. the commonly used profiles are the psi-blast generated pssms derived from query dependent alignments, multiple sequence alignment based position specific gap penalty profiles and hmms. in general, hmms have been shown to be more sensitive than other profile based sequence-profile search methods. this is usually attributed to the ability of hmms to parameterize position specific gaps. the use of dirichlet mixture priors in estimation of amino acid probabilities in a msa column could also be a reason for the success of hmms. the profile in general is a representation of conservation of amino acids at a given position in the msa. thus, it was believed that aligning two profiles will lead to better sensitivity and alignment accuracy as only the patterns in extent of conservation will be taken into consideration. various methods have been developed for the alignment of profiles, which differ in the input profile type and also the scoring scheme used for the alignment of columns in the two profiles. for instance, in the msa derived profile/pssm based profile-profile alignment methods, compass, salign, coach, and others have been shown to give better sensitivity than simple sequence profile search methods such as psi-blast and hmmer. some of the recent developments using the psi-blast programs such as mulpssm and cascade blast have increased sensitivity of psi-blast methods by a few percentage points, but they may not be suited for homology based structural modeling since they depend on psi-blast for alignments, which has modest alignment accuracy in the midnight region. another recent development has increased the sequence-profile based sensitivity is hmmer which has pushed sensitivity at the scop superfamily level to around 30% at 10% error rate. two recent methods based on hmm - hmm alignment have shown that hmm based profile-profile alignment methods are more sensitive than pssm-pssm alignment methods, although at least one recent development in alignment of msa's seems to give better sensitivity than the hmm based methods at 50% error rate. the hmm-hmm alignment in a general case is thought of as maximizing the probability of co-occurrence of amino acids along an alignment path between the emission states of the two hmms. this can be achieved by different combinations of pairwise state transitions as described in the profile comparer method. the most important parameter which determines the sensitivity of a method is the column discrimination score, and both prc and hhsearch use a log sum of odds score for aligning hmm match states. the alignment accuracy is generally high for both methods, even if the alignment length is usually quite low for hmms of distantly related domain families. the increase in both sensitivity and alignment accuracy is also in part due to the use of secondary structure information in the hhsearch alignment procedure and such an increase in remote homology detection rates by the use of secondary structure information has been reported earlier. use of secondary structure information alone can lead to increase in false positive rate since there could be many proteins with similar sequence of helices and β-strands, but different 3-d topology. the algorithm presented in this paper takes into account the residue conservation, secondary structure propensity and hydrophobicity of not only the columns being aligned, but also the adjacent columns, thus enabling it to differentiate hmms with similar secondary structure but different topology. methods the alignhush procedure has been developed to detect remote homologs more effectively than the currently existing tools without compromising on the alignment accuracy. the objective of the current work was to develop a generally applicable algorithm without the use of explicit structural information to align two sequence-based hmms. the sequence conservation information based profiles currently used for remote homology detection are inadequate for detection of very remote homologs since it is known that the sequence conservation is not seen in such cases of remote homology. the structure is still seen to be conserved and hence use of structural information can lead to an improvement in the remote homology detection. the use of structural information may lead to many relationships being incorrectly found as significant matches in a search since there may not be a robust method to distinguish between related and unrelated sequence of secondary structures. one way to distinguish such cases would be to find the packing of the secondary structures, but such information can be derived only from an analysis of the 3-d structure. an approximation to the packing can be derived from the hydrophobicity pattern since it is known that the core of any protein is composed of hydrophobic residues. such an approach has been shown to improve remote homology detection in sequence-profile alignments recently. thus, in the alignhush procedure a contribution to the score is derived from explicit hydrophobicity calculations which might enable the detection of remote homologues with finer detail. another fact that has been exploited in the development of the alignhush procedure is the observation that conservation of residues occurs over a stretch of residues. thus, adding the contribution from neighboring columns should enable better differentiation than by using information from a single column. in case of a match between homologous patches, the score per column is enhanced but in unrelated patches, it is expected that the effect will be on average cancel out and the score for such patches will remain largely unchanged. thus, use of neighbor information is expected to increase the separation between the scores for homologous matches and non-homologous matches which should enhance the difference in scores between the unrelated and related profiles. in the next few sections, the incorporation of these ideas into the algorithm will be described in detail, followed by assessment based on the scop database. datasets used the dataset of hmms used in the analysis was obtained from the superfamily database which provides hmms and pssms of scop database. scop has been used throughout the analysis for parametrization. out of the hmms present in the database corresponding to scop families, one hmm has been selected randomly from each family. this resulted in a total of families which will henceforth be called the'full scop dataset'. the latest scop database profiles from superfamily database were also used to determine the sensitivity and specificity. the hhsearch compatible hmms for the superfamily database were downloaded from hhsearch website ftp://toolkit.lmb.uni-muenchen.de/hhsearch/databases/. from a total profiles, extraction of single profile per family as performed for scop database lead to a dataset of profiles which were used for comparison of the performance of three methods. the true relationships in this work have been defined as two profiles corresponding to two scop families that belong to the same scop superfamily. any two profiles belonging to scop families that are present in different classes have been deemed as unrelated. the scop families belonging to two different folds in the same class are ignored. in the next section, the procedure used to incorporate additional information to hmms is described. format of hmms in alignhush procedure the alignhush procedure uses information which is not present in the hmms generated by hmmer/sam packages. hence, the input hmm was re-encoded to alignhush format and this is explained in detail in the subsequent sections. gap penalties hmmer uses the plan architecture of hmms, which has been well documented. the architecture results in three'states' at each'node'. the states can be either m, i, or d states. each of the match/delete states correspond exactly to one column in the msa from which the hmm is derived. multiple columns of msa can lead to a single insert state. the match - match transition probability is close to in most nodes. where the probability of occurrence of inserts is high, the transition from a previous match state to the current insert state is also high. this leads to a position-specific gap penalty which is one of the reasons why hmms are more accurate and sensitive than pssm-based methods which usually have uniform gap penalties. the alignment between profiles is usually thought of as optimal match of two conservation patterns. hence, the information on the probability of insert at a site is important but, the composition of insert states is not important. thus, the insert emission line is discarded in the hmms for use in alignhush. scores for emission of amino acids at each match state the conservation of amino acids at a position in a msa is not sufficient to discriminate between related and unrelated patterns. thus, to enhance the information content of a column in the msa, information on the hydrophobicity and predicted secondary structure scores are added to a column of the msa. the hmmer suite of programs stores the match emission probabilities as log odds scores. these scores are first converted into probabilities using the equations specified in hmmer userguide. the probabilities are modified and stored as ratios of probability of amino acid to square root of background probability of that amino acid. the explanation for this unusual step will be made clear when alignment procedure is explained. since alignhush uses hydrophobicity and secondary structure at each position, these values/features are incorporated as emission probabilities set. the hydrophobicity of each state is calculated as the product of probabilities of amino acids and the kyte-doolittle hydropathy values for the respective amino acids. for the generation of secondary structure scores, secondary structures of each of the sequences in the msa have been predicted using psipred and the frequency of occurrence of each of the secondary structures in a column of the msa has been calculated. since each column in the msa corresponds to either match state or an insert state, the probabilities of secondary structures occurring in a msa column can be transferred to either a match state or an insert state. the frequencies for each secondary structural state, for every match position is stored and used for calculating the secondary structure based score. alignment scheme the alignment of profiles can either be global or local. most profile-profile methods use local alignments since it is thought that only highly conserved amino acid motifs are conserved across families in a scop superfamily. this view is appropriate when conservation of amino acids is used as a measure of relatedness. but, it is known from structural classification databases that even if sequence patterns are not conserved, structure is conserved in such sequence fragments. since the objective of the alignhush method is to recognize remote homologs it is imperative that the alignment length cover at least the structurally similar core of the two families in consideration. this can be achieved if local alignments are constructed and parameters are optimized to allow for the local alignment to cover most of the homologous regions. the viterbi algorithm has been used for local alignments of profile-profile matches, and the equations used closely follows the procedure of hhsearch and are reproduced in this manuscript. the procedure is briefly described in the next few subsections. the viterbi procedure breaks down the goal of aligning two profiles into a series of local optimizations. initially as no alignment is made yet, the score is set to zero. throughout this section, one of the two profiles is defined as p, which is a profile p with'n' match states, and the other profile is represented by q which is the profile q with'm' match states. p means the ith column of profile p and p means the ath amino acid in the ith column in profile p. the notation for state transition probabilities is derived on similar lines. for example, for a state transition from match state at i-1th position in profile p to insert state at ith position in profile p is given as pi- the alignment between two profiles is thought of as a pair-hmm following the suggestions made in hhsearch procedure. according to the hhsearch procedure, among the nine pair-hmm states, five states mm, mi, im, dg, and gd are sufficient for describing the profile-profile alignment, where m means'match', d means delete, g means gap and i means insert in a profile. the viterbi procedure starts by setting up five matrices for each of the pair-hmm states. the total score till pi and qj are aligned is given by the variable sij which is maximized in the viterbi procedure. the equations for aligning the profiles closely follows the procedure suggested in hhsearch and are given in detail as equations 1a - 1e. the difference between the hhsearch procedure and alignhush lies in the calculation of the score for alignment of two match positions, which is described below in the alignhush procedure, the match between the columns consists of three scores, the hydrophobic score, the conservation score and the secondary structure score. the conservation score is taken from the work of soding on hhsearch, and is given as a log-sum of odds score where ba refers to the background frequency of amino acid'a'. the conservation patterns are usually observed in short motifs, and not in isolation, and hence in alignhush procedure, the conservation score is taken over a window of a few columns. thus the conservation score at position is the sum of conservation scores over a window. optimization using sensitivity as a criterion revealed that a window size of gives the best results and this has been used throughout the analysis. the hydrophobic score and the secondary structure score are likewise derived and the window size for each score is determined separately. in equation hx and hy refer to the hydrophobicity of a column at position x in first hmm and position y in second hmm. similarly, the fs term is the frequency of occurrence of secondary structure's' at position x in first hmm, and likewise for the second hmm. the lss term in the equation is taken from a substitution table of secondary structural elements that was derived during the alignhush development. the substitution table was derived by calculating the frequency of substitution of one secondary structure, with another in structural alignment of scop family sequences. the three scores combined with their respective weightage given to each term gives the final column match score that is used to calculate the column match score. in addition to the weights given to the column match score parameters, an additional weightage term is used for gap penalties which can be expected to give a score better than the score that is observed between two proteins. if the number is very low, then the alignment score is very significant. the e-value parameters for local ungapped alignments are well understood, but heuristic measures are used for the case of gapped local alignments. the assessment of statistical significance in case of hmms is more complicated and several methods have been proposed based on whether the alignment has been generated using viterbi algorithm or the full forward algorithm. in order to decrease the bias due to the length of profile or composition of the profile, a per-family assessment of significance is better suited than an estimation of database specific parameters. for assessment of statistical significance, the distribution followed by alignment scores of random profiles is required. an approximation to alignment to random profiles can be obtained by aligning each query hmm to a large randomly selected profile database. the scores obtained using the random database of profiles is used to fit the e-value parameters and these are used to report e-values in searches. the definition of homologous and non-homologous families is subjective in several cases, with various classification schemes following different criteria for determining homology. since the hmms are derived based on a scop based classification, homology as proposed in scop has been used. thus, if two hmms belong to same scop superfamily, then they are considered homologous. hmms belonging to the different scop classes were considered clearly non-homologous two hmms belonging to the same scop fold but different scop superfamilies, or two hmms belonging to different folds in the same class are ignored and not evaluated as either true positives or false positives. the sensitivity is defined as tp/ and error rate as fp/, where tp stands for true positives, fn stands for false negatives and fp stands for false positives. the comparison of sensitivity has been made with two other methods namely, prc and hhsearch. since prc accepts hmms in hmmer format, no conversion of hmm format was needed to search in the scop database of hmms provided by superfamily database. the hmms downloaded from the superfamily database were converted into the hhsearch format by using the'hhmake' program and the predicted secondary structure was added using the hhsearch tool'addpsipred.pl' in order to use secondary structure scores in hhsearch. for the latest scop database, the profiles corresponding to latest scop were downloaded from hhsearch web site in hhsearch compatible format. the calibration of each of the hmms in the scop and the latest scop database was done by searching in the calibration database provided with the respective hhsearch programs. both prc and hhsearch were used with an e-value of as default, and in case of hhsearch, an option to print at least hits was used to estimate correctly the number of profiles found as false positives for a query. assessment of alignment accuracy the assessment of alignment accuracy especially for remotely related proteins is practically not feasible since the evolutionary history of any protein cannot be determined with high accuracy. currently, there are no methods available which can provide the evolutionary path through which two proteins might have diverged from an ancestor protein. the alignment is a statistical approximation to this path and its accuracy cannot as such be measured reliably. in the absence of such'gold standard' alignments, careful approximations must be made to derive a set of reference alignments against which the accuracy can be gauged. at present, the structure based alignments are considered the'gold standard' especially if manual curation has been made to refine small misaligned regions. there are several such databases, out of which the balibase database was chosen since it provides alignments based on sequence identity cutoffs, which enables the assessment of alignment accuracy for remotely related proteins. the balibase database provides manually curated structure-based alignments which have been pruned to ensure that the secondary structure elements align well, and care is also taken to ensure that functional residues are always aligned. thus, the alignments present in the balibase database are considered as the'gold standard' of alignments. the comparison of alignments generated using alignhush, prc and hhsearch with reference alignments in this database was done and the correctly aligned columns in each case were determined. the procedure followed was to take the rv rv rv and rv subsets of the balibase database, which give alignment between proteins with less than 30% sequence identity. there were pairs of proteins, which have less than 30% sequence identity and which are also in different scop families in the same scop superfamily. the sequences of the proteins were aligned to its cognate scop family using the hmmalign program in the hmmer suite of programs. this step might introduce inaccuracies, since the sequence-profile alignment is not 100% accurate. the profile-profile alignment between two scop families is taken from each of the three methods, and a sequence - sequence alignment of remotely related proteins is generated by combining the two sequence-profile alignments with the profile-profile alignment. for each test alignment, the region of overlap with the reference alignment was taken and the proportion of correctly aligned residues was calculated.  comparison of alignhush to other hmm profile alignment methods the plots in figure 1a, show that when using the same query and database, alignhush performs better than hhsearch and prc at all error rates. the sensitivity at 5% and 10% error rate for a number of other profile-profile alignment methods is given in table the data in the figure 1a and the table demonstrate that the sensitivity of alignhush, especially when all three scoring parameters are used, is slightly higher than all the currently existing methods. for comparison, the sensitivity of alignhush at 10% error rate is 57%, whereas the sensitivity of hhsearch is 51% and that of prc is 54%. the comparison of hhsearch and prc to other methods has been made in an independent assessment reported by sadrayev and grishin that reveals that hhsearch and prc perform better than other profile-profile alignment methods. the definition of true positives in this work is deliberately restricted to families within a scop superfamily since such relationships can be considered evolutionarily related with high confidence. scop families belonging to different folds could still have homology and hence an assessment of sensitivity and error-rate was performed with families within same fold considered as true positives and the results are similar to that observed in the case of scop superfamily analysis. the sensitivity values at three levels of error rates for some of the most commonly used profile-profile search methods. the source of each value is given in the last column. note that the datasets used and the definitions used for true positives can differ from one source to another and hence the values are not comparable across different sources. "#": the values given for procain are extracted from fig 2b of wang et al where the definition of true positives and false positives is similar to that used in the current work. "§": value reported from soding,. "*": the values reported with asterisk are for the comparison using the latest scop release. for hhsearch the value reported is for the latest version of the program. the use of neighbor information has lead to a significant increase in the sensitivity at all error rates as demonstrated by the plots in figure 1a, which shows an increase of around 20% when such information is used. the use of secondary structure information has also lead to an increase as can be seen from comparison of alignhush with no secondary structure scoring and alignhush in figure 1a. the use of hydrophobicity information also leads to a modest increase in sensitivity of alignhush procedure. the major difference between alignhush and the other methods is the use of neighbour information and this parameter has lead to the increase seen in the sensitivity of alignhush. the assessment of sensitivity of the three methods alignhush, hhsearch and prc was also done for the latest scop database version profiles. the sensitivity of hhsearch in the latest scop database shows an increase of 2%, alignhush shows an increase of 1% and prc shows a decrease of 1% suggesting that the sensitivity values for each method could vary with changes in the underlying database. the alignment accuracy of the three methods compared in this paper was calculated as two different values that give slightly different views on the alignment accuracy. the first value is the'developer score' which is the ratio between the number of correctly aligned columns and the alignment region. the second score is the'modeler score' that gives the ratio of correctly aligned columns and the length of the reference alignment. the two values can be thought of loosely as the specificity of the alignment and the sensitivity of correct alignment. the two alignment accuracy values for each of the three methods tested are given in figure 1b and 1c. the average alignment accuracy for the three methods when the developer score is calculated is alignhush, prc and hhsearch. the developer score for hhsearch is higher than that of prc or alignhush, but this could be due to the short alignments generated by hhsearch. the'modeller score' on the other hand is a measure of how much of the alignable region has been correctly aligned by a method. thus, the modeler score is of great interest from a user's perspective. the values for the three methods are alignhush, prc and hhsearch. thus, the alignhush procedure compares favorably to the best performing methods as far as alignment accuracy is concerned. the plots in figure 1d suggest that the length of alignment is usually as long as the length of the query profile in case of alignhush alignments which would be useful for functional and structural studies. the values obtained for sensitivity at 10% error rate for the three methods studied, are useful as a guide for automated annotation efforts. for detailed analysis of a few families, it is usually preferable to detect as many remote homologs as possible, which can then be pruned based on additional biological data. for such efforts, the alignhush procedure can be more useful than hhsearch or prc since it provides better sensitivity at higher error rates. moreover, from a user perspective, it is always advisable to use as many methods as available to increase the chances of recognizing meaningful remote homologues, since none of the methods recognize all the available remote homologues. an analysis of the overlap between various methods can thus be indicative of the relative merits and demerits of the use of multiple methods. such an analysis has been performed in this paper, where the pairwise remote homologs identified between scop families, are considered at a low e-value threshold of for each of the methods. the most significant point that emerges from the figure is the high degree of overlap between hhsearch and prc results. on the other hand, the number of hits found unique to alignhush procedure is very large and suggests that the scoring scheme of alignhush is sufficiently different from that of the other two methods. thus, even though the sensitivity values considered for the whole dataset is marginally better, the biological value added due to the use of alignhush can be enormous as far as remote homology detection is concerned considering the fact that alignhush takes roughly only twice as long as hhsearch to search the same number of profiles. this point is further illustrated in the next section where a few examples of remote relationships detected using alignhush are presented. examples of remote relationships discovered using alignhush procedure in the current analysis, relationships if identified between two scop families belonging to different scop folds have been considered false positives. but the structural similarity between proteins involved in many such relationships is striking and has also been mentioned in scop. one such relationship is between the scop family dna-binding domain of mlu1-box binding protein mbp and the family dna-binding protein mj. the two families are from different classes but the method suggests similarity between the n-terminal part of mlu1-box binding protein and the winged helix fold domain. seven other families belonging to the winged helix superfamily are also found as hits with significant e-values strengthening the suggestion of homology between the n-terminal fragment of mbp protein and the winged helix superfamily. interestingly, scop database mentions that the mbp family proteins have topological similarity to winged helix domains, but they are in different classes according to scop. comparison of structures of regions of suggested similarity in two proteins belonging to the two scop families, was done using dali and the structures are given in figure 3a. the structures in the figure suggest that there is a significant structural similarity between the proteins. alignhush, as it is basically sequence-based, suggests that the structural similarity might be due to common evolutionary ancestry. another example of structural similarity is between the families nitrilase and dna double strand break repair nuclease family. in this case too, scop mentions that the two families, might have topological similarities. the nitrilase family protein from c.elegans finds a homolog of known structure with z score of in the dali database. the structural classification schemes do not provide indication of divergent evolution reliably at the scop fold level or above. thus, if a method such as alignhush finds a hit to a profile that is present in a different scop fold or scop class, it cannot always be considered a genuine false positive. the structural similarity and evolutionary signatures might still be present in such proteins, and since the alignment accuracy of the profile-profile methods is high, such cases must be treated manually. the alignhush procedure can be useful for annotation of families of proteins with as yet unknown function. the duf family is an example of a family of proteins with unknown function for which alignhush has enabled a putative functional annotation. this family has been recognized as related to the d. using alignhush with d.. family. there are multiple families in this superfamily and the active site residues participating in the catalytic function may not be conserved across different families in this scop superfamily. for example, two proteins with pdb codes 1miv and 7icq, are both classified into the nucleotidyltransferase superfamily but their active sites are not exactly superposable. the aspartate residues that bind to mg2+ ion are conserved in the two proteins shown in figure 4a, but the catalytic arginine residue in 1miv is not conserved in the 7icq protein. thus, the conservation of active site residues is not observed in this scop superfamily although it must be pointed out that each of the proteins in this superfamily binds to a nucleotide and mg2+, and hence the relationship of the duf family to this scop superfamily suggests that the duf family proteins could participate in a nucleotidyl tranferase reaction, but the substrate and the mechanism of catalysis may be different than that in the existing scop families in this superfamily. the alignment of the duf proteins with the top hit in the scop superfamily is given in figure 4b, and shows conservation of some residues. the residues important for binding the mg2+ ion in the scop family are the two aspartate residues marked in the alignment which align with aspartate residues in the duf family and a glutamate residue which has been substituted with an aspartate or a glutamate in most proteins in the duf family and a serine residue in some proteins in the duf family sequences. thus, it seems likely that the duf family adopts the same fold as the proteins in the nucleotidyltransferase superfamily and the partial conservation of some residues important for binding the catalytically active metal ion suggests that the proteins in this duf family could participate in a reaction similar to the nucleotidyltransferase reaction. a more detailed mutagenesis experiments needs to be carried out to explore in detail the role of these proteins of this duf family. discussion the method developed has been demonstrated to have better sensitivity than currently existing methods such as hhsearch and prc leading to an increase of around 7% and 3% respectively when assessed using release of scop database. the increase in sensitivity when the latest scop database is used is 4% and 6% with respect to hhsearch and prc respectively. the alignment accuracy is also comparable or better than that of hhsearch and prc. however, there are certain issues which point out that the method developed can in principle have even better performance than it has in its current form. one of the major improvements can be in statistical evaluation. currently there are no models analogous to that for local sequence alignments, for profile-profile alignments. it is difficult to give a theoretical explanation for the gaps present in profile-profile alignments. does it mean that all sequences in one profile have a tendency to have inserts at that position or does it mean that there are no homologous regions in the other profile? these issues can be resolved if a detailed model of evolution which goes beyond family level of sequence similarity is generated. a lot of work in recent years seems to be moving in this direction but a clear answer is yet to emerge. thus, at present ad hoc methods like curve-fitting need to be done to interpret the alignment scores statistically. some of the previous works in the area have used e-values derived from psi-blast like calculations and others have devised novel techniques to estimate statistical significance. although it has been demonstrated that the alignment accuracy of alignhush is quite high, it must be pointed out that the results must be carefully scrutinized. the assessment using balibase reference alignments points out that the alignments bring the topologically equivalent secondary structures in register most of the time, and also align specific residues correctly 50% of the cases studied. if the balibase alignments are a true representative of the distant relationships existing in the structural universe, then the alignment accuracy estimated in the current work can be extended to all the alignments produced by alignhush. currently, there is no data to prove that there is a bias in the baiibase alignment datasets, and hence the alignment accuracy values can be taken as truly representative of all the alignments produced by alignhush. other measures of alignment accuracy such as the gdt_ts score have been proposed and used in earlier work. the gdt_ts score was developed to evaluate the match between a modeled structure and a real structure, and thus cannot handle large inserts and deletions very accurately. moreover, the structural alignment between divergent proteins cannot be automatically generated with high reliability. hence the applicability of the gdt_ts scores to remote structural similarities is not proved beyond doubt and hence, these scores have not been used in the current work. the sensitivity of the developed method is quite high but it could in theory be higher for purely sequence based profiles. one of the major stumbling blocks in generation of profiles is the low number of sequences present in a family. for example, close to 90% of families in scop are composed of two or three proteins. in such a case, estimation of conservation becomes very difficult since almost every position might seem to be conserved. it is made more difficult if the sequence identity between the few proteins in the family is quite high. on the other hand, if sequence identity is very low on average in a family, then getting a high quality msa becomes very difficult. so, at present the quality of profiles generated for such divergent families in either scop or pfam databases might be low, and hence these families may not be performing very well in the current assessment. this is also reflected in the fluctuations in the sensitivity values when using two different databases for all three methods.  a method for aligning profile hmms of protein sequences has been developed. the algorithm takes into account three kinds of information from the sequence alignment in addition to conservation of amino acids at a position. the additional information used are the predicted secondary structure information, hydrophobicity of the aligned residues, and the information present in neighboring columns. assessment of sensitivity and error-rate in a large database of proteins of know structure, revealed that the sensitivity of our method is more than that of currently existing methods. the alignments provided by alignhush have comparable accuracy or slightly better accuracy than currently existing methods. the coverage of alignment on the profiles usually covers almost the entire length of the profile, and thus alignments generated by alignhush can be used for function/structure annotation. a web-server incorporating the algorithm has been developed and is publicly available at http://crick.mbu.iisc.ernet.in/~alignhush/ competing interests the authors declare that they have no competing interests. authors' contributions ns conceived of the study, and participated in its design and coordination and helped to draft the manuscript. ok implemented the method and performed the analysis of the results obtained using the method. both the authors read and approved the final manuscript. supplementary material additional file 1 sensitivity at the fold level. sensitivity and error-rate values with true positives defined as scop families in the same fold. click here for file additional file 2 sensitivity using latest scop release. sensitivity and error-rate values of hhsearch, prc and alignhush using the latest scop release. click here for file additional file 3 alignment of two structurally similar families. sequence alignment of winged helix domain protein and dna binding mlu box protein generated using alignhush. click here for file additional file 4 alignment of two structurally similar families. sequence alignment of nit-fhit protein family and dna double strand break repair family generated using alignhush. click here for file acknowledgements this research is supported by the mathematical biology initiative of department of science and technology, new delhi as well as by the department of biotechnology, new delhi. o.k. was supported by dst.
sensitive remote homology detection and accurate alignments especially in the midnight zone of sequence similarity are needed for better function annotation and structural modeling of proteins. the effect of using adjoining column information has also been investigated and is found to increase the sensitivity of hmm-hmm alignments and remote homology detection. an algorithm, alignhush for hmm-hmm alignment has been developed which is capable of recognizing distantly related domain families the method uses structural information, in the form of predicted secondary structure probabilities, and hydrophobicity of amino acids to align hmms of two sets of aligned sequences. the alignment length and the alignment quality are found to be appropriate for homology modeling and function annotation. the proposed method could effectively aid obtaining clues to functions of proteins of yet unknown function. alignhush performs better than the best hmm-hmm alignment methods and is observed to be even more sensitive at higher error rates. the alignment accuracy is found to be comparable to existing methods for profile-profile alignments. a web-server incorporating the alignhush method is available at http://crick.mbu.iisc.ernet.in/~alignhush/
 sensitive remote homology detection and accurate alignments especially in the midnight zone of sequence similarity are needed for better function annotation and structural modeling of proteins. an algorithm, alignhush for hmm-hmm alignment has been developed which is capable of recognizing distantly related domain families the method uses structural information, in the form of predicted secondary structure probabilities, and hydrophobicity of amino acids to align hmms of two sets of aligned sequences. the effect of using adjoining column information has also been investigated and is found to increase the sensitivity of hmm-hmm alignments and remote homology detection.  we have assessed the performance of alignhush using known evolutionary relationships available in scop. alignhush performs better than the best hmm-hmm alignment methods and is observed to be even more sensitive at higher error rates. accuracy of the alignments obtained using alignhush has been assessed using the structure-based alignments available in balibase. the alignment length and the alignment quality are found to be appropriate for homology modeling and function annotation. the alignment accuracy is found to be comparable to existing methods for profile-profile alignments.  a new method to align hmms has been developed and is shown to have better sensitivity at error rates of 10% and above when compared to other available programs. the proposed method could effectively aid obtaining clues to functions of proteins of yet unknown function. a web-server incorporating the alignhush method is available at http://crick.mbu.iisc.ernet.in/~alignhush/ 