BACKGROUND
hidden markov models  are probabilistic models  <cit> , commonly used during the last years for applications in bioinformatics  <cit> .
these tasks include gene finding  <cit> , multiple alignments  <cit>  and database searches  <cit> , prediction of signal peptides  <cit> , prediction of protein secondary structure  <cit> , prediction of transmembrane protein topology  <cit> , as well as joint prediction of transmembrane helices and signal peptides  <cit> .
especially in the case of transmembrane proteins, hmms have been found to perform significantly better compared to other sophisticated machine-learning techniques such as neural networks  or support vector machines .
this is the case irrespective to which class of transmembrane proteins we refer to, since it has been shown that the best currently available predictors for alpha-helical membrane proteins  <cit>  as well as for beta-barrel outer membrane proteins  <cit> , are methods based on hmms.
experimental techniques are routinely used to partially uncover the transmembrane topology of membrane proteins .
such methods include the use of various reporter fusions  <cit> , chemical labelling  <cit> , epitope tagging  <cit> , antibodies  <cit>  and cysteine scanning mutagenesis  <cit> .
the gene fusion approach seems to be the most effective method and the reporters used, include alkaline phosphatase , beta-galactosidase   <cit> , beta-lactamase   <cit>  as well as various fluorescent proteins  <cit> .
with the development of fast and reliable methods to utilise gene fusion technology in order to determine the location of a protein's c-terminus, it has been shown that incorporating topological information into the prediction methods improves largely the performance of even the top-scoring methods, making easy to screen newly sequenced genomes  <cit> .
this has been demonstrated, using experimentally derived information regarding e. coli  <cit>  and s. cerevisiae  <cit>  protein datasets.
more recently, a global topological analysis of the e. coli inner membrane proteins was performed, providing reliable models for more than  <dig> membrane proteins  <cit> .
among the top-scoring hmm predictors currently available, hmmtop  <cit>  provides the user the option to incorporate such information.
tmhmm is currently not supporting such an option in its standard web-server, and the users have to turn the tmhmmfix server  <cit>  or to the joint prediction of transmembrane helices and signal peptides offered by phobius  <cit> .
lately, bernsel and von heijne  <cit> , used a similar idea that consisted of treating the occurrence  of soluble protein domains with known localisation, as experimentally determined topology.
this way, they implemented a modified version of the hmm described by viklund and elofsson  <cit> , in order to apply constrained predictions.
however, even in this work the algorithmic details were not presented nor the prediction method became available to the public.
moreover, no effort has been made in the literature in order to completely and accurately describe the mathematical details of the algorithms that allow the arbitrary incorporation of such prior knowledge, in a way that prevents hmms from loosing their probabilistic interpretation.
the nature of hmms, allows some brute conditioning; for instance, setting transition probabilities from a particular state to the end state to zero will allow the fixation of the c-terminus in the desired topology.
similarly, having knowledge of the presence of a signal peptide, after removing it, one may force the hmm to consider as allowed transitions from the begin state only those with direction to the extracellular loop states of the model.
unfortunately, the probabilistic interpretation of these results will be lost.
thus, it would be useful to have a method that enables us to arbitrarily fix any part of the sequence in a specified topology, while at the same time retaining the probabilistic interpretation of the algorithms used for decoding the hmm.
in this work, we present some trivial modifications to the standard algorithms used in hmms, namely the forward and backward algorithms  <cit> .
these modifications are very similar with those used on training hmms with labelled sequences  <cit> , but here they are considered in the context of models' decoding.
we also show, that the likelihoods derived when applying these modified algorithms, can be expressed as posterior probabilities of the prior experimental information given the sequences and the model parameters, thus retaining this way the probabilistic interpretation of the results.
we also introduce similar trivial modifications to all known algorithms used for decoding an hmm.
in particular, we present modified versions of the standard viterbi algorithm  <cit> , which finds the most probable path of states, of the 1-best algorithm  <cit> , which tries to find the optimal labelling of a sequence, giving always a labelling with equal or greater probability compared to the viterbi decoding.
similar modifications follow for the "a-posteriori" decoding method  <cit> , which in many applications, and under certain conditions, provides better prediction  <cit> , as well as to the newly developed posterior-viterbi method  <cit>  and the optimal accuracy posterior decoding method  <cit> , that both combine elements of viterbi and posterior decoding.
finally, we present an application of these algorithms, training a hmm to predict the transmembrane segments of alpha-helical membrane proteins.
the model is trained in a discriminative manner with the conditional maximum likelihood  criterion, using a dataset of proteins with structures known at atomic resolution, and it is shown  to compare well against the top-scoring algorithms currently available.
the method, hmm-tm, is freely available for academic users at , where the user may choose any of the four above mentioned algorithms for decoding, an option not currently available in any other prediction method.
RESULTS
in table  <dig>  we list the results obtained on the training set with our method , both on a self-consistency test and on a 9-fold cross-validation procedure.
in the same table, for the sake of comparison, the results obtained on the same dataset are listed also, using the other available hmm and hmm-like predictors tmhmm  <cit> , hmmtop  <cit> , memsat  <cit> , phobius  <cit> , umdhmmtmhp  <cit> , and the newly developed s-tmhmm, pro-tmhmm and prodiv-tmhmm  <cit> .
all methods are using single sequence information except from pro-tmhmm and prodiv-tmhmm that use evolutionary information derived from multiple alignments.
the recently published and very successful method of martelli et al  <cit> , was not considered in the current evaluation for several reasons.
firstly, the particular method is currently not available to the public.
secondly and more importantly, this method is based in an ensemble network combining the results of two independent hmm modules with these of a neural network predictor, using a dynamic programming algorithm that filters the prediction in a last step.
thus, this method even though uses hmms it cannot be benefited directly by the currently proposed methodology.
other popular and successful methods such as phdhtm  <cit>  and toppred  <cit> , were also not consider in this evaluation since on the one hand our intention was to evaluate only the hmm and hmm-like predictors that are amenable to incorporate the modifications presented here, and, on the other hand, due to their lower accuracy in general  <cit> , as also as on the particular datasets  <cit> .
for measures of accuracy, we chose the fraction of the correctly predicted residues , the correlation coefficient , the segments overlap , as well as the fraction of proteins with correctly predicted transmembrane segments and correctly predicted topology  <cit> .
the differences in q, c, sov and in the number correctly predicted transmembrane segments among the methods compared here were not statistically significant .
only an overall difference in the number of correctly predicted topologies could be detected , which is attributable to the large discrepancies between the high-scoring methods  and the low-scoring ones .
however, even this should be questionable due to the presence in the set used for training pro-tmhmm, prodiv-tmhmm of proteins similar to the ones we compare here.
even though some of the proteins present in the training set were also included in the sets used for training the other predictors, hmm-tm as tested in the cross-validation test, performs better compared to methods that use single sequences.
the superiority is visible  in almost all measured attributes, but it is more evident in the number of correctly predicted topologies.
we have to assume that the combination of the quality of the training dataset, the cml training scheme and the label optimisation procedure that was performed using the above-mentioned algorithms, is responsible for this result, even though the training set is the one of the smallest that has ever been used for alpha-helical membrane proteins.
hmm-tm, when trained and tested on the whole dataset of  <dig> proteins clearly outperforms also, the algorithmically simpler hmm method umdhmmtmhp that is trained on the same dataset .
compared against the methods that utilise multiple alignments, hmm-tm performs slightly worse, something already expected  <cit> .
however the superiority of the two multiple alignment-based methods is not in the extent previously believed, considering also the presence of homologous sequences in the set used to train these methods, and the non-significant result of the kruskal-wallis test.
the optimal accuracy posterior decoding, the posterior decoding with the dynamic programming and the posterior-viterbi decoding, perform equally well, and both are superior to the 1-best and viterbi algorithms, results which, at least for this case, are in partial agreement with those reported in  <cit> .
when the performance of the methods was tested in the independent test set of  <dig> proteins , similar results were obtained .
all methods  seem to perform equally well, and in all cases the performance of the topology prediction lies within the expected range.
no statistically significant differences could be found concerning q, c, sov and the number of correctly predicted transmembrane segments among the different methods .
however, when comparing the number of correctly predicted topologies, there was a marginally significant difference with a p-value of  <dig> .
when excluding the three worst performing methods , no overall differences could be detected .
in the pairwise comparisons of hmm-tm against these three methods , hmm-tm performs better than memsat and phobius  and marginally better than pro-tmhmm .
overall, hmm-tm performs slightly better than both tmhmm and hmmtop, and it is interesting that umdhmmtmhp performs somewhat better, even though in some cases it yields spurious predictions such as a transmembrane helix with  <dig> amino-acids length .
interestingly, the newly developed methods  do not seem to perform better, despite the presence in their training set of some sequences similar to those under evaluation.
even though the independent test set consists mostly of multi-spanning , and prokaryotic proteins , its use is currently the most appropriate solution since we wanted to independently test the predictors in an, as much as larger as possible dataset, consisting of proteins having no significant similarity to the ones used for training each method.
we should emphasize, that in nearly all the publications describing similar prediction methods, an independent test set was not used  <cit> .
only martelli et al  <cit> , used as an independent test set, proteins with topology determined by low-resolution biochemical experiments, and concluded that such datasets should not be used either as training or test datasets.
this last argument, also applies in order to explain the fact that we were not used such proteins to further enlarge the test set making it thus more balanced.
our prediction method was also tested on the  <dig> datasets containing proteins from e. coli  <cit>  and s. cerevisiae  <cit> .
for reasons of brevity, the detailed results are listed in .
we observe, that our method compares favourably to the other available predictors.
in the e. coli dataset, hmm-tm predicts correctly the localization of the c-terminal part of the sequence for  <dig> out of the  <dig> proteins , outperformed only by phobius, which predicts correctly  <dig> out of the  <dig> proteins .
compared against the methods using evolutionary information , our method performs similarly to the prodiv-tmhmm , and better than pro-tmhmm .
all the remaining methods  perform significantly worse, yielding from  <dig> to  <dig> correct predictions.
in this dataset, the kruskal-wallis test yields an overall p-value of  <dig> , suggesting that there are true statistically detectable differences in the performance of the various methods.
in the pairwise comparisons hmm-tm performs significantly better compared to umdhmmtmhp  and against memsat .
the comparisons of hmm-tm against the remaining methods yielded insignificant results.
excluding from the analysis these two last methods, no overall differences could be found .
furthermore, the two methods using evolutionary information  do not perform significantly better compared to the other four single-sequence methods , since the kruskal-wallis test yields an overall p-value of  <dig> .
concerning the number of the predicted transmembrane helices, hmm-tm predicts closely to the other available top-scoring predictors.
for instance, it is in agreement with the predictions obtained from tmhmm for  <dig> out of the  <dig> proteins, with those obtained from hmmtop for  <dig> out of the  <dig>  and for  <dig> out of the  <dig> proteins with those obtained from pro-tmhmm and prodiv-tmhmm.
in the s. cerevisiae dataset, top-scoring methods were found to be hmmtop, memsat, pro-tmhmm and prodiv-tmhmm correctly predicting the localisation for the c-terminus for  <dig> out of the  <dig> proteins .
hmm-tm, predicts correctly  <dig> out of the  <dig> proteins , and tmhmm, s-tmhmm and umdhmmtmhp reached correct conclusions for  <dig> out of the  <dig> proteins .
phobius in this dataset performs significantly worse, reaching an accuracy of only  <dig> %.
similar observations hold also for this set, concerning the number of predicted transmembrane segments, and the general agreement of our method with the others.
in this dataset however, there are not large discrepancies among the various methods resulting in an overall insignificant kruskal-wallis test .
in total , the  <dig> methods using evolutionary information , were ranked first, with  <dig> % and  <dig> % correct predictions respectively, followed by hmm-tm , hmmtop , phobius , tmhmm , memsat , s-tmhmm  and umdhmmtmhp .
however, these differences showed no overall statisticall significance .
even though, the methods using evolutionary information perform slightly  better than hmm-tm, their superiority is not validated statistically here and more importantly, they do not offer the option to fix the topology of various sequence parts.
only tmhmm, phobius and hmmtop offer such options, and compared to them, hmm-tm seems to perform constantly better in all the tests performed.
interestingly, when the experimentally determined topology of the c-terminus is incorporated into the predictions for the two proteins on which the method failed , the predicted number of transmembrane segments changes  and shows a remarkable agreement with those predicted by the above-mentioned methods .
using the same reasoning for the proteins missed by hmmtop and tmhmm, we can reach similar conclusions.
in the independent dataset of  <dig> proteins, if we fix the location of the c-terminus to its observed topology, all of the methods that are capable of incorporating such information , increase both the number of correctly predicted transmembrane segments and the number of correctly predicted topologies.
in hmm-tm the number of correctly predicted transmembrane segments is increased from  <dig> to  <dig>  as well as the number of correctly predicted topologies .
similarly, in tmhmm number of correctly predicted topologies becomes  <dig> , while the number of correctly predicted transmembrane segments remains 19; in hmmtop we observe only a slight increase of the correctly predicted topologies  and finally for phobius we observe an increase both in the correctly predicted topologies becomes  and in the correctly predicted transmembrane segments .
similar results were presented initially in the work of mellen, krogh and von heijne  <cit> , but here we could not validate them statistically due to the small sample size.
thus, this observation should be further tested in a larger independent dataset of proteins with experimentally determined topology.
we have to mention though, that there is a clear gain in correctly specifying the topology using such algorithms, and in future works it might be tempting to construct a predictor that uses both evolutionary derived information and the option to fix various sequence parts in the desired location.
the usefulness and the practical applicability of the prediction method described here, combined with the option of fixing the topology of various segments along the sequence incorporating this way the experimental information during the decoding phase, could be demonstrated in the case of the multidrug efflux transporter acrb of e. coli.
the structure has been resolved crystallographically  <cit> , and it has been shown that the protein contains  <dig> transmembrane helices .
all the prediction methods used here  failed to accurately predict the full topology of the protein.
as we can see , hmm-tm misses  <dig> transmembrane segments, while falsely predicts an additional segment that does not exist.
however, using the results obtained from cysteine-scanning mutagenesis  <cit> , and incorporating them in the predictions obtained with hmm-tm , results in a highly reliable prediction that is in excellent agreement with the obtained crystallographically solved structure.
lastly, even though this was not a primary intention of our study, we evaluated the discrimination capabilities of the methods on the set of  <dig> globular proteins with known three-dimensional structures, a set used initially for the same purpose in the evaluation of tmhmm  <cit> .
the results were very conflicting reflecting the differences in the training strategies of the various predictors as well as the different primary intentions of their developers.
thus, when the total number of proteins predicted to be non transmembrane was evaluated, methods that were designed to be applied only on transmembrane proteins such as hmm-tm, hmmtop, umdhmmtmhp, memsat and prodiv-tmhmm perform poorly, predicting falsely  <dig> %,  <dig> %,  <dig> %,  <dig> % and  <dig> % of the globular proteins to possess at least one transmembrane segment, respectively.
from the other hand, methods that were trained initially in order to discriminate globular proteins from transmembrane ones, such as tmhmm, phobius, s-tmhmm and pro-tmhmm, perform considerably better, predicting respectively only  <dig> %,  <dig> %,  <dig> % and  <dig> % of the globular proteins to be transmembrane.
when we considered as a discrimination criterion the total number of aminoacids predicted in transmebrane segments, and taking as a cut-off length the value of  <dig> aminoacids, hmm-tm predicts falsely  <dig> % of the globular proteins, tmhmm  <dig> %, hmmtop  <dig> %, phobius  <dig> %, umdhmmtmhp  <dig> %, memsat  <dig> %, s-tmhmm  <dig> %, pro-tmhmm  <dig> % and prodiv-tmhmm  <dig> %.
the differences in both cases are highly significant , and it is evident that prodiv-tmhmm is highly unreliable for discrimination purposes, a fact noticed already in  <cit> , followed by memsat and umdhmmtmhp, whereas hmm-tm and hmmtop form a group of intermediate reliability just before the highly reliable for this task methods, tmhmm, phobius, s-tmhmm and pro-tmhmm.
discussion
the primary intention of this work was to introduce the modifications to the standard algorithms that will allow incorporation of prior structural or topological information during the decoding procedure; however, the prediction method presented is quite accurate.
one may argue, that we should have trained a prediction method that uses evolutionary information in order to achieve the best possible results  <cit> .
however, this was not possible currently for technical reasons.
furthermore, as we already stated, the primary intention of the particular work was to present the algorithmic details, and not to develop a prediction method.
thus, the algorithmic modifications could now be easily applied in any prediction method based on a hmm.
from the reported results, it is obvious, that hmm-tm performs comparably if not better than the already established top-scoring hmm methods using single sequences and compares well against the methods using multiple alignments.
as a matter of fact, using a rigorous statistical methodology, we found that hmm-tm is not outperformed significantly in any of the tests presented here .
on the contrary, clearly outperforms some of the available methods in some of the performed tests.
these conclusions, are valid also for the per-residue and per-segment measures reported in the set of  <dig> proteins, as well as for the blind test on newly solved three-dimensional structures and on proteins with experimentally verified location of the c-terminus.
however, there are cases in which a joint prediction could give better results than each one of the individual methods.
from the detailed results listed in , we observe that for only  <dig> out of the  <dig> proteins used  all of the available algorithms fail to predict correctly the localisation of the c-terminal.
this yields another potential use for hmm-tm besides acting as a standalone predictor: it could be very useful as a part of a consensus prediction method.
such consensus predictions, have been proven to significantly improve the predictive performance compared to individual methods, either referring to alpha-helical  <cit> , beta-barrel membrane proteins  <cit>  or to general secondary structure prediction methods  <cit> .
for developing a successful consensus prediction method, it is necessary to have high-scoring individual methods, producing independent results, which indeed is the case here.
we should emphasize also at this point, that the algorithmic modifications that we introduce, by no way confer bias to the prediction method.
thus, when the decoding  is applied in an unconstrained manner, the results obtained are not by any means are affected by the existence of the modifications since they do not used at all.
however, when experimentally derived information emerges, the algorithmic modifications force the predictions to be in agreement with this prior information.
thus, in such cases it is reasonable to observe better predictions obtained by such an algorithm  compared to another algorithm  that does not use this information.
ideally, in future works these modifications should be applied to a prediction method that uses evolutionary information in order to obtain the best possible results.
furthermore, the extent to which the prior knowledge affects the rate of the correct predictions should be evaluated in a larger dataset.
the algorithmic modifications presented in this paper , are for the first time introduced in such detail, allowing one to implement them in a straightforward manner.
although these modifications appear trivial, there is clearly a need to be described in such a detail in order to further clarify some obscure points in the literature.
all the relevant works addressed such an issue, in the past were either published as a short applications note in computational biology journals, or as regular papers in molecular biology journals, and in both cases they did not spend more than a sentence or two for describing the algorithms .
for instance, in the first published work that mentions a constraint prediction  <cit> , the authors state : "this segment information is incorporated into the baum-welch algorithm by a conditional probability."
in a later work  <cit> , the authors simply state that: "the basic tmhmm algorithm allows one to fix the class-assignment for any position in the sequence by setting the probability for a position to belong to a certain class to  <dig>  a priori."
finally, in a recently published work  <cit> , bernsel and von heijne state that: "the in/out-fixation of a certain residue is achieved by setting the corresponding state probability in the hmm equal to  <dig> , ...".
clearly, these statements do not constitute complete and thoroughly described methodology that it is easily applicable from someone willing to incorporate such options to a prediction method.
furthermore, here for the first time we apply algorithms for constrained predictions applicable to all the currently available decoding methods, and in all cases preserving the probabilistic nature of the hmm.
it is clear though, that these modifications can also be used in any decoding algorithm may appear in the future, or in any hmm trained with various schemes , as well as in methods using evolutionary information or not.
lastly, we should also point that in this work we considered only incorporating in the prediction the experimentally verified topology of various sequence segments.
other works have been presented, dealing for instance with the incorporation of prior physicochemical knowledge concerning the propensity of a helix to be transmembrane or not  <cit> .
clearly, such approaches even though useful in practical applications, are irrelevant to the currently proposed methodology and should be considered separately.
CONCLUSIONS
we have presented here, modified algorithms for incorporating prior topological information into hmms.
these algorithms constitute trivial modifications to the well known forward and backward algorithms involved in the probability calculations on hmms, as well as to the already established algorithms for decoding such models .
we presented these algorithms without introducing further computational complexity, while at the same time retaining the probabilistic interpretation of the results.
these algorithms may also be useful in other applications of hmms, besides the transmembrane protein topology prediction, since they could be applied in any circular hmm, irrespective of the training procedure used.
we have shown that these algorithms could be used also with more complex labelling schemes as well as with hmms using both discrete and continuous emission probabilities.
the same modifications may also be applied in optimising the discriminative capability of the models, especially in cases of misplaced labelling arising from inherently mislabelled data.
we have presented an application in the prediction of transmembrane segments of alpha-helical membrane proteins, and we developed a method that compares well against, if not better than, the already available top-scoring methods for the same task either using single sequences or multiple alignments.
we also have to note, that the method presented here undoubtedly seems to perform better compared to the other hmm predictors that allow the incorporation of experimentally derived information.
we also confirmed the results of previous studies, indicating that incorporation of prior topological knowledge will further improve the performance of predictive algorithms, and provided evidence that using a consensus of the top-scoring methods, the predictive performance increases.
consensus of individual methods has been proven a useful strategy for obtaining better predictions, and thus, it could be benefited from including even more high-scoring individual methods.
finally, we set up a web-server, freely available to academic users, where the above-mentioned predictive method can be found (), offering the most advanced decoding options currently available.
the method developed here might be useful to experimentalists who require reliable predictions, in the light of experimentally derived information.

 hidden markov models are probabilistic models, commonly used during the last years for applications in bioinformatics. these tasks include gene finding, multiple alignments and database searches, prediction of signal peptides, prediction of protein secondary structure, prediction of transmembrane protein topology, as well as joint prediction of transmembrane helices and signal peptides. especially in the case of transmembrane proteins, hmms have been found to perform significantly better compared to other sophisticated machine-learning techniques such as neural networks or support vector machines. this is the case irrespective to which class of transmembrane proteins we refer to, since it has been shown that the best currently available predictors for alpha-helical membrane proteins as well as for beta-barrel outer membrane proteins, are methods based on hmms. experimental techniques are routinely used to partially uncover the transmembrane topology of membrane proteins. such methods include the use of various reporter fusions, chemical labelling, epitope tagging, antibodies and cysteine scanning mutagenesis. the gene fusion approach seems to be the most effective method and the reporters used, include alkaline phosphatase, beta-galactosidase, beta-lactamase as well as various fluorescent proteins. with the development of fast and reliable methods to utilise gene fusion technology in order to determine the location of a protein's c-terminus, it has been shown that incorporating topological information into the prediction methods improves largely the performance of even the top-scoring methods, making easy to screen newly sequenced genomes. this has been demonstrated, using experimentally derived information regarding e. coli and s. cerevisiae protein datasets. more recently, a global topological analysis of the e. coli inner membrane proteins was performed, providing reliable models for more than membrane proteins. among the top-scoring hmm predictors currently available, hmmtop provides the user the option to incorporate such information. tmhmm is currently not supporting such an option in its standard web-server, and the users have to turn the tmhmmfix server or to the joint prediction of transmembrane helices and signal peptides offered by phobius. lately, bernsel and von heijne, used a similar idea that consisted of treating the occurrence of soluble protein domains with known localisation, as experimentally determined topology. this way, they implemented a modified version of the hmm described by viklund and elofsson, in order to apply constrained predictions. however, even in this work the algorithmic details were not presented nor the prediction method became available to the public. moreover, no effort has been made in the literature in order to completely and accurately describe the mathematical details of the algorithms that allow the arbitrary incorporation of such prior knowledge, in a way that prevents hmms from loosing their probabilistic interpretation. the nature of hmms, allows some brute conditioning; for instance, setting transition probabilities from a particular state to the end state to zero will allow the fixation of the c-terminus in the desired topology. similarly, having knowledge of the presence of a signal peptide, after removing it, one may force the hmm to consider as allowed transitions from the begin state only those with direction to the extracellular loop states of the model. unfortunately, the probabilistic interpretation of these results will be lost. thus, it would be useful to have a method that enables us to arbitrarily fix any part of the sequence in a specified topology, while at the same time retaining the probabilistic interpretation of the algorithms used for decoding the hmm. in this work, we present some trivial modifications to the standard algorithms used in hmms, namely the forward and backward algorithms. these modifications are very similar with those used on training hmms with labelled sequences, but here they are considered in the context of models' decoding. we also show, that the likelihoods derived when applying these modified algorithms, can be expressed as posterior probabilities of the prior experimental information given the sequences and the model parameters, thus retaining this way the probabilistic interpretation of the results. we also introduce similar trivial modifications to all known algorithms used for decoding an hmm. in particular, we present modified versions of the standard viterbi algorithm, which finds the most probable path of states, of the 1-best algorithm, which tries to find the optimal labelling of a sequence, giving always a labelling with equal or greater probability compared to the viterbi decoding. similar modifications follow for the "a-posteriori" decoding method, which in many applications, and under certain conditions, provides better prediction, as well as to the newly developed posterior-viterbi method and the optimal accuracy posterior decoding method, that both combine elements of viterbi and posterior decoding. finally, we present an application of these algorithms, training a hmm to predict the transmembrane segments of alpha-helical membrane proteins. the model is trained in a discriminative manner with the conditional maximum likelihood criterion, using a dataset of proteins with structures known at atomic resolution, and it is shown to compare well against the top-scoring algorithms currently available. the method, hmm-tm, is freely available for academic users at, where the user may choose any of the four above mentioned algorithms for decoding, an option not currently available in any other prediction method.  in table we list the results obtained on the training set with our method, both on a self-consistency test and on a 9-fold cross-validation procedure. in the same table, for the sake of comparison, the results obtained on the same dataset are listed also, using the other available hmm and hmm-like predictors tmhmm, hmmtop, memsat, phobius, umdhmmtmhp, and the newly developed s-tmhmm, pro-tmhmm and prodiv-tmhmm. all methods are using single sequence information except from pro-tmhmm and prodiv-tmhmm that use evolutionary information derived from multiple alignments. the recently published and very successful method of martelli et al, was not considered in the current evaluation for several reasons. firstly, the particular method is currently not available to the public. secondly and more importantly, this method is based in an ensemble network combining the results of two independent hmm modules with these of a neural network predictor, using a dynamic programming algorithm that filters the prediction in a last step. thus, this method even though uses hmms it cannot be benefited directly by the currently proposed methodology. other popular and successful methods such as phdhtm and toppred, were also not consider in this evaluation since on the one hand our intention was to evaluate only the hmm and hmm-like predictors that are amenable to incorporate the modifications presented here, and, on the other hand, due to their lower accuracy in general, as also as on the particular datasets. for measures of accuracy, we chose the fraction of the correctly predicted residues, the correlation coefficient, the segments overlap, as well as the fraction of proteins with correctly predicted transmembrane segments and correctly predicted topology. the differences in q, c, sov and in the number correctly predicted transmembrane segments among the methods compared here were not statistically significant. only an overall difference in the number of correctly predicted topologies could be detected, which is attributable to the large discrepancies between the high-scoring methods and the low-scoring ones. however, even this should be questionable due to the presence in the set used for training pro-tmhmm, prodiv-tmhmm of proteins similar to the ones we compare here. even though some of the proteins present in the training set were also included in the sets used for training the other predictors, hmm-tm as tested in the cross-validation test, performs better compared to methods that use single sequences. the superiority is visible in almost all measured attributes, but it is more evident in the number of correctly predicted topologies. we have to assume that the combination of the quality of the training dataset, the cml training scheme and the label optimisation procedure that was performed using the above-mentioned algorithms, is responsible for this result, even though the training set is the one of the smallest that has ever been used for alpha-helical membrane proteins. hmm-tm, when trained and tested on the whole dataset of proteins clearly outperforms also, the algorithmically simpler hmm method umdhmmtmhp that is trained on the same dataset. compared against the methods that utilise multiple alignments, hmm-tm performs slightly worse, something already expected. however the superiority of the two multiple alignment-based methods is not in the extent previously believed, considering also the presence of homologous sequences in the set used to train these methods, and the non-significant result of the kruskal-wallis test. the optimal accuracy posterior decoding, the posterior decoding with the dynamic programming and the posterior-viterbi decoding, perform equally well, and both are superior to the 1-best and viterbi algorithms, results which, at least for this case, are in partial agreement with those reported in. when the performance of the methods was tested in the independent test set of proteins, similar results were obtained. all methods seem to perform equally well, and in all cases the performance of the topology prediction lies within the expected range. no statistically significant differences could be found concerning q, c, sov and the number of correctly predicted transmembrane segments among the different methods. however, when comparing the number of correctly predicted topologies, there was a marginally significant difference with a p-value of. when excluding the three worst performing methods, no overall differences could be detected. in the pairwise comparisons of hmm-tm against these three methods, hmm-tm performs better than memsat and phobius and marginally better than pro-tmhmm. overall, hmm-tm performs slightly better than both tmhmm and hmmtop, and it is interesting that umdhmmtmhp performs somewhat better, even though in some cases it yields spurious predictions such as a transmembrane helix with amino-acids length. interestingly, the newly developed methods do not seem to perform better, despite the presence in their training set of some sequences similar to those under evaluation. even though the independent test set consists mostly of multi-spanning, and prokaryotic proteins, its use is currently the most appropriate solution since we wanted to independently test the predictors in an, as much as larger as possible dataset, consisting of proteins having no significant similarity to the ones used for training each method. we should emphasize, that in nearly all the publications describing similar prediction methods, an independent test set was not used. only martelli et al, used as an independent test set, proteins with topology determined by low-resolution biochemical experiments, and concluded that such datasets should not be used either as training or test datasets. this last argument, also applies in order to explain the fact that we were not used such proteins to further enlarge the test set making it thus more balanced. our prediction method was also tested on the datasets containing proteins from e. coli and s. cerevisiae. for reasons of brevity, the detailed results are listed in. we observe, that our method compares favourably to the other available predictors. in the e. coli dataset, hmm-tm predicts correctly the localization of the c-terminal part of the sequence for out of the proteins, outperformed only by phobius, which predicts correctly out of the proteins. compared against the methods using evolutionary information, our method performs similarly to the prodiv-tmhmm, and better than pro-tmhmm. all the remaining methods perform significantly worse, yielding from to correct predictions. in this dataset, the kruskal-wallis test yields an overall p-value of, suggesting that there are true statistically detectable differences in the performance of the various methods. in the pairwise comparisons hmm-tm performs significantly better compared to umdhmmtmhp and against memsat. the comparisons of hmm-tm against the remaining methods yielded insignificant results. excluding from the analysis these two last methods, no overall differences could be found. furthermore, the two methods using evolutionary information do not perform significantly better compared to the other four single-sequence methods, since the kruskal-wallis test yields an overall p-value of. concerning the number of the predicted transmembrane helices, hmm-tm predicts closely to the other available top-scoring predictors. for instance, it is in agreement with the predictions obtained from tmhmm for out of the proteins, with those obtained from hmmtop for out of the and for out of the proteins with those obtained from pro-tmhmm and prodiv-tmhmm. in the s. cerevisiae dataset, top-scoring methods were found to be hmmtop, memsat, pro-tmhmm and prodiv-tmhmm correctly predicting the localisation for the c-terminus for out of the proteins. hmm-tm, predicts correctly out of the proteins, and tmhmm, s-tmhmm and umdhmmtmhp reached correct conclusions for out of the proteins. phobius in this dataset performs significantly worse, reaching an accuracy of only %. similar observations hold also for this set, concerning the number of predicted transmembrane segments, and the general agreement of our method with the others. in this dataset however, there are not large discrepancies among the various methods resulting in an overall insignificant kruskal-wallis test. in total, the methods using evolutionary information, were ranked first, with % and % correct predictions respectively, followed by hmm-tm, hmmtop, phobius, tmhmm, memsat, s-tmhmm and umdhmmtmhp. however, these differences showed no overall statisticall significance. even though, the methods using evolutionary information perform slightly better than hmm-tm, their superiority is not validated statistically here and more importantly, they do not offer the option to fix the topology of various sequence parts. only tmhmm, phobius and hmmtop offer such options, and compared to them, hmm-tm seems to perform constantly better in all the tests performed. interestingly, when the experimentally determined topology of the c-terminus is incorporated into the predictions for the two proteins on which the method failed, the predicted number of transmembrane segments changes and shows a remarkable agreement with those predicted by the above-mentioned methods. using the same reasoning for the proteins missed by hmmtop and tmhmm, we can reach similar conclusions. in the independent dataset of proteins, if we fix the location of the c-terminus to its observed topology, all of the methods that are capable of incorporating such information, increase both the number of correctly predicted transmembrane segments and the number of correctly predicted topologies. in hmm-tm the number of correctly predicted transmembrane segments is increased from to as well as the number of correctly predicted topologies. similarly, in tmhmm number of correctly predicted topologies becomes, while the number of correctly predicted transmembrane segments remains 19; in hmmtop we observe only a slight increase of the correctly predicted topologies and finally for phobius we observe an increase both in the correctly predicted topologies becomes and in the correctly predicted transmembrane segments. similar results were presented initially in the work of mellen, krogh and von heijne, but here we could not validate them statistically due to the small sample size. thus, this observation should be further tested in a larger independent dataset of proteins with experimentally determined topology. we have to mention though, that there is a clear gain in correctly specifying the topology using such algorithms, and in future works it might be tempting to construct a predictor that uses both evolutionary derived information and the option to fix various sequence parts in the desired location. the usefulness and the practical applicability of the prediction method described here, combined with the option of fixing the topology of various segments along the sequence incorporating this way the experimental information during the decoding phase, could be demonstrated in the case of the multidrug efflux transporter acrb of e. coli. the structure has been resolved crystallographically, and it has been shown that the protein contains transmembrane helices. all the prediction methods used here failed to accurately predict the full topology of the protein. as we can see, hmm-tm misses transmembrane segments, while falsely predicts an additional segment that does not exist. however, using the results obtained from cysteine-scanning mutagenesis, and incorporating them in the predictions obtained with hmm-tm, results in a highly reliable prediction that is in excellent agreement with the obtained crystallographically solved structure. lastly, even though this was not a primary intention of our study, we evaluated the discrimination capabilities of the methods on the set of globular proteins with known three-dimensional structures, a set used initially for the same purpose in the evaluation of tmhmm. the results were very conflicting reflecting the differences in the training strategies of the various predictors as well as the different primary intentions of their developers. thus, when the total number of proteins predicted to be non transmembrane was evaluated, methods that were designed to be applied only on transmembrane proteins such as hmm-tm, hmmtop, umdhmmtmhp, memsat and prodiv-tmhmm perform poorly, predicting falsely %, %, %, % and % of the globular proteins to possess at least one transmembrane segment, respectively. from the other hand, methods that were trained initially in order to discriminate globular proteins from transmembrane ones, such as tmhmm, phobius, s-tmhmm and pro-tmhmm, perform considerably better, predicting respectively only %, %, % and % of the globular proteins to be transmembrane. when we considered as a discrimination criterion the total number of aminoacids predicted in transmebrane segments, and taking as a cut-off length the value of aminoacids, hmm-tm predicts falsely % of the globular proteins, tmhmm %, hmmtop %, phobius %, umdhmmtmhp %, memsat %, s-tmhmm %, pro-tmhmm % and prodiv-tmhmm %. the differences in both cases are highly significant, and it is evident that prodiv-tmhmm is highly unreliable for discrimination purposes, a fact noticed already in, followed by memsat and umdhmmtmhp, whereas hmm-tm and hmmtop form a group of intermediate reliability just before the highly reliable for this task methods, tmhmm, phobius, s-tmhmm and pro-tmhmm. discussion the primary intention of this work was to introduce the modifications to the standard algorithms that will allow incorporation of prior structural or topological information during the decoding procedure; however, the prediction method presented is quite accurate. one may argue, that we should have trained a prediction method that uses evolutionary information in order to achieve the best possible results. however, this was not possible currently for technical reasons. furthermore, as we already stated, the primary intention of the particular work was to present the algorithmic details, and not to develop a prediction method. thus, the algorithmic modifications could now be easily applied in any prediction method based on a hmm. from the reported results, it is obvious, that hmm-tm performs comparably if not better than the already established top-scoring hmm methods using single sequences and compares well against the methods using multiple alignments. as a matter of fact, using a rigorous statistical methodology, we found that hmm-tm is not outperformed significantly in any of the tests presented here. on the contrary, clearly outperforms some of the available methods in some of the performed tests. these conclusions, are valid also for the per-residue and per-segment measures reported in the set of proteins, as well as for the blind test on newly solved three-dimensional structures and on proteins with experimentally verified location of the c-terminus. however, there are cases in which a joint prediction could give better results than each one of the individual methods. from the detailed results listed in, we observe that for only out of the proteins used all of the available algorithms fail to predict correctly the localisation of the c-terminal. this yields another potential use for hmm-tm besides acting as a standalone predictor: it could be very useful as a part of a consensus prediction method. such consensus predictions, have been proven to significantly improve the predictive performance compared to individual methods, either referring to alpha-helical, beta-barrel membrane proteins or to general secondary structure prediction methods. for developing a successful consensus prediction method, it is necessary to have high-scoring individual methods, producing independent results, which indeed is the case here. we should emphasize also at this point, that the algorithmic modifications that we introduce, by no way confer bias to the prediction method. thus, when the decoding is applied in an unconstrained manner, the results obtained are not by any means are affected by the existence of the modifications since they do not used at all. however, when experimentally derived information emerges, the algorithmic modifications force the predictions to be in agreement with this prior information. thus, in such cases it is reasonable to observe better predictions obtained by such an algorithm compared to another algorithm that does not use this information. ideally, in future works these modifications should be applied to a prediction method that uses evolutionary information in order to obtain the best possible results. furthermore, the extent to which the prior knowledge affects the rate of the correct predictions should be evaluated in a larger dataset. the algorithmic modifications presented in this paper, are for the first time introduced in such detail, allowing one to implement them in a straightforward manner. although these modifications appear trivial, there is clearly a need to be described in such a detail in order to further clarify some obscure points in the literature. all the relevant works addressed such an issue, in the past were either published as a short applications note in computational biology journals, or as regular papers in molecular biology journals, and in both cases they did not spend more than a sentence or two for describing the algorithms. for instance, in the first published work that mentions a constraint prediction, the authors state: "this segment information is incorporated into the baum-welch algorithm by a conditional probability." in a later work, the authors simply state that: "the basic tmhmm algorithm allows one to fix the class-assignment for any position in the sequence by setting the probability for a position to belong to a certain class to a priori." finally, in a recently published work, bernsel and von heijne state that: "the in/out-fixation of a certain residue is achieved by setting the corresponding state probability in the hmm equal to,...". clearly, these statements do not constitute complete and thoroughly described methodology that it is easily applicable from someone willing to incorporate such options to a prediction method. furthermore, here for the first time we apply algorithms for constrained predictions applicable to all the currently available decoding methods, and in all cases preserving the probabilistic nature of the hmm. it is clear though, that these modifications can also be used in any decoding algorithm may appear in the future, or in any hmm trained with various schemes, as well as in methods using evolutionary information or not. lastly, we should also point that in this work we considered only incorporating in the prediction the experimentally verified topology of various sequence segments. other works have been presented, dealing for instance with the incorporation of prior physicochemical knowledge concerning the propensity of a helix to be transmembrane or not. clearly, such approaches even though useful in practical applications, are irrelevant to the currently proposed methodology and should be considered separately.  we have presented here, modified algorithms for incorporating prior topological information into hmms. these algorithms constitute trivial modifications to the well known forward and backward algorithms involved in the probability calculations on hmms, as well as to the already established algorithms for decoding such models. we presented these algorithms without introducing further computational complexity, while at the same time retaining the probabilistic interpretation of the results. these algorithms may also be useful in other applications of hmms, besides the transmembrane protein topology prediction, since they could be applied in any circular hmm, irrespective of the training procedure used. we have shown that these algorithms could be used also with more complex labelling schemes as well as with hmms using both discrete and continuous emission probabilities. the same modifications may also be applied in optimising the discriminative capability of the models, especially in cases of misplaced labelling arising from inherently mislabelled data. we have presented an application in the prediction of transmembrane segments of alpha-helical membrane proteins, and we developed a method that compares well against, if not better than, the already available top-scoring methods for the same task either using single sequences or multiple alignments. we also have to note, that the method presented here undoubtedly seems to perform better compared to the other hmm predictors that allow the incorporation of experimentally derived information. we also confirmed the results of previous studies, indicating that incorporation of prior topological knowledge will further improve the performance of predictive algorithms, and provided evidence that using a consensus of the top-scoring methods, the predictive performance increases. consensus of individual methods has been proven a useful strategy for obtaining better predictions, and thus, it could be benefited from including even more high-scoring individual methods. finally, we set up a web-server, freely available to academic users, where the above-mentioned predictive method can be found (), offering the most advanced decoding options currently available. the method developed here might be useful to experimentalists who require reliable predictions, in the light of experimentally derived information. 
the algorithms presented here, are easily implemented in any kind of a hidden markov model, whereas the prediction method is freely available for academic users at, offering the most advanced decoding options currently available. in many applications, such as transmembrane protein topology prediction, the incorporation of limited amount of information regarding the topology, arising from biochemical experiments, has been proved a very useful strategy that increased remarkably the performance of even the top-scoring methods. we present modifications to the standard forward and backward algorithms of hmms and we also show explicitly, how reliable predictions may arise by these modifications, using all the algorithms currently available for decoding hmms. a similar procedure may be used in the training procedure, aiming at optimizing the labels of the hmm's classes, especially in cases such as transmembrane proteins where the labels of the membrane-spanning segments are inherently misplaced. hidden markov models have been extensively used in computational molecular biology, for modelling protein and nucleic acid sequences. we present here, a simple method that allows incorporation of prior topological information concerning the sequences at hand, while at the same time the hmms retain their full probabilistic interpretation in terms of conditional probabilities. however, no clear and formal explanation of the algorithms that retains the probabilistic interpretation of the models has been presented so far in the literature. we present an application of this approach developing a method to predict the transmembrane regions of alpha-helical membrane proteins, trained on crystallographically solved data. we show that this method compares well against already established algorithms presented in the literature, and it is extremely useful in practical applications.
 hidden markov models have been extensively used in computational molecular biology, for modelling protein and nucleic acid sequences. in many applications, such as transmembrane protein topology prediction, the incorporation of limited amount of information regarding the topology, arising from biochemical experiments, has been proved a very useful strategy that increased remarkably the performance of even the top-scoring methods. however, no clear and formal explanation of the algorithms that retains the probabilistic interpretation of the models has been presented so far in the literature.  we present here, a simple method that allows incorporation of prior topological information concerning the sequences at hand, while at the same time the hmms retain their full probabilistic interpretation in terms of conditional probabilities. we present modifications to the standard forward and backward algorithms of hmms and we also show explicitly, how reliable predictions may arise by these modifications, using all the algorithms currently available for decoding hmms. a similar procedure may be used in the training procedure, aiming at optimizing the labels of the hmm's classes, especially in cases such as transmembrane proteins where the labels of the membrane-spanning segments are inherently misplaced. we present an application of this approach developing a method to predict the transmembrane regions of alpha-helical membrane proteins, trained on crystallographically solved data. we show that this method compares well against already established algorithms presented in the literature, and it is extremely useful in practical applications.  the algorithms presented here, are easily implemented in any kind of a hidden markov model, whereas the prediction method is freely available for academic users at, offering the most advanced decoding options currently available. 