BACKGROUND
all-beta membrane proteins constitute a well structurally conserved class of proteins, that span the outer membrane of gram-negative bacteria with a barrel-like structure.
in all cases known so far with atomic resolution, the barrel consists of an even number of anti-parallel beta strands, whose number ranges from  <dig> to  <dig> strands, depending on the protein and/or its functional role  <cit> .
in eukaryotes, it is known that similar architectures are present in the outer membrane of chloroplasts and mitochondria, although so far none of the so-called "porins", mainly acting as voltage dependent anion channels , have been solved with atomic resolution .
it is therefore urgent to devise methods for the prediction of the topology of this class of membrane proteins.
indeed the correct prediction of the protein topology, given the conservation of the barrel architecture may greatly help in threading procedures, especially when sequence homology is low.
furthermore reliable methods, endowed with a low rate of false positives, can also help in genome annotation on the basis of protein structure prediction  <cit> .
the problem of predicting beta barrel membrane proteins has been recently addressed with machine learning approaches, and among them hidden markov models  have been shown to outperform previously existing methods  <cit> .
hmms were developed for alignments  <cit> , pattern detection  <cit>  and also for predictions, as in the case of the topology of all-alpha and all-beta membrane proteins  <cit> .
when hmms are implemented for predicting a given feature, a decoding algorithm is needed.
with decoding we refer to the assignment of a path through the hmm states  given an observed sequence o. in this way, we can also assign a label to each sequence element  <cit> .
more generally, as stated in  <cit> , the decoding is the prediction of the labelsof an unknownpath.
the most famous decoding procedure is the viterbi algorithm, which finds the most probable allowed path through the hmm model.
viterbi decoding is particularly effective when there is a single best path among others much less probable.
when several paths have similar probabilities, the posterior decoding or the 1-best algorithms are more convenient  <cit> .
the posterior decoding assigns the state path on the basis of the posterior probability, although the selected path might be not allowed.
in this paper we address the problem of preserving the automaton grammar and concomitantly exploiting the posterior probabilities, without the need of the post-processing algorithm  <cit> .
prompted by this, we design a new decoding algorithm, the posterior-viterbidecoding , which preserves the automaton grammars and at thesame time exploits the posterior probabilities.
a related idea, that is specific for pairwise alignments was previously introduced to improve the sequence alignment accuracy  <cit> .
we show that pv performs better than the other algorithms when we test it on the problem of predicting the topology of beta-barrel membrane proteins.
RESULTS
testing the decoding algorithms on all-beta membrane proteins
in order to test our decoding algorithm on real biological data, we used a previously developed hmm, devised for the prediction of the topology of beta-barrel membrane proteins  <cit> .
the hidden markov model is a sequence-profile-based hmm and takes advantage of emitting vectors instead of symbols, as described in  <cit> .
since the previously designed and trained hmm  <cit>  emits profile vectors, sequence profiles have been computed from the alignments as derived with psi-blast  <cit>  on the non-redundant database of protein sequences .
the results obtained using the four different decoding algorithms are shown in table  <dig>  where the performance is tested with a leave-one-out cross validation procedure for the first  <dig> proteins and as blind-test for the latter  <dig> .
it is evident that for the problem at hand the viterbi decoding and the 1-best are unreliable, since only one of the proteins is correctly assigned.
in this case the posterior decoding is more efficient and can correctly assign 60% and 40% of the proteins, in cross-validation and on the blind set, respectively.
here the posterior decoding is used without maxsubseq, introduced before to recast the grammar  <cit> .
from table  <dig> it evident that the new pv decoding is the best performing decoding achieving 80% and 60% accuracy in cross-validation and on the blind set, respectively.
this is done ensuring that predictions are consistent with the designed automaton grammar.
comparison with other available hmms
in table  <dig> we show the results of the comparison between our hmm-decoding with those obtained from the available web servers, based on similar approaches  <cit> .
the pred-tmbb server  <cit>  allows the user to test three different algorithms .
differently from us they find that their hmm does not show significant differences among the three decoding algorithms.
this dissimilar behaviour may be due to several concurring facts: i) the different hmm models, ii) pred-tmbb runs on a single-sequence input, iii) pred-tmbb is trained using the conditional maximum likelihood  <cit> .
the second server proftmb  <cit>  is based on a method that exploits multiple sequence information and posterior probabilities.
their decoding is related to the posterior-viterbi; however, in their algorithm the authors first obtained the posterior sum contracted into two possible labeling , then they made use of the explicit value of the hmm transition probabilities .
in this way they count the transition probabilities twice  and the proftmb performance is not very different from ours.
finally, the third server hmmb2tmr  <cit>  achieves a performance quite similar to that obtained with pv decoding.
to do that hmmb2tmr takes advantage of the maxsubseq algorithm on top of the posterior sum decoding.
however, although maxsubseq is a very general two-class segment optimization algorithm, it is a post processing procedure that has to be applied after a hmm decoding.
on the contrary, pv is a general decoding algorithm and it is more useful when the underlying predictor is a hmm, where more than two labels and different constraints can be introduced into the automaton grammars.
CONCLUSIONS
the new pv decoding algorithm is more convenient in that it overcomes the difficulties of introducing a problem-dependent optimization algorithm when the automaton grammar is to be re-cast.
when one-state-path dominates we may expect that pv does not perform better than the other decoding algorithms, and in these cases the 1-best is preferred  <cit> .
nevertheless, we show that when several concurring paths are present, as in the case of our beta-barrel hmm, pv performs better than the others.
although pv takes more time than other algorithms , the pv asymptotic computational time-complexity still remains o  as for the other decodings.
as far as the memory requirement is concerned, pv needs the same space-complexity of the viterbi and posterior ), while 1-best in the average case requires less memory, and can also be reduced  <cit> .
when computational speed is an issue, viterbi algorithm is the fastest and the time complexity order is time ≤ time ≤ time.
finally, pv satisfies any hmm grammar structures, including automata containing silent states, and it is applicable to all the possible hmm models with an arbitrary number of labels and without having to work out a problem-dependent optimization algorithm.

 all-beta membrane proteins constitute a well structurally conserved class of proteins, that span the outer membrane of gram-negative bacteria with a barrel-like structure. in all cases known so far with atomic resolution, the barrel consists of an even number of anti-parallel beta strands, whose number ranges from to strands, depending on the protein and/or its functional role. in eukaryotes, it is known that similar architectures are present in the outer membrane of chloroplasts and mitochondria, although so far none of the so-called "porins", mainly acting as voltage dependent anion channels, have been solved with atomic resolution. it is therefore urgent to devise methods for the prediction of the topology of this class of membrane proteins. indeed the correct prediction of the protein topology, given the conservation of the barrel architecture may greatly help in threading procedures, especially when sequence homology is low. furthermore reliable methods, endowed with a low rate of false positives, can also help in genome annotation on the basis of protein structure prediction. the problem of predicting beta barrel membrane proteins has been recently addressed with machine learning approaches, and among them hidden markov models have been shown to outperform previously existing methods. hmms were developed for alignments, pattern detection and also for predictions, as in the case of the topology of all-alpha and all-beta membrane proteins. when hmms are implemented for predicting a given feature, a decoding algorithm is needed. with decoding we refer to the assignment of a path through the hmm states given an observed sequence o. in this way, we can also assign a label to each sequence element. more generally, as stated in, the decoding is the prediction of the labelsof an unknownpath. the most famous decoding procedure is the viterbi algorithm, which finds the most probable allowed path through the hmm model. viterbi decoding is particularly effective when there is a single best path among others much less probable. when several paths have similar probabilities, the posterior decoding or the 1-best algorithms are more convenient. the posterior decoding assigns the state path on the basis of the posterior probability, although the selected path might be not allowed. in this paper we address the problem of preserving the automaton grammar and concomitantly exploiting the posterior probabilities, without the need of the post-processing algorithm. prompted by this, we design a new decoding algorithm, the posterior-viterbidecoding, which preserves the automaton grammars and at thesame time exploits the posterior probabilities. a related idea, that is specific for pairwise alignments was previously introduced to improve the sequence alignment accuracy. we show that pv performs better than the other algorithms when we test it on the problem of predicting the topology of beta-barrel membrane proteins.  testing the decoding algorithms on all-beta membrane proteins in order to test our decoding algorithm on real biological data, we used a previously developed hmm, devised for the prediction of the topology of beta-barrel membrane proteins. the hidden markov model is a sequence-profile-based hmm and takes advantage of emitting vectors instead of symbols, as described in. since the previously designed and trained hmm emits profile vectors, sequence profiles have been computed from the alignments as derived with psi-blast on the non-redundant database of protein sequences. the results obtained using the four different decoding algorithms are shown in table where the performance is tested with a leave-one-out cross validation procedure for the first proteins and as blind-test for the latter. it is evident that for the problem at hand the viterbi decoding and the 1-best are unreliable, since only one of the proteins is correctly assigned. in this case the posterior decoding is more efficient and can correctly assign 60% and 40% of the proteins, in cross-validation and on the blind set, respectively. here the posterior decoding is used without maxsubseq, introduced before to recast the grammar. from table it evident that the new pv decoding is the best performing decoding achieving 80% and 60% accuracy in cross-validation and on the blind set, respectively. this is done ensuring that predictions are consistent with the designed automaton grammar. comparison with other available hmms in table we show the results of the comparison between our hmm-decoding with those obtained from the available web servers, based on similar approaches. the pred-tmbb server allows the user to test three different algorithms. differently from us they find that their hmm does not show significant differences among the three decoding algorithms. this dissimilar behaviour may be due to several concurring facts: i) the different hmm models, ii) pred-tmbb runs on a single-sequence input, iii) pred-tmbb is trained using the conditional maximum likelihood. the second server proftmb is based on a method that exploits multiple sequence information and posterior probabilities. their decoding is related to the posterior-viterbi; however, in their algorithm the authors first obtained the posterior sum contracted into two possible labeling, then they made use of the explicit value of the hmm transition probabilities. in this way they count the transition probabilities twice and the proftmb performance is not very different from ours. finally, the third server hmmb2tmr achieves a performance quite similar to that obtained with pv decoding. to do that hmmb2tmr takes advantage of the maxsubseq algorithm on top of the posterior sum decoding. however, although maxsubseq is a very general two-class segment optimization algorithm, it is a post processing procedure that has to be applied after a hmm decoding. on the contrary, pv is a general decoding algorithm and it is more useful when the underlying predictor is a hmm, where more than two labels and different constraints can be introduced into the automaton grammars.  the new pv decoding algorithm is more convenient in that it overcomes the difficulties of introducing a problem-dependent optimization algorithm when the automaton grammar is to be re-cast. when one-state-path dominates we may expect that pv does not perform better than the other decoding algorithms, and in these cases the 1-best is preferred. nevertheless, we show that when several concurring paths are present, as in the case of our beta-barrel hmm, pv performs better than the others. although pv takes more time than other algorithms, the pv asymptotic computational time-complexity still remains o as for the other decodings. as far as the memory requirement is concerned, pv needs the same space-complexity of the viterbi and posterior ), while 1-best in the average case requires less memory, and can also be reduced. when computational speed is an issue, viterbi algorithm is the fastest and the time complexity order is time ≤ time ≤ time. finally, pv satisfies any hmm grammar structures, including automata containing silent states, and it is applicable to all the possible hmm models with an arbitrary number of labels and without having to work out a problem-dependent optimization algorithm. 
structure prediction of membrane proteins is still a challenging computational problem. we show that pv decoding performs better than other algorithms when tested on the problem of the prediction of the topology of beta-barrel membrane proteins. the former is very efficient when one path dominates, while the latter, even though does not guarantee to preserve the hmm grammar, is more effective when several concurring paths have similar probabilities. in this paper we introduce the posterior-viterbi a new decoding which combines the posterior and viterbi algorithms. pv is a two step process: first the posterior probability of each state is computed and then the best posterior allowed path through the model is evaluated by a viterbi algorithm. hidden markov models have been successfully applied to the problem of predicting membrane protein topology.
 structure prediction of membrane proteins is still a challenging computational problem. hidden markov models have been successfully applied to the problem of predicting membrane protein topology. in a predictive task, the hmm is endowed with a decoding algorithm in order to assign the most probable state path, and in turn the labels, to an unknown sequence. the viterbi and the posterior decoding algorithms are the most common. the former is very efficient when one path dominates, while the latter, even though does not guarantee to preserve the hmm grammar, is more effective when several concurring paths have similar probabilities. a third good alternative is 1-best, which was shown to perform equal or better than viterbi.  in this paper we introduce the posterior-viterbi a new decoding which combines the posterior and viterbi algorithms. pv is a two step process: first the posterior probability of each state is computed and then the best posterior allowed path through the model is evaluated by a viterbi algorithm.  we show that pv decoding performs better than other algorithms when tested on the problem of the prediction of the topology of beta-barrel membrane proteins. 17– march italian society of bioinformatics: annual meeting milan, italy 