BACKGROUND
transmembrane proteins play several key roles in the human body including inter-cell communication, transportation of nutrients, and ion transport.
they also play key roles in human diseases like depression, hypertension, cancer, thus are targeted by a majority of pharmaceuticals being manufactured today.
the transmembrane proteins are divided into two main types according to their conformation: α-helical bundles and β-barrels .
the tmb proteins, which are much less abundant than helical bundles, are found in the outer membrane of gram-negative bacteria, mitochondria and chloroplasts.
they perform diverse functions such as porins, passive or active transporters, enzymes, defensive or structural proteins  <cit> .
thus, the structure of tmb proteins is very important for both biological and medical sciences.
these proteins, which span the membrane entirely, make up  <dig> - 30% of identified proteins in most whole genomes.
however, due to difficulties in determination of their structures, solved tmb structures constitute only a meagre 2% of the rcsb protein data bank   <cit> .
this is mainly due to experimental difficulties and complexity of the tmb structure  <cit> .
consequently, various learning-based techniques have been developed for discriminating tmb proteins from globular and transmembrane α-helical proteins  <cit> , and for predicting tmb secondary structures  <cit> .
we first discuss these methods and their potential shortcomings in detail, and then proceed with describing our approach.
ou et al.
<cit>  proposed a method based on radial basis function networks to predict the number of β-strands and membrane spanning regions in β-barrel outer membrane proteins.
randall et al.
<cit>  tried to predict the tmb secondary structure with 1d recursive neural network using alignment profiles.
gromiha et al.
<cit>  used the amino acid compositions of both globular and outer membrane proteins  to discriminate omps and developed a feed forward neural network-based method to predict the transmembrane segments.
bagos et al.
<cit>  produced a consensus prediction from different methods based on hidden markov models, neural networks and support vector machines  <cit> .
tractability has been an issue for some of these approaches.
in order to overcome this limitation, waldispühl et al.
<cit>  used a structural model and pairwise interstrand residue statistical potentials derived from globular proteins to predict the supersecondary structure of tmb proteins.
freeman et al.
<cit>  have introduced a statistical approach for recognition of tmb proteins based on known physicochemical properties.
most of these rely on the learning assumptions in the underlying models as well as the sampling of proteins in their training set.
however, the number of tmb proteins known today is tiny.
thus, it is arguable whether these approaches can work well for recognizing and folding tmb proteins which are not homologous to those currently known.
it is also important to note that none of these methods allow for permutations in protein structures.
the tmb structures are not merely a series of β-strands where each is bonded to the preceding and succeeding ones in the primary sequence, but they may contain greek key or jelly roll motifs as well, for instance, the c-terminal domain of the papc usher .
this level of structure may be described as a permutation on the order of the bonded strands.
in this paper, we present a novel ab initio model for classification and structure prediction of tmb proteins based on minimizing free energy in a graph-theoretic framework.
it is able to deal with permuted tmb structures.
the prediction accuracy is evaluated on known tmb proteins available in popular protein databases  <cit> , and compared with existing software  <cit> .
our approach also performs well in structure prediction and the results are comparable to those of the existing algorithms.
ours is the first model that actually gives an insight into the physicochemical model rather than merely classifying or predicting tmb proteins.
the results show that our approach is also good at discriminating tmb proteins.
RESULTS
folding
the folding prediction results are presented in table  <dig> and figure  <dig>  figure  <dig> plots the matthews correlation coefficient for our approach bbp  and tmbpro for different proteins along the x-axis.
the results of our approach are comparable to those of tmbpro but more consistent as we do not rely on training for folding.
we note that, in the cases the program predicts an optimal structure with a wrong number of strands, the optimal energy is really close to the energy of the topologically right structure.
*standard deviation
the tmbetapred-rbf web-server predicted non-tmb for  <dig> over  <dig> proteins of pdbtm <dig>  or  <dig> %.
the structures for correctly identified proteins were completely accurate.
this might be because they were included in the training set.
evaluation of shear numbers
we study the energy distribution of  <dig> tmb structures  in e. coli taken from pdbtm <dig>  with regards to the slant angle, hence the shear number .
most optimal structures incline with an angle of 41° - 49°, as observed in databases.
this suggests that our model performs well the physicochemical properties of tmb structures.
it should be also noted that there is no natural way to define the shear number a priori.
influence of the filtering threshold
we apply the filtering thresholds ρ= <dig>  and 23on ecoli <dig>  these thresholds ensure that on average, considering 3-residue blocks as subunits, each segment is accepted as a β-strand if its propensity to be β-strand is at most  <dig>   <dig>   <dig>  times, respectively, less than its propensity to be other structure .
the observed minor difference in accuracy with such considerably distinguished thresholds reinforces the fair independence of our approach from the training data.
the results in table  <dig> show the strong predicting ability of bbp from a poor known database.
the lower the parameter ρ, the more independent to the training the predictor.
this reduced the prediction performance of the model on the known structures, however, it may be useful to discover new tmb proteins.
*standard deviation
evaluation on mutated sequences
we generate the mutated sequences from ecoli <dig> by substituting the amino acids at turns or loops using the pam <dig> substitution matrix  <cit> .
each sequence in ecoli <dig> is mutated up to 5% of amino acids into  <dig> new sequences.
figures  <dig> and  <dig> show the matthews correlation coefficient and f-score for residues and β-strands.
we observe from these results the stability of our predictions.
it also suggests that the tmb proteins are stable against these mutations at their turns and loops.
the difference in structures of those mutated proteins may merely come from the shift of membrane spanning β-strands when their two extremities are mutated.
permuted structures
for , the c-terminal domain of the papc usher in e. coli, the observed structure topology containing a greek key motif corresponds to the permutation σ =  and is predicted with an accuracy  of  <dig> % at ρ =  <dig> .
following the experimental observations that were published previously on the efficiency of the in vivo membrane assembly of ompa variants  <cit> , we test our algorithm with different given permutations.
ompa  consists of eight β-strands, thus without feasibility being taken into account, there are !
=  <dig> circular permutations to check .
the pseudo-energy  <dig>  of the observed permutation is found in the lowest energy zone.
<dig> permuted structures, or  <dig> %, reach an energy of .
a ratio of about  <dig> % is found in the case of ompx  .
these results are not surprising since a protein may be folded into more than one spatial conformation.
in both cases, a poisson-like distribution is found.
this observation may help to discriminate most of infeasible conformations with the use of a threshold on the global energy.
hence, the method is expected to rapidly find a small set containing the right structure within a threshold of, for instance, 2% from the lowest energy and with structural feasibility conditions on permutations.
this set might be much smaller be refining the biologically plausible permutations.
other proposed solutions in this set may be the candidates for in vivo and in vitro studies.
classification
100% of the non-redundant set of  <dig> α-helical transmembrane proteins of length from  <dig> to  <dig> residues in pdbtm are rejected, whereas  <dig> out of  <dig> non-redundant lipocalins taken from pdb are predicted as non-tmb .
though lipocalins are also β-barrels which reverse the tmb pattern with a hydrophobic core, the environmental effects on both sides of the barrel are still different.
our pseudo-energy model yields unfavorably on such structures and discriminates considerably better than the learning-based methods like freeman-wimley  <cit> , tmbpro  <cit> , pred-tmbb  <cit>  and tmbetapred-rbf  <cit> , but also of transfold  <cit> .
CONCLUSIONS
we have presented a new pseudo-energy minimization method for the classification and prediction of transmembrane protein super-secondary structure based on a variety of potential structures.
our approach takes into account many physicochemical constraints and minimizes the free energy.
it also accounts for permuted structures, thus giving more complete information on the folded structure.
our method is quite accurate with more than 90% sensitivity and f-score, over 80% m.c.c.
score on strands; and over 74% accuracy and f-score on residues.
the results are comparable to those given by tmbpro and tmbetapred-rbf, which are both learning based methods.
moreover, our results are more consistent and have a significantly less variation across different tmb proteins.
this is especially interesting given that our algorithm is based mainly on pseudo-energy minimizations, and the probabilistic model only plays a very small role.
while the model presented here is only for tmb proteins, it can be easily extended to accommodate α-helical bundles.
we did not use a more sophisticated statistical model for classifying β-barrel strands because that would risk overfitting and reliance on the training dataset.
it is also interesting to note that our approach performs very well for identification of tmb proteins, rejecting all the α-helical bundles.
the freeman and wimley  <cit>  approach is more accurate on some datasets.
however, it risks overfitting and does not predict the structure.
therefore, our approach provides the best overall classification results amongst the methods that try to predict structures.
our model does learn the probabilistic model from training dataset, but it is mainly to screen out obvious non-tmb strands.
therefore, there are no concerns about the size of the training data or overfitting.
even though the results presented in this paper are comparable to other methods, the methodology presented here is novel and gives insight into the actual physicochemical constraints and energy.
moreover, our approach should be able to predict tmb proteins which are significantly different from known proteins.
finally, our approach provides more information than the current approaches by providing the permutations of the strands.
future work
we are working on energy models for tm α-helical bundles and β-barrels with broken strands, as well as globular β-barrels like lipocalins or membrane targeting proteins  where permuted structures are usually found.
nevertheless, similar to the other methods, we only propose single-domain protein structures.
we are also currently working on refinements in structural constraints and hydrophobicity, which may help to improve the accuracy of our predicted structure.
finally, it will be interesting to investigate more sophisticated statistical models for the initial screening, both to improve the results and understand how effective a mixed approach can be.

 transmembrane proteins play several key roles in the human body including inter-cell communication, transportation of nutrients, and ion transport. they also play key roles in human diseases like depression, hypertension, cancer, thus are targeted by a majority of pharmaceuticals being manufactured today. the transmembrane proteins are divided into two main types according to their conformation: α-helical bundles and β-barrels. the tmb proteins, which are much less abundant than helical bundles, are found in the outer membrane of gram-negative bacteria, mitochondria and chloroplasts. they perform diverse functions such as porins, passive or active transporters, enzymes, defensive or structural proteins. thus, the structure of tmb proteins is very important for both biological and medical sciences. these proteins, which span the membrane entirely, make up - 30% of identified proteins in most whole genomes. however, due to difficulties in determination of their structures, solved tmb structures constitute only a meagre 2% of the rcsb protein data bank. this is mainly due to experimental difficulties and complexity of the tmb structure. consequently, various learning-based techniques have been developed for discriminating tmb proteins from globular and transmembrane α-helical proteins, and for predicting tmb secondary structures. we first discuss these methods and their potential shortcomings in detail, and then proceed with describing our approach. ou et al. proposed a method based on radial basis function networks to predict the number of β-strands and membrane spanning regions in β-barrel outer membrane proteins. randall et al. tried to predict the tmb secondary structure with 1d recursive neural network using alignment profiles. gromiha et al. used the amino acid compositions of both globular and outer membrane proteins to discriminate omps and developed a feed forward neural network-based method to predict the transmembrane segments. bagos et al. produced a consensus prediction from different methods based on hidden markov models, neural networks and support vector machines. tractability has been an issue for some of these approaches. in order to overcome this limitation, waldispühl et al. used a structural model and pairwise interstrand residue statistical potentials derived from globular proteins to predict the supersecondary structure of tmb proteins. freeman et al. have introduced a statistical approach for recognition of tmb proteins based on known physicochemical properties. most of these rely on the learning assumptions in the underlying models as well as the sampling of proteins in their training set. however, the number of tmb proteins known today is tiny. thus, it is arguable whether these approaches can work well for recognizing and folding tmb proteins which are not homologous to those currently known. it is also important to note that none of these methods allow for permutations in protein structures. the tmb structures are not merely a series of β-strands where each is bonded to the preceding and succeeding ones in the primary sequence, but they may contain greek key or jelly roll motifs as well, for instance, the c-terminal domain of the papc usher. this level of structure may be described as a permutation on the order of the bonded strands. in this paper, we present a novel ab initio model for classification and structure prediction of tmb proteins based on minimizing free energy in a graph-theoretic framework. it is able to deal with permuted tmb structures. the prediction accuracy is evaluated on known tmb proteins available in popular protein databases, and compared with existing software. our approach also performs well in structure prediction and the results are comparable to those of the existing algorithms. ours is the first model that actually gives an insight into the physicochemical model rather than merely classifying or predicting tmb proteins. the results show that our approach is also good at discriminating tmb proteins.  folding the folding prediction results are presented in table and figure figure plots the matthews correlation coefficient for our approach bbp and tmbpro for different proteins along the x-axis. the results of our approach are comparable to those of tmbpro but more consistent as we do not rely on training for folding. we note that, in the cases the program predicts an optimal structure with a wrong number of strands, the optimal energy is really close to the energy of the topologically right structure. *standard deviation the tmbetapred-rbf web-server predicted non-tmb for over proteins of pdbtm or %. the structures for correctly identified proteins were completely accurate. this might be because they were included in the training set. evaluation of shear numbers we study the energy distribution of tmb structures in e. coli taken from pdbtm with regards to the slant angle, hence the shear number. most optimal structures incline with an angle of 41° - 49°, as observed in databases. this suggests that our model performs well the physicochemical properties of tmb structures. it should be also noted that there is no natural way to define the shear number a priori. influence of the filtering threshold we apply the filtering thresholds ρ= and 23on ecoli these thresholds ensure that on average, considering 3-residue blocks as subunits, each segment is accepted as a β-strand if its propensity to be β-strand is at most times, respectively, less than its propensity to be other structure. the observed minor difference in accuracy with such considerably distinguished thresholds reinforces the fair independence of our approach from the training data. the results in table show the strong predicting ability of bbp from a poor known database. the lower the parameter ρ, the more independent to the training the predictor. this reduced the prediction performance of the model on the known structures, however, it may be useful to discover new tmb proteins. *standard deviation evaluation on mutated sequences we generate the mutated sequences from ecoli by substituting the amino acids at turns or loops using the pam substitution matrix. each sequence in ecoli is mutated up to 5% of amino acids into new sequences. figures and show the matthews correlation coefficient and f-score for residues and β-strands. we observe from these results the stability of our predictions. it also suggests that the tmb proteins are stable against these mutations at their turns and loops. the difference in structures of those mutated proteins may merely come from the shift of membrane spanning β-strands when their two extremities are mutated. permuted structures for, the c-terminal domain of the papc usher in e. coli, the observed structure topology containing a greek key motif corresponds to the permutation σ = and is predicted with an accuracy of % at ρ =. following the experimental observations that were published previously on the efficiency of the in vivo membrane assembly of ompa variants, we test our algorithm with different given permutations. ompa consists of eight β-strands, thus without feasibility being taken into account, there are! = circular permutations to check. the pseudo-energy of the observed permutation is found in the lowest energy zone. permuted structures, or %, reach an energy of. a ratio of about % is found in the case of ompx. these results are not surprising since a protein may be folded into more than one spatial conformation. in both cases, a poisson-like distribution is found. this observation may help to discriminate most of infeasible conformations with the use of a threshold on the global energy. hence, the method is expected to rapidly find a small set containing the right structure within a threshold of, for instance, 2% from the lowest energy and with structural feasibility conditions on permutations. this set might be much smaller be refining the biologically plausible permutations. other proposed solutions in this set may be the candidates for in vivo and in vitro studies. classification 100% of the non-redundant set of α-helical transmembrane proteins of length from to residues in pdbtm are rejected, whereas out of non-redundant lipocalins taken from pdb are predicted as non-tmb. though lipocalins are also β-barrels which reverse the tmb pattern with a hydrophobic core, the environmental effects on both sides of the barrel are still different. our pseudo-energy model yields unfavorably on such structures and discriminates considerably better than the learning-based methods like freeman-wimley, tmbpro, pred-tmbb and tmbetapred-rbf, but also of transfold.  we have presented a new pseudo-energy minimization method for the classification and prediction of transmembrane protein super-secondary structure based on a variety of potential structures. our approach takes into account many physicochemical constraints and minimizes the free energy. it also accounts for permuted structures, thus giving more complete information on the folded structure. our method is quite accurate with more than 90% sensitivity and f-score, over 80% m.c.c. score on strands; and over 74% accuracy and f-score on residues. the results are comparable to those given by tmbpro and tmbetapred-rbf, which are both learning based methods. moreover, our results are more consistent and have a significantly less variation across different tmb proteins. this is especially interesting given that our algorithm is based mainly on pseudo-energy minimizations, and the probabilistic model only plays a very small role. while the model presented here is only for tmb proteins, it can be easily extended to accommodate α-helical bundles. we did not use a more sophisticated statistical model for classifying β-barrel strands because that would risk overfitting and reliance on the training dataset. it is also interesting to note that our approach performs very well for identification of tmb proteins, rejecting all the α-helical bundles. the freeman and wimley approach is more accurate on some datasets. however, it risks overfitting and does not predict the structure. therefore, our approach provides the best overall classification results amongst the methods that try to predict structures. our model does learn the probabilistic model from training dataset, but it is mainly to screen out obvious non-tmb strands. therefore, there are no concerns about the size of the training data or overfitting. even though the results presented in this paper are comparable to other methods, the methodology presented here is novel and gives insight into the actual physicochemical constraints and energy. moreover, our approach should be able to predict tmb proteins which are significantly different from known proteins. finally, our approach provides more information than the current approaches by providing the permutations of the strands. future work we are working on energy models for tm α-helical bundles and β-barrels with broken strands, as well as globular β-barrels like lipocalins or membrane targeting proteins where permuted structures are usually found. nevertheless, similar to the other methods, we only propose single-domain protein structures. we are also currently working on refinements in structural constraints and hydrophobicity, which may help to improve the accuracy of our predicted structure. finally, it will be interesting to investigate more sophisticated statistical models for the initial screening, both to improve the results and understand how effective a mixed approach can be. 
transmembrane β-barrel proteins are a special class of transmembrane proteins which play several key roles in human body and diseases. the ab initio model presented in this paper is the first method to allow for permutations in the structure of transmembrane proteins and provides more structural information than any known algorithm. the results are comparable to other algorithms suggesting that our pseudo-energy model is close to the actual physical model. this model folds proteins based on energy minimization rather than a homology search, avoiding any assumption on availability of training dataset. the model is also able to recognize β-barrels by assessing the pseudo free energy. over the years, a number of learning-based methods have been introduced for recognition and structure prediction of transmembrane β-barrel proteins. we present a novel graph-theoretic model for classification and structure prediction of transmembrane β-barrel proteins. we assess the structure prediction on proteins gathered from existing databases on experimentally validated transmembrane β-barrel proteins. we show that it is possible to design models for classification and structure prediction for transmembrane β-barrel proteins which do not depend essentially on training sets but on combinatorial properties of the structures to be proved. due to experimental difficulties, the number of transmembrane β-barrel proteins with known structures is very small. we test our classification approach and show that it is able to reject α-helical bundles with 100% accuracy and β-barrel lipocalins with 97% accuracy.
 transmembrane β-barrel proteins are a special class of transmembrane proteins which play several key roles in human body and diseases. due to experimental difficulties, the number of transmembrane β-barrel proteins with known structures is very small. over the years, a number of learning-based methods have been introduced for recognition and structure prediction of transmembrane β-barrel proteins. most of these methods emphasize on homology search rather than any biological or chemical basis.  we present a novel graph-theoretic model for classification and structure prediction of transmembrane β-barrel proteins. this model folds proteins based on energy minimization rather than a homology search, avoiding any assumption on availability of training dataset. the ab initio model presented in this paper is the first method to allow for permutations in the structure of transmembrane proteins and provides more structural information than any known algorithm. the model is also able to recognize β-barrels by assessing the pseudo free energy. we assess the structure prediction on proteins gathered from existing databases on experimentally validated transmembrane β-barrel proteins. we show that our approach is quite accurate with over 90% f-score on strands and over 74% f-score on residues. the results are comparable to other algorithms suggesting that our pseudo-energy model is close to the actual physical model. we test our classification approach and show that it is able to reject α-helical bundles with 100% accuracy and β-barrel lipocalins with 97% accuracy.  we show that it is possible to design models for classification and structure prediction for transmembrane β-barrel proteins which do not depend essentially on training sets but on combinatorial properties of the structures to be proved. these models are fairly accurate, robust and can be run very efficiently on pc-like computers. such models are useful for the genome screening. 3- february first ieee international conference on computational advances in bio and medical sciences orlando, fl, usa 