BACKGROUND
from the very beginning of modern biology, which can be traced to the 1950s when the structure of the dna was unveiled, linguistic metaphors were readily used to describe the molecular world.
linguistics itself experienced a revolution led by noam chomsky in the second half of 20th century  <cit> .
in the 1980s his work regarding mathematical theory of language was adopted in the field of molecular biology by several researchers  <cit> .
many similarities between natural languages and the language of nature have been revealed.
for instance, any functional polypeptide can be regarded as syntactically proper.
however, similarly to natural languages, where a correct grammatical structure does not imply that a sentence is meaningful, not all amino acid chains fold into proteins with physiological functions.
according to the linguistic level of the analysis, computational tools utilised in biochemistry can be divided into those operating at the lexical, structural, semantic and pragmatic levels  <cit> .
the first level is occupied by algorithms providing statistical analysis  <cit> .
structural or syntax features are examined by software which parse sequences  <cit> .
the embedded ambiguity of structures, as well as flexibility and versatility are among the advantages of this approach.
recently, an increasing amount of linguistic methods with a probabilistic component has been investigated at the structural level, i.e.
hidden markov models  <cit>  and stochastic context-free grammars  <cit> .
at the semantic level a representation of meaning is assigned to the structure  <cit>  and at the pragmatic level some context of the sequence  is taken into account.
in the field of protein sequence analysis, the size of the alphabet and the complexity of relationships between amino acids have mainly limited the application of formal language theory to the production of grammars whose expressive power is not higher than stochastic regular grammars.
the first rules were designed to define short functional patterns consisting of adjacent and well conserved amino acids.
they are expressed by non-probabilistic regular grammars, e.g.
prosite patterns  <cit>  and prints  <cit> .
although their expressive power is fairly limited, they have proved extremely useful in protein annotation and detection of important protein regions  by highlighting short sub-sequences associated to biochemical functions.
approaches based on hidden markov models  are regarded as the state of the art methods in the field of protein sequence annotation.
specifically, profile hmms, which were introduced by krogh et al.
<cit> , are widely used and proved their efficiency for representing motifs, calculating multiple alignments, and profile analysis  <cit> .
however, an important drawback of hmm profiles is that they are not human-readable and, therefore, these descriptors cannot provide any biological insight by themselves.
in addition, since the expressive power of an hmm is similar to a stochastic regular grammar  <cit> , they have limitations regarding the types of patterns they are able to encode.
for example, they cannot cover any higher-order dependencies such as nested and crossing relationships that are common in proteins, e.g.
anti-parallel β-sheets and parallel β-sheets respectively  <cit> .
similarly, bonds in binding sites often exceed the capability of regular grammars and hmms  <cit> .
attempts to produce systems with an increased expressive power have been limited  <cit>  and, according to our knowledge, the only practical tool dedicated to protein analysis was built using stochastic tree grammars to predict both anti-parallel and parallel β-sheets  <cit> .
these weakly context-sensitive grammars could not only predict which amino acids were involved in sheets, but also the locations of the hydrogen bonds.
however, the structure of the grammar had to be provided; their algorithm learned the probability parameters.
context free grammars  have the potential to overcome some of the limitations of hmm based schemes since they have the next level of expressiveness in chomsky's classification and produce human-readable descriptors.
although they do not have the power of context-sensitive grammars and, therefore, cannot deal with crossing relationships, their reduced complexity makes them more practical and allows the possibility of learning grammar structure from examples.
consequently, they could potentially be used to describe a variety of patterns including nested relationships.
anti-parallel β-sheets are natural candidates, see figure 1a).
moreover, we believe that many ligand binding sites, where main dependencies are essentially branched and nested like, could be detected using cfgs.
these relationships are often not direct interactions between amino acids, but indirect through the intermediate of a ligand.
for example, the nap  binding region of aldo-keto reductases, see figure 1b), could be modelled as involving indirect nested dependencies between nap binding residues, figure 1c).
moreover, cfgs can be utilised to model dependencies between different parts of a binding site, such as beta strands, helices and loops, by using branching rules.
thus, the development of grammars which have the abilities to model branched and nested relationships should permit to improve modelling of such type of binding sites.
cfg have already been applied successfully in the fields of bioinformatics, particularly for rna structure prediction  <cit>  and compression  <cit> .
a cfg is particularly adapted to this task because it can express, unlike regular grammar, the nested dependencies due to the watson-crick pairing which is key to rna structure.
due to a larger set of terminals  and less straightforward relations between residues , utilisation of context-free grammars to analyse proteins has not been, so far, comparably successful.
since the design of an unbiased negative sample is particularly difficult in protein sequence analysis, the fact that cfgs cannot be inferred from positive data only is a serious drawback  <cit> .
an alternative is to develop an approach based on stochastic grammars which, in principle, do not require a negative set for their inference  <cit> .
in this paper, a stochastic context free grammar based framework for the analysis of protein sequences is presented and applied to the interpretation and detection of amino acids involved in binding sites.
we start by demonstrating the value of our framework by showing the biological insight which is provided by the produced grammars.
then, we assess its performance in sequence annotation and binding site detection and evaluate them against profile hmms.
in the methods section, we present the general principles which are behind our framework and the key strategies it relies on.
formal definition of stochastic context free grammars, implementation aspects and detailed description of datasets are provided in the appendix.
RESULTS
description of datasets
we evaluate our framework using a set of binding site patterns which are based on prosite entries  <cit> .
they vary in term of size and complexity and include prosite patterns and domain profile, as well as a zinc finger 'meta-pattern' that was derived from  <dig> zinc finger prosite patterns .
the negative test set is defined as a representative set  of all protein sequences available in the protein data bank   <cit> .
a complete description of these datasets is provided in appendix e.
analysis of grammar structures
the rational for utilising stochastic context free grammars to produce ligand binding site descriptors is that not only they have the power to express branched and nested like dependencies, but also their rules can be analysed to acquire biological knowledge about binding sites of interest.
in this section, we illustrate how analysis of sequence based scfgs allows gaining an insight into the spatial configuration of binding sites.
we propose two ways of analysing probabilistic grammars to extract biologically meaningful features focusing on either parse trees or grammar rules.
we start by providing an in-depth study of grammars produced to describe the extended ps <dig> pattern which include calcium and manganese binding sites.
through this analysis, we will use the 3d structure of a legume lectin protein, i.e.
1fat, to visualise the structure of the site and its description as provided by the grammar parse trees.
we will focus our attention on grammars based on residue accessibility, calcium propensity and manganese propensity, since these grammars have been shown as being the most informative to describe the ps <dig> pattern.
figure 2a) shows the 3d structure of the extended ps <dig> pattern.
figure 2b) displays hydrogen-bonds involved in ligand binding and beta sheet which exhibit anti-parallel β-sheet type relationships.
the grammar generated for this pattern based on accessibility is composed of the following rules associated with their normalized probability.
p, z and n express respectively high, average and low accessibility.
a → bc rules:
s → ts  | vp
t → xu
u → nz  | zz
v → pn  | pz
w → zp  | tu
x → vw
a → a rules:
a/l r/k n/m d/f c/p q/s e/t g/w h/y i/v
n:  <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
<dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
z:  <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
<dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
p:  <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
<dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig>
as shown on the grammar parse tree, see figure 3b), there is a set of context free rules t→xu, x→vw, w→tu which is repeated to elongate the tree.
moreover, the derivation of x→vw is v→pn|pz.
since all amino acids which show high accessibility propensity, i.e.
l, m, f, c, w, i and v, have also high beta sheet propensity  <cit> , the v rule is beta strand friendly.
therefore, this grammar imposes a constraint between the length of the loop and the first beta strand, see figure 3a).
similarly, the rule s → vp associated with v → pn|pz is right-hand side strand friendly, which defines the second beta sheet, see figure 3a) &3b).
whereas the accessibility based grammar describes in particular the beta sheet which is present in the pattern, the magnesium propensity based grammar deals with magnesium binding.
rules of the 'a → bc' type for this grammar are the following:
s → vn  | vz
t → zu
u → xn  | tz  | tw
v → ns  | xw  | vu
w → np  | zp  | xw
x → zw
where p, z and n express respectively high, average and low magnesium binding propensity.
the parse tree of this grammar reveals the magnesium binding site is divided between strand and loop parts at v → vu branching rule, see figure 4a), 4b) &4c).
the derivations of v on the strand side and u on the loop side impose the presence of w rules.
since any w rule derivation exits with w → np|zp, which is magnesium binding friendly, both sides of the magnesium binding sites must include magnesium binding residues.
finally, the calcium propensity based grammar defines not only the calcium binding part of the pattern, but more generally the pattern's structure.
'a → bc' type grammar rules are the following:
s → tw  | xs
t → tw  | xw
u → zp
v → vu  | zz
w → vw  | vz  | pn
x → vu  | xu
where p, z and n express respectively high, average and low calcium binding propensity.
the parse tree of this grammar decomposes neatly the site in four parts: beta <dig>  ca binding loop, beta <dig> and rest of the loop, see figure 5a), 5b) &5c).
the second way of reading grammars, namely analysis of highly probable production chains and especially cycles, is demonstrated on the nap binding pattern ps <dig> which is found in some aldo- and ketoreductases.
the protein structure of 1mrq is used for illustration .
rules of the 'a → bc' type for the nap propensity grammar for this pattern are the following:
s → zu  | sz
t → pv  | tz
u → zt  | uz
v → pu  | vz  | sp  |
v → zp  | np
where p, z and n express respectively high, average and low nap propensity.
for this grammar, there exist two cyclic rule chains of high probability  which start from non-terminal t.
cycle a defines a nap binding fragment consisting of two consecutive amino acids of high nap propensity.
this corresponds to the well conserved lys <dig> and ser <dig> of 1mrq, which are seen in orange in figure  <dig>
since the termination of any derivation of this grammar imposes either v→np or v→zp rules and another t→pv production  is required to end the cycle b, the shortest parse tree terminating cycle b  would display the following pattern 'pzzpypp', where y represents either z or n. residues of high nap propensity show a 'i → i+3' periodicity which could suggest the presence of a nap binding site involving an alpha helix.
the derivation tree of 1mrq shows that compared to the shortest predicted parse tree, the recursive rule t→tz is used to extend the original pattern to 'pzzpzpzp'  which corresponds to the substring 'neqrirqn'.
analysis of the pdb model confirms this pattern defines a helix.
moreover, asn <dig>  arg <dig> and asn <dig>  which are seen in blue in figure  <dig>  are indeed very close to the ligand and provide an nap binding environment.
ligplot data  <cit>  show that arg <dig>  and asn <dig> are actually involved in the bound state of the molecule.
finally, we analyse the so <dig> binding site associated to ps <dig> profile of m-phase inducer  phosphatase using both parse trees and grammar rules.
this region is illustrated using cartoon and stick 3d models of 1cws .
the parse tree of the accessibility based grammar for the region is shown in figure 8a).
this tree shows a strong asymmetry with a mainly hydrophilic left side and a hydrophobic right side.
this suggests very different structural properties between these parts of binding site.
figure 7a) reveals a beta-sheet on the left and an alpha-helix plus one disturbed but clear turn on the right.
in addition to these features which could have been obtained using standard secondary structure prediction methods, the parse tree also highlights the creation of a hydrophilic environment between the right side hydrophilic amino acids close to the tree root  and the left side amino acids.
this is confirmed in figure 7b) where the side chains of right hand side cys <dig> and ile <dig> are directed towards the beta sheet.
using the parse tree of the so <dig> propensity based grammar , some insight can be provided regarding so <dig> binding.
contrarily to the hydrophilic side of the site which is composed of residues showing low so <dig> propensity, the hydrophobic side appears as a good candidate for so <dig> binding.
more specific information can be obtained through the analysis of the so <dig> propensity based grammar whose rules of type 'a → bc' are as follows:
s → tw
t → xw  | nu  | nz
u → xz  | xn  | xp
v → np  | zp  | nz
w → vz  | vp
x → zs  | ns
where p, z and n express respectively high, average and low so <dig> binding propensity.
two most probably cyclic chains are as follows:
where the most likely derivation of w is: w → vz and v → n|z p
from cycle a, the following pattern is revealed: 'ysypzypz', where y represents either z or n. since s can be substituted by the pattern itself, after a substitution the patterns become 'yysypzypzypzypz'.
this shows a 'i→i+3' periodicity of so4-friendly residues which is consistent with the presence of an alpha-helix.
in addition, the derivation of the less likely cycle b produces the following pattern: 'nysxypz' where x represents any so <dig> propensity.
then, if s is substituted by the pattern coded in cycle a, the new pattern models a 'i→i+3/i+4' periodicity, 'nyysypzypzxypz', which is also typical for helices.
this result combined with the low so <dig> propensity of the hydrophobic side of the binding site suggests that so <dig> binding would involve the arginine-rich ridge of a helix.
this is confirmed by ligplot which shows that arg <dig> and arg <dig> are involved in so <dig> binding.
this analysis of grammars describing ligand binding sites has shown that probabilistic context-free grammars allow the production of binding site descriptors which are human-readable and, hence, provide some insight into biologically meaningful features.
moreover, each of these grammars relies on high probability rules which could not be expressed with regular grammars.
therefore, this confirms that the description of many ligand binding sites benefits from the expressive power of context free grammars.
stochastic context-free grammars for sequence annotation and binding site detection
in order to demonstrate that, not only scfg based descriptors are meaningful, but are powerful at both annotating sequences and detecting binding sites, we first evaluate them on sites which can be expressed quite successfully by a prosite pattern.
in this section, all results are produced using grammars containing a full set of rules.
since each scfg deals with one amino acid property at a time, scores obtained by several grammars need to be combined to obtain optimal results .
table  <dig> shows tp and tn rates for grammars based on different properties, their combinations and their comparison with scores obtained by prosite patterns.
this short pattern - only  <dig> residues - is the anion exchanger pattern .
the table reveals that charge and van der waals volume are important features for the expression of this binding site.
moreover, scfgs allows detecting relevant sequences missed by the prosite pattern.
since each scfg deals with one amino acid property at a time, scores obtained by several grammars need to be combined to obtain optimal results .
table  <dig> shows tp and tn rates for grammars based on different properties, their combinations and their comparison with scores obtained by prosite patterns.
this short pattern - only  <dig> residues - is the anion exchanger pattern .
the table reveals that charge and van der waals volume are important features for the expression of this binding site.
moreover, scfgs allows detecting relevant sequences missed by the prosite pattern.
a more complete performance analysis of different grammars  is provided in table  <dig> for ps <dig> in terms of precision, recall and maximum f <dig> is shown.
we also provide in figure  <dig> the receiver operating characteristic .
since negative-to-positive ratios in our datasets are quite high , roc curves may present an optimistic assessment of the performances of our framework.
therefore, we also show in figure  <dig> a recall-precision curve   <cit>  which has been proposed as a better alternative  <cit> .
although accessibility and, ca and mn propensity are key properties of the residues involved in this binding site, they need to be combined to produce good results.
results obtained for ps <dig> pattern by using scfgs are near perfect.
pattern ps <dig> appeared to be more difficult, but recall for 100%precision is still very high  <dig> .
the results for combined grammars are also very good for ps00063: recall of  <dig>  for  <dig>  precision and maximum f <dig> of  <dig>  .
only 69% of sequences in the positive set are recognised without fp.
this slightly worse result can be explained by the fact that unlike the two other patterns, the pattern covers only a part of the binding site to relatively huge nap molecule.
therefore many key dependencies were not available to the grammars.
since correct annotation does not imply correct detection, both tests - annotation and detection - are necessary to prove the functionality of the approach.
in order to evaluate capabilities of detection, a number of tests were carried out.
in table  <dig> results for ps <dig> for the combined grammar most successful in annotation task are shown.
detection : the peak is expected to be exactly at the position of the pattern; detection : the peak is expected to be no longer distance than 50% of the pattern length
as an outcome of this evaluation, performance of detection appears to be good.
in the most difficult task, where the highest peak was demanded to be exactly at the position of the pattern, success rate was 75%.
when 50% coverage, i.e.
<dig> residues displacement for ps <dig>  was allowed, success rate rose to 100%.
similar outcomes were obtained for the other patterns where detection results were in line with annotation results.
to conclude, our system managed to achieve good accuracy in both annotation and detection.
the results confirmed suitability of our approach in integrating amino acid properties in our grammars and combining obtained grammars.
it shows that these strategies together with appropriate choice of the properties relevant to the pattern provide satisfactory solutions to the requirement of alphabet size reduction.
the remaining part of this paper will only show annotation results since it makes comparisons with profile hmm performances easier.
constrained grammar evaluation
in this section we evaluate the approach consisting on constraining the initial grammar structure as described in the methods section.
it imposes a bias in the grammars so that they use context-free features and it allows increasing the number of non-terminal while keeping a manageable total number of rules .
comparisons between performances obtained by scfgs with a full set of rules - standard scfg - and a constrained set - nestednt scfg - is provided in table  <dig> where results regarding annotation task for ps <dig>  ps <dig>  mpi phosphatase and zinc finger meta-patterns are provided.
nestednt scfgs performed consistently better than standard scfgs, especially concerning recall for 100%precision.
these results suggest that increasing the number of non-terminals allows improving performance by increasing expressive capabilities.
analysis of parse trees shows that more than  <dig> independent nts would be required to cover all important structural features.
moreover, examination of grammar structures produced with different parameters confirmed that constrained grammars were more consistent in their structure than standard scfgs.
performance comparison of scfgs with profile hmms
since we have already demonstrated that unlike hmm profiles, rules of scfg are human readable and can be used to gain some biological insight about binding sites, in this section comparison between the two techniques is limited to annotation results.
as ps <dig>  ps <dig> and ps <dig> patterns were optimised for prosite, this method has an intrinsic advantage compared to profile hmms and scfgs for these patterns in this experiment.
moreover, since mpi phosphatases are a subset of rhodanese-like proteins which can be expressed by a domain profile , it is expected that profile hmms would perform well in annotating this family.
since prosite scores are calculated using the whole swiss-prot/trembl database, comparison with other methods based on precision and therefore f <dig> statistics may not be fair.
therefore, we use recall for 100%precision of profile hmms and pcfgs, and prosite recall to evaluate prosite performance against the others.
table  <dig> shows comparison of results between the methods for our patterns of interest.
as expected, although scfgs scores are generally good, prosite and profile hmms outperform scfgs when dealing with standard prosite patterns.
ps <dig> is an exception where scfgs obtain perfect score.
results achieved by profile hmm and scfg for mpi phosphatase pattern are very similar, with the former only slightly superior over the latter.
in the case of the zinc finger meta-pattern, table  <dig> does not reveal any significant difference between performances of profile hmms and scfgs.
these results validate our assumption that scfgs gain efficiency from higher expressiveness and, despite operating on a reduced protein alphabet, can be at least as efficient as lower-level grammars, i.e.
prosite patterns and profile hmms, built on sequences of amino acid identities.
to investigate further the meta-pattern results, roc and rpc are provided in figure  <dig> and  <dig>
these curves show that although our stochastic grammars are based here on a single feature - zinc propensity - they perform slightly better than profile hmms.
although none of the other tested properties allowed improving scfgs results, we believe there is still some space for improvement if suitable properties could be combined to zinc propensity.
study of false negatives produced by these two methods at their maximum performance level in the term of f <dig>  shows  <dig> sequences were rejected by scfg while  <dig> by profile hmm.
since only  <dig> sequences belonged to both groups, this seems to confirm both schemes have very different definitions of this binding site which might be regarded as complementary.
discussion
this study demonstrates the capability of the framework we propose to take advantage of the expressive power of stochastic context free grammar for analysis of protein sequences.
first, we have shown with a few examples that the analysis of sequence based scfg rules allows gaining an insight into the 3d structure of binding sites.
this is a unique feature of our approach compared to, for example, hmm based methods which only produce 'black box' descriptors.
our analysis of grammar structures has revealed that the ability of expressing branched and nested dependencies is essential to describe some binding sites which can be seen as displaying such relationships through the intermediate of a ligand.
this confirms the theoretical potential of our method in describing sites which are out of the scope of hmm profiles.
it is important to be aware that many sites, such as parallel β-sheets, display dependencies which are beyond the expressiveness of scfgs and, therefore, are not suitable candidates for our approach.
secondly, we have demonstrated that our scfg based system can be practical and accurate to annotate proteins and detect binding site patterns.
this confirms that the various strategies developed to deal with the challenge of using scfgs for proteins sequences were appropriate.
our approach of integrating quantitative properties of amino acids into the scfg framework has shown to be an efficient method to reduce the size of grammars.
moreover, properties based on ligand propensity were especially useful.
in addition, combining grammars typically yielded in better scores than those obtained by any single property grammar.
furthermore, experimentations, where grammar structures are constrained, suggest that restricting the grammar induction search space using heuristics is an approach which merits further investigation.
results show that our approach usually does not perform as well as profile hmms in annotation task when dealing with binding sites which can be well expressed with rigid regular grammars.
this can be explained by the fact our scheme relies on a reduced amount of information, i.e.
amino acid properties instead of amino acid identities,
the main benefit of the system we propose is that - when considering only rules with significant probabilities - both structure and rule probabilities of context-free grammars are learned automatically without introducing constraints specific to the targeted sites.
such grammars of relatively simple structure are human-readable; hence they could become valuable sources of information for molecular biologists.
another advantage of our framework is that, unlike other methods, it does not rely on sequence alignments.
therefore, as encouraging results with zinc finger meta-pattern suggest, our system may be particularly suited to deal with patterns shared by non-homologous proteins.
CONCLUSIONS
we have presented a novel stochastic context-free grammars based framework relying on quantitative representation of amino acid properties.
the scfg based system for protein sequence analysis was tested on several data samples in various configurations.
first, we have shown the produced binding site descriptors are human-readable and their analysis can provide biological insight into the structures of their associated binding sites.
to our knowledge, no other type of binding site descriptors can reveal subtle interactions as described by scfgs.
secondly, by achieving high precision and recall in annotation and very good detection rates our system proved to be a practical tool for protein pattern recognition.
moreover, results for the zinc finger meta-pattern which outperformed profile hmms suggest that meta-patterns are one of the fields where application of scfgs can be especially useful.
in addition, since both approaches produced different false negative, scfgs can be seen as complementary to existing profile hmm based methods.
this suggests our scfg framework could be used to improve those methods.
this study also supports the idea that binding site regions which could be seen as involving indirect nested dependencies between residues are prime targets for our framework.
an increase of the number of non-terminal symbols allows representing a larger variety of relations within a binding site.
additional constraints to grammars enable the use of more symbols and facilitate the learning process.
indeed, our experiment showed that, generally, constrained grammars produced better results.
for future work, we intend to further our research into constrained grammars by inferring optimal grammar structure.
we will also implement secondary structure based grammars to take advantage of this higher level property.
furthermore, our procedure of grammar combination will be refined by customising each grammar's weight to reflect the entropy of underlying properties in the training samples and single grammar performance.
finally, we plan to develop a web tool allowing interactive analysis of binding sites encoded by scfg based descriptors.

 from the very beginning of modern biology, which can be traced to the 1950s when the structure of the dna was unveiled, linguistic metaphors were readily used to describe the molecular world. linguistics itself experienced a revolution led by noam chomsky in the second half of 20th century. in the 1980s his work regarding mathematical theory of language was adopted in the field of molecular biology by several researchers. many similarities between natural languages and the language of nature have been revealed. for instance, any functional polypeptide can be regarded as syntactically proper. however, similarly to natural languages, where a correct grammatical structure does not imply that a sentence is meaningful, not all amino acid chains fold into proteins with physiological functions. according to the linguistic level of the analysis, computational tools utilised in biochemistry can be divided into those operating at the lexical, structural, semantic and pragmatic levels. the first level is occupied by algorithms providing statistical analysis. structural or syntax features are examined by software which parse sequences. the embedded ambiguity of structures, as well as flexibility and versatility are among the advantages of this approach. recently, an increasing amount of linguistic methods with a probabilistic component has been investigated at the structural level, i.e. hidden markov models and stochastic context-free grammars. at the semantic level a representation of meaning is assigned to the structure and at the pragmatic level some context of the sequence is taken into account. in the field of protein sequence analysis, the size of the alphabet and the complexity of relationships between amino acids have mainly limited the application of formal language theory to the production of grammars whose expressive power is not higher than stochastic regular grammars. the first rules were designed to define short functional patterns consisting of adjacent and well conserved amino acids. they are expressed by non-probabilistic regular grammars, e.g. prosite patterns and prints. although their expressive power is fairly limited, they have proved extremely useful in protein annotation and detection of important protein regions by highlighting short sub-sequences associated to biochemical functions. approaches based on hidden markov models are regarded as the state of the art methods in the field of protein sequence annotation. specifically, profile hmms, which were introduced by krogh et al., are widely used and proved their efficiency for representing motifs, calculating multiple alignments, and profile analysis. however, an important drawback of hmm profiles is that they are not human-readable and, therefore, these descriptors cannot provide any biological insight by themselves. in addition, since the expressive power of an hmm is similar to a stochastic regular grammar, they have limitations regarding the types of patterns they are able to encode. for example, they cannot cover any higher-order dependencies such as nested and crossing relationships that are common in proteins, e.g. anti-parallel β-sheets and parallel β-sheets respectively. similarly, bonds in binding sites often exceed the capability of regular grammars and hmms. attempts to produce systems with an increased expressive power have been limited and, according to our knowledge, the only practical tool dedicated to protein analysis was built using stochastic tree grammars to predict both anti-parallel and parallel β-sheets. these weakly context-sensitive grammars could not only predict which amino acids were involved in sheets, but also the locations of the hydrogen bonds. however, the structure of the grammar had to be provided; their algorithm learned the probability parameters. context free grammars have the potential to overcome some of the limitations of hmm based schemes since they have the next level of expressiveness in chomsky's classification and produce human-readable descriptors. although they do not have the power of context-sensitive grammars and, therefore, cannot deal with crossing relationships, their reduced complexity makes them more practical and allows the possibility of learning grammar structure from examples. consequently, they could potentially be used to describe a variety of patterns including nested relationships. anti-parallel β-sheets are natural candidates, see figure 1a). moreover, we believe that many ligand binding sites, where main dependencies are essentially branched and nested like, could be detected using cfgs. these relationships are often not direct interactions between amino acids, but indirect through the intermediate of a ligand. for example, the nap binding region of aldo-keto reductases, see figure 1b), could be modelled as involving indirect nested dependencies between nap binding residues, figure 1c). moreover, cfgs can be utilised to model dependencies between different parts of a binding site, such as beta strands, helices and loops, by using branching rules. thus, the development of grammars which have the abilities to model branched and nested relationships should permit to improve modelling of such type of binding sites. cfg have already been applied successfully in the fields of bioinformatics, particularly for rna structure prediction and compression. a cfg is particularly adapted to this task because it can express, unlike regular grammar, the nested dependencies due to the watson-crick pairing which is key to rna structure. due to a larger set of terminals and less straightforward relations between residues, utilisation of context-free grammars to analyse proteins has not been, so far, comparably successful. since the design of an unbiased negative sample is particularly difficult in protein sequence analysis, the fact that cfgs cannot be inferred from positive data only is a serious drawback. an alternative is to develop an approach based on stochastic grammars which, in principle, do not require a negative set for their inference. in this paper, a stochastic context free grammar based framework for the analysis of protein sequences is presented and applied to the interpretation and detection of amino acids involved in binding sites. we start by demonstrating the value of our framework by showing the biological insight which is provided by the produced grammars. then, we assess its performance in sequence annotation and binding site detection and evaluate them against profile hmms. in the methods section, we present the general principles which are behind our framework and the key strategies it relies on. formal definition of stochastic context free grammars, implementation aspects and detailed description of datasets are provided in the appendix.  description of datasets we evaluate our framework using a set of binding site patterns which are based on prosite entries. they vary in term of size and complexity and include prosite patterns and domain profile, as well as a zinc finger'meta-pattern' that was derived from zinc finger prosite patterns. the negative test set is defined as a representative set of all protein sequences available in the protein data bank. a complete description of these datasets is provided in appendix e. analysis of grammar structures the rational for utilising stochastic context free grammars to produce ligand binding site descriptors is that not only they have the power to express branched and nested like dependencies, but also their rules can be analysed to acquire biological knowledge about binding sites of interest. in this section, we illustrate how analysis of sequence based scfgs allows gaining an insight into the spatial configuration of binding sites. we propose two ways of analysing probabilistic grammars to extract biologically meaningful features focusing on either parse trees or grammar rules. we start by providing an in-depth study of grammars produced to describe the extended ps pattern which include calcium and manganese binding sites. through this analysis, we will use the 3d structure of a legume lectin protein, i.e. 1fat, to visualise the structure of the site and its description as provided by the grammar parse trees. we will focus our attention on grammars based on residue accessibility, calcium propensity and manganese propensity, since these grammars have been shown as being the most informative to describe the ps pattern. figure 2a) shows the 3d structure of the extended ps pattern. figure 2b) displays hydrogen-bonds involved in ligand binding and beta sheet which exhibit anti-parallel β-sheet type relationships. the grammar generated for this pattern based on accessibility is composed of the following rules associated with their normalized probability. p, z and n express respectively high, average and low accessibility. a → bc rules: s → ts | vp t → xu u → nz | zz v → pn | pz w → zp | tu x → vw a → a rules:     a/l r/k n/m d/f c/p q/s e/t g/w h/y i/v n:     z:     p:     as shown on the grammar parse tree, see figure 3b), there is a set of context free rules t→xu, x→vw, w→tu which is repeated to elongate the tree. moreover, the derivation of x→vw is v→pn|pz. since all amino acids which show high accessibility propensity, i.e. l, m, f, c, w, i and v, have also high beta sheet propensity, the v rule is beta strand friendly. therefore, this grammar imposes a constraint between the length of the loop and the first beta strand, see figure 3a). similarly, the rule s → vp associated with v → pn|pz is right-hand side strand friendly, which defines the second beta sheet, see figure 3a) &3b). whereas the accessibility based grammar describes in particular the beta sheet which is present in the pattern, the magnesium propensity based grammar deals with magnesium binding. rules of the'a → bc' type for this grammar are the following: s → vn | vz t → zu u → xn | tz | tw v → ns | xw | vu w → np | zp | xw x → zw where p, z and n express respectively high, average and low magnesium binding propensity. the parse tree of this grammar reveals the magnesium binding site is divided between strand and loop parts at v → vu branching rule, see figure 4a), 4b) &4c). the derivations of v on the strand side and u on the loop side impose the presence of w rules. since any w rule derivation exits with w → np|zp, which is magnesium binding friendly, both sides of the magnesium binding sites must include magnesium binding residues. finally, the calcium propensity based grammar defines not only the calcium binding part of the pattern, but more generally the pattern's structure.'a → bc' type grammar rules are the following: s → tw | xs t → tw | xw u → zp v → vu | zz w → vw | vz | pn x → vu | xu where p, z and n express respectively high, average and low calcium binding propensity. the parse tree of this grammar decomposes neatly the site in four parts: beta ca binding loop, beta and rest of the loop, see figure 5a), 5b) &5c). the second way of reading grammars, namely analysis of highly probable production chains and especially cycles, is demonstrated on the nap binding pattern ps which is found in some aldo- and ketoreductases. the protein structure of 1mrq is used for illustration. rules of the'a → bc' type for the nap propensity grammar for this pattern are the following: s → zu | sz t → pv | tz u → zt | uz v → pu | vz | sp | v → zp | np where p, z and n express respectively high, average and low nap propensity. for this grammar, there exist two cyclic rule chains of high probability which start from non-terminal t. cycle a defines a nap binding fragment consisting of two consecutive amino acids of high nap propensity. this corresponds to the well conserved lys and ser of 1mrq, which are seen in orange in figure since the termination of any derivation of this grammar imposes either v→np or v→zp rules and another t→pv production is required to end the cycle b, the shortest parse tree terminating cycle b would display the following pattern'pzzpypp', where y represents either z or n. residues of high nap propensity show a'i → i+3' periodicity which could suggest the presence of a nap binding site involving an alpha helix. the derivation tree of 1mrq shows that compared to the shortest predicted parse tree, the recursive rule t→tz is used to extend the original pattern to'pzzpzpzp' which corresponds to the substring'neqrirqn'. analysis of the pdb model confirms this pattern defines a helix. moreover, asn arg and asn which are seen in blue in figure are indeed very close to the ligand and provide an nap binding environment. ligplot data show that arg and asn are actually involved in the bound state of the molecule. finally, we analyse the so binding site associated to ps profile of m-phase inducer phosphatase using both parse trees and grammar rules. this region is illustrated using cartoon and stick 3d models of 1cws. the parse tree of the accessibility based grammar for the region is shown in figure 8a). this tree shows a strong asymmetry with a mainly hydrophilic left side and a hydrophobic right side. this suggests very different structural properties between these parts of binding site. figure 7a) reveals a beta-sheet on the left and an alpha-helix plus one disturbed but clear turn on the right. in addition to these features which could have been obtained using standard secondary structure prediction methods, the parse tree also highlights the creation of a hydrophilic environment between the right side hydrophilic amino acids close to the tree root and the left side amino acids. this is confirmed in figure 7b) where the side chains of right hand side cys and ile are directed towards the beta sheet. using the parse tree of the so propensity based grammar, some insight can be provided regarding so binding. contrarily to the hydrophilic side of the site which is composed of residues showing low so propensity, the hydrophobic side appears as a good candidate for so binding. more specific information can be obtained through the analysis of the so propensity based grammar whose rules of type'a → bc' are as follows: s → tw t → xw | nu | nz u → xz | xn | xp v → np | zp | nz w → vz | vp x → zs | ns where p, z and n express respectively high, average and low so binding propensity. two most probably cyclic chains are as follows: where the most likely derivation of w is: w → vz and v → n|z p from cycle a, the following pattern is revealed:'ysypzypz', where y represents either z or n. since s can be substituted by the pattern itself, after a substitution the patterns become'yysypzypzypzypz'. this shows a'i→i+3' periodicity of so4-friendly residues which is consistent with the presence of an alpha-helix. in addition, the derivation of the less likely cycle b produces the following pattern:'nysxypz' where x represents any so propensity. then, if s is substituted by the pattern coded in cycle a, the new pattern models a'i→i+3/i+4' periodicity,'nyysypzypzxypz', which is also typical for helices. this result combined with the low so propensity of the hydrophobic side of the binding site suggests that so binding would involve the arginine-rich ridge of a helix. this is confirmed by ligplot which shows that arg and arg are involved in so binding. this analysis of grammars describing ligand binding sites has shown that probabilistic context-free grammars allow the production of binding site descriptors which are human-readable and, hence, provide some insight into biologically meaningful features. moreover, each of these grammars relies on high probability rules which could not be expressed with regular grammars. therefore, this confirms that the description of many ligand binding sites benefits from the expressive power of context free grammars. stochastic context-free grammars for sequence annotation and binding site detection in order to demonstrate that, not only scfg based descriptors are meaningful, but are powerful at both annotating sequences and detecting binding sites, we first evaluate them on sites which can be expressed quite successfully by a prosite pattern. in this section, all results are produced using grammars containing a full set of rules. since each scfg deals with one amino acid property at a time, scores obtained by several grammars need to be combined to obtain optimal results. table shows tp and tn rates for grammars based on different properties, their combinations and their comparison with scores obtained by prosite patterns. this short pattern - only residues - is the anion exchanger pattern. the table reveals that charge and van der waals volume are important features for the expression of this binding site. moreover, scfgs allows detecting relevant sequences missed by the prosite pattern. since each scfg deals with one amino acid property at a time, scores obtained by several grammars need to be combined to obtain optimal results. table shows tp and tn rates for grammars based on different properties, their combinations and their comparison with scores obtained by prosite patterns. this short pattern - only residues - is the anion exchanger pattern. the table reveals that charge and van der waals volume are important features for the expression of this binding site. moreover, scfgs allows detecting relevant sequences missed by the prosite pattern. a more complete performance analysis of different grammars is provided in table for ps in terms of precision, recall and maximum f is shown. we also provide in figure the receiver operating characteristic. since negative-to-positive ratios in our datasets are quite high, roc curves may present an optimistic assessment of the performances of our framework. therefore, we also show in figure a recall-precision curve which has been proposed as a better alternative. although accessibility and, ca and mn propensity are key properties of the residues involved in this binding site, they need to be combined to produce good results. results obtained for ps pattern by using scfgs are near perfect. pattern ps appeared to be more difficult, but recall for 100%precision is still very high. the results for combined grammars are also very good for ps00063: recall of for precision and maximum f of. only 69% of sequences in the positive set are recognised without fp. this slightly worse result can be explained by the fact that unlike the two other patterns, the pattern covers only a part of the binding site to relatively huge nap molecule. therefore many key dependencies were not available to the grammars. since correct annotation does not imply correct detection, both tests - annotation and detection - are necessary to prove the functionality of the approach. in order to evaluate capabilities of detection, a number of tests were carried out. in table results for ps for the combined grammar most successful in annotation task are shown. detection: the peak is expected to be exactly at the position of the pattern; detection: the peak is expected to be no longer distance than 50% of the pattern length as an outcome of this evaluation, performance of detection appears to be good. in the most difficult task, where the highest peak was demanded to be exactly at the position of the pattern, success rate was 75%. when 50% coverage, i.e. residues displacement for ps was allowed, success rate rose to 100%. similar outcomes were obtained for the other patterns where detection results were in line with annotation results. to conclude, our system managed to achieve good accuracy in both annotation and detection. the results confirmed suitability of our approach in integrating amino acid properties in our grammars and combining obtained grammars. it shows that these strategies together with appropriate choice of the properties relevant to the pattern provide satisfactory solutions to the requirement of alphabet size reduction. the remaining part of this paper will only show annotation results since it makes comparisons with profile hmm performances easier. constrained grammar evaluation in this section we evaluate the approach consisting on constraining the initial grammar structure as described in the methods section. it imposes a bias in the grammars so that they use context-free features and it allows increasing the number of non-terminal while keeping a manageable total number of rules. comparisons between performances obtained by scfgs with a full set of rules - standard scfg - and a constrained set - nestednt scfg - is provided in table where results regarding annotation task for ps ps mpi phosphatase and zinc finger meta-patterns are provided. nestednt scfgs performed consistently better than standard scfgs, especially concerning recall for 100%precision. these results suggest that increasing the number of non-terminals allows improving performance by increasing expressive capabilities. analysis of parse trees shows that more than independent nts would be required to cover all important structural features. moreover, examination of grammar structures produced with different parameters confirmed that constrained grammars were more consistent in their structure than standard scfgs. performance comparison of scfgs with profile hmms since we have already demonstrated that unlike hmm profiles, rules of scfg are human readable and can be used to gain some biological insight about binding sites, in this section comparison between the two techniques is limited to annotation results. as ps ps and ps patterns were optimised for prosite, this method has an intrinsic advantage compared to profile hmms and scfgs for these patterns in this experiment. moreover, since mpi phosphatases are a subset of rhodanese-like proteins which can be expressed by a domain profile, it is expected that profile hmms would perform well in annotating this family. since prosite scores are calculated using the whole swiss-prot/trembl database, comparison with other methods based on precision and therefore f statistics may not be fair. therefore, we use recall for 100%precision of profile hmms and pcfgs, and prosite recall to evaluate prosite performance against the others. table shows comparison of results between the methods for our patterns of interest. as expected, although scfgs scores are generally good, prosite and profile hmms outperform scfgs when dealing with standard prosite patterns. ps is an exception where scfgs obtain perfect score. results achieved by profile hmm and scfg for mpi phosphatase pattern are very similar, with the former only slightly superior over the latter. in the case of the zinc finger meta-pattern, table does not reveal any significant difference between performances of profile hmms and scfgs. these results validate our assumption that scfgs gain efficiency from higher expressiveness and, despite operating on a reduced protein alphabet, can be at least as efficient as lower-level grammars, i.e. prosite patterns and profile hmms, built on sequences of amino acid identities. to investigate further the meta-pattern results, roc and rpc are provided in figure and these curves show that although our stochastic grammars are based here on a single feature - zinc propensity - they perform slightly better than profile hmms. although none of the other tested properties allowed improving scfgs results, we believe there is still some space for improvement if suitable properties could be combined to zinc propensity. study of false negatives produced by these two methods at their maximum performance level in the term of f shows sequences were rejected by scfg while by profile hmm. since only sequences belonged to both groups, this seems to confirm both schemes have very different definitions of this binding site which might be regarded as complementary. discussion this study demonstrates the capability of the framework we propose to take advantage of the expressive power of stochastic context free grammar for analysis of protein sequences. first, we have shown with a few examples that the analysis of sequence based scfg rules allows gaining an insight into the 3d structure of binding sites. this is a unique feature of our approach compared to, for example, hmm based methods which only produce'black box' descriptors. our analysis of grammar structures has revealed that the ability of expressing branched and nested dependencies is essential to describe some binding sites which can be seen as displaying such relationships through the intermediate of a ligand. this confirms the theoretical potential of our method in describing sites which are out of the scope of hmm profiles. it is important to be aware that many sites, such as parallel β-sheets, display dependencies which are beyond the expressiveness of scfgs and, therefore, are not suitable candidates for our approach. secondly, we have demonstrated that our scfg based system can be practical and accurate to annotate proteins and detect binding site patterns. this confirms that the various strategies developed to deal with the challenge of using scfgs for proteins sequences were appropriate. our approach of integrating quantitative properties of amino acids into the scfg framework has shown to be an efficient method to reduce the size of grammars. moreover, properties based on ligand propensity were especially useful. in addition, combining grammars typically yielded in better scores than those obtained by any single property grammar. furthermore, experimentations, where grammar structures are constrained, suggest that restricting the grammar induction search space using heuristics is an approach which merits further investigation. results show that our approach usually does not perform as well as profile hmms in annotation task when dealing with binding sites which can be well expressed with rigid regular grammars. this can be explained by the fact our scheme relies on a reduced amount of information, i.e. amino acid properties instead of amino acid identities, the main benefit of the system we propose is that - when considering only rules with significant probabilities - both structure and rule probabilities of context-free grammars are learned automatically without introducing constraints specific to the targeted sites. such grammars of relatively simple structure are human-readable; hence they could become valuable sources of information for molecular biologists. another advantage of our framework is that, unlike other methods, it does not rely on sequence alignments. therefore, as encouraging results with zinc finger meta-pattern suggest, our system may be particularly suited to deal with patterns shared by non-homologous proteins.  we have presented a novel stochastic context-free grammars based framework relying on quantitative representation of amino acid properties. the scfg based system for protein sequence analysis was tested on several data samples in various configurations. first, we have shown the produced binding site descriptors are human-readable and their analysis can provide biological insight into the structures of their associated binding sites. to our knowledge, no other type of binding site descriptors can reveal subtle interactions as described by scfgs. secondly, by achieving high precision and recall in annotation and very good detection rates our system proved to be a practical tool for protein pattern recognition. moreover, results for the zinc finger meta-pattern which outperformed profile hmms suggest that meta-patterns are one of the fields where application of scfgs can be especially useful. in addition, since both approaches produced different false negative, scfgs can be seen as complementary to existing profile hmm based methods. this suggests our scfg framework could be used to improve those methods. this study also supports the idea that binding site regions which could be seen as involving indirect nested dependencies between residues are prime targets for our framework. an increase of the number of non-terminal symbols allows representing a larger variety of relations within a binding site. additional constraints to grammars enable the use of more symbols and facilitate the learning process. indeed, our experiment showed that, generally, constrained grammars produced better results. for future work, we intend to further our research into constrained grammars by inferring optimal grammar structure. we will also implement secondary structure based grammars to take advantage of this higher level property. furthermore, our procedure of grammar combination will be refined by customising each grammar's weight to reflect the entropy of underlying properties in the training samples and single grammar performance. finally, we plan to develop a web tool allowing interactive analysis of binding sites encoded by scfg based descriptors. 
however, these grammars, like other state of the art methods, cannot cover any higher-order dependencies such as nested and crossing relationships that are common in proteins. however, in the field of proteomics, the size of the protein alphabet and the complexity of relationship between amino acids have mainly limited the application of formal language theory to the production of grammars whose expressive power is not higher than stochastic regular grammars. grammars were induced using quantitative properties of amino acids to deal with the size of the protein alphabet. in order to overcome some of these limitations, we propose a stochastic context free grammar based framework for the analysis of protein sequences where grammars are induced using a genetic algorithm. a new stochastic context free grammar based framework has been introduced allowing the production of binding site descriptors for analysis of protein sequences. finally, grammars based on different properties were combined to convey as much information as possible. results show the produced binding site descriptors are human-readable and, hence, highlight biologically meaningful features. this framework was implemented in a system aiming at the production of binding site descriptors. experiments have shown that not only is this new approach valid, but produces human-readable descriptors for binding sites which have been beyond the capability of current machine learning techniques. in the last decade, there have been many applications of formal language theory in bioinformatics such as rna structure prediction and detection of patterns in dna. evaluation was performed on sites of various sizes and complexity described either by prosite patterns, domain profiles or a set of patterns. in addition, findings suggest that, unlike current state-of-the-art methods, our system may be particularly suited to deal with patterns shared by non-homologous proteins. moreover, they achieve good accuracy in both annotation and detection.
 in the last decade, there have been many applications of formal language theory in bioinformatics such as rna structure prediction and detection of patterns in dna. however, in the field of proteomics, the size of the protein alphabet and the complexity of relationship between amino acids have mainly limited the application of formal language theory to the production of grammars whose expressive power is not higher than stochastic regular grammars. however, these grammars, like other state of the art methods, cannot cover any higher-order dependencies such as nested and crossing relationships that are common in proteins. in order to overcome some of these limitations, we propose a stochastic context free grammar based framework for the analysis of protein sequences where grammars are induced using a genetic algorithm.  this framework was implemented in a system aiming at the production of binding site descriptors. these descriptors not only allow detection of protein regions that are involved in these sites, but also provide insight in their structure. grammars were induced using quantitative properties of amino acids to deal with the size of the protein alphabet. moreover, we imposed some structural constraints on grammars to reduce the extent of the rule search space. finally, grammars based on different properties were combined to convey as much information as possible. evaluation was performed on sites of various sizes and complexity described either by prosite patterns, domain profiles or a set of patterns. results show the produced binding site descriptors are human-readable and, hence, highlight biologically meaningful features. moreover, they achieve good accuracy in both annotation and detection. in addition, findings suggest that, unlike current state-of-the-art methods, our system may be particularly suited to deal with patterns shared by non-homologous proteins.  a new stochastic context free grammar based framework has been introduced allowing the production of binding site descriptors for analysis of protein sequences. experiments have shown that not only is this new approach valid, but produces human-readable descriptors for binding sites which have been beyond the capability of current machine learning techniques. 