BACKGROUND
several classes of small "non-coding rna"  have been discovered in the last decade and have been found to play a central role in biological processes.
one such class of non-coding rna is microrna .
mature mirna sequences are single stranded, typically 20- <dig> nucleotides long and encoded as a precursor molecule of about 60- <dig> nucleotides .
these precursors are derived from processing of a pri-mirna  by a ribonuclease, such as drosha.
pre-mirnas are also further cleaved to generate active mature mirna with the help of dicer.
computational approaches to identify mirnas are based on major properties of previously identified mirnas, such as presence of a hairpin-shaped stem loop like secondary structure, evolutionary conservation and low minimum free energy.
most of these tools share the same overall strategy but use different approaches  <cit> .
some of the tools, such as mirscan  <cit> , use a filtering criteria to pick out pre-mirnas from the initial set of candidate stem-loops based on gc content, minimum free energy and structural filters.
this fails to identify all the known mirnas with a high level of accuracy.
"homology-based" approaches exploit information from both sequence and structure to find new members of known mirna families  but cannot detect new mirnas.
examples of these are profile based erpin  <cit>  and miralign  <cit> .
promir  <cit> , a probabilistic co-learning method that relies on the paired hmm, models characteristics of the stem portion of the stem-loop viewed as a paired sequence.
it uses a set of additional filters like comparison to other vertebrate genomes.
a number of svm-based machine learning methods have also been developed for prediction of mirnas.
triplet-svm  <cit>  recognizes pre-mirnas based on the presence of small  structural features.
svm-based mirfinder  <cit>  was designed for analyzing genome-wide, pair-wise sequences from two related species and rnamicro  <cit>  uses twelve different features/descriptors, such as sequence composition, sequence conservation, structure, structure conservation and thermodynamic stability for svm classification.
it uses a preprocessor that identifies conserved 'almost-hairpins' in a multiple sequence alignment.
mipred <cit>  uses a set of  <dig> features, consisting of global and intrinsic rna folding measures, to construct an svm classifier to distinguish between precursors and non-precursors.
other kinds of learning-based prediction tools have also been developed, such as a random forest prediction technique mipred  <cit>  that uses a set of tree-based classifiers combining sampling of training data with random feature selection, and linear genetic programming-based mirpred  <cit> .
mirpred uses  <dig> classifiers and an est match filter.
these tools generally use pairwise/multiple alignments for scanning, except for triplet-svm and mirpred that use a single genome; and these have been evaluated on a single chromosome, or a part of a chromosome.
hybrid approaches involving both experimentation and computation have also been used for large scale novel mirna discovery.
one such approach is to sequence small rnas and then to analyse these in terms of known and novel mirnas using mirna prediction tools  <cit> .
mirdeep uses a probabilistic, additive scoring method to detect mirnas  <cit> .
however, some of the filters used for scoring are highly stringent and likely to miss many mirnas.
this report describes a mirna prediction method which uses a context-sensitive hidden markov model  and examines its application for predicting new mirnas in the human genome.
methods
datasets
the following datasets were used for experiments in this paper:
the primary and secondary structures of  <dig> human mirna precursors ;  the primary structure of  <dig> "pseudo-hairpin" sequences  <cit> ; i.e., sequences from human genic regions which can fold up into a hairpin structure, similar to pre-mirna.
these are expected to contain no mirna precursors;  the primary structures of  <dig>  non-human mirna precursors from  <dig> different species ;  the non coding rna set .
homo_sapiens.ncbi <dig> .ncrna.fa;  small rna sequences obtained from normal human leukocytes.
cross validation and hold out tests
part of datasets d <dig> and d <dig>  were used as the training data  to construct the final classification tree.
the remaining sequences from these two datasets, along with datasets d <dig> and d <dig> were used as test data on which predictions were made.
to exclude the influence of same-family members on the test results, all human mirnas from a given text set which had a member of the same family in the training set were removed; additionally, for dataset d <dig>  only one member of each family in a test set was kept.
thus the  <dig> remaining human precursors were purged of all the actual human pre-mirnas belonging to families that were also represented in the training set .
the residual test set comprised  <dig> human pre-mirnas and  <dig> pseudo-hairpins.
similarly the dataset d <dig>  was reduced to  <dig> sequences on removing family similarities.
the known mirnas were removed from the non coding rna set d <dig> and the rest  were used as a test set as many of the other ncrnas also form mirna-like secondary structures.
for details of the cross validation see additional file  <dig>
representing mirna precursors
regular hmms cannot be used to generate the language of mirna precursors: ignoring the loop, this language is that of palindromes with distant interactions between nucleotides and we need at least a context-free grammar to represent it.
however, the idea of cshmms has been recently proposed  <cit> .
these are capable of representing such sequences.
cshmms extend the idea of hmms by introducing a memory, in the form of a stack or a queue, between certain states in the model.
the original idea was to have a pairwise-emission state, which would put a copy of every symbol emitted by it into the associated memory, and a single corresponding context-sensitive state, which would read a symbol from the memory, and based on it, would then decide what to emit and where to transit.
to represent mirna structures, we have extended this idea slightly.
the cshmm structure we propose has two context sensitive states which are linked to the same pairwise-emission state through a stack.
this is because we need separate states to generate the stem and the symmetric bulges; yet both these states need information about what was emitted earlier .
the structure of the cshmm we propose is shown in fig.
<dig>  here states labeled as p are pairwise-emission states, those labeled as c are context-sensitive ones, and those labeled as s are regular hmm states.
identifying mirna precursors
parameter estimation
a complete cshmm consists not just of the structure, but also of probabilities for the symbols emitted and the probabilities of transition from one state to another .
given data of known stem-loop structures, these probabilities can be estimated by keeping count of the different transition and emission events for all the states.
with these counts, estimates of the emission and transition probabilities can be obtained using the following formulae  <cit> :
here, pe is the probability of emitting symbol σ in state q; and pt the probability of transiting from state q to q'.
q is the set of all states in the models; Σ is the output alphabet, consisting in this case of a, c, g and u; ct and ce are the transition and emission counts obtained from the labeled data.
for the two context-sensitive states, the symbol at the top of the stack also has to be taken into account.
accordingly, we modify the formulae above as follows :
discrimination
given a complete cshmm , and any input sequence, an optimal alignment algorithm for computing the most likely sequence of states using the cshmm is known  <cit> , we cannot, however, use this algorithm to discriminate between mirna precursors and other kinds of rna sequences.
for each such sequence, the algorithm simply gives us two things: the most likely state sequence  and the likelihood of obtaining that state sequence.
nevertheless, if the parameters have been estimated using mirna precursors, we can expect relatively high likelihoods for such sequences.
in addition, we would also expect to see a much closer match between the true secondary structure of mirna sequences and the structure predicted by the alignment algorithm.
in this paper, we investigate a very simple discriminatory function that uses the results from the alignment algorithm.
for our model, discrimination is a function only of the likelihood returned by the alignment algorithm.
the form of the discriminatory function is thus just a single-node classification tree  <cit> , which corresponds to a threshold on the likelihood score.
the value of this threshold is estimated from sequences of mirna precursors and non-precursors.
each sequence is provided to the alignment algorithm, which uses the cshmm from stage  <dig> to return a likelihood value.
a classification tree is then constructed to discriminate between the two sets of sequences, using just one feature: the likelihood value.
RESULTS
performance of the cshmm-based mirna classifier
the performance of the two-stage procedure for identifying mirna precursors described here was assessed by:  cross-validation estimates of predictive performance,  predictions on an independent dataset of known mirna precursors, and  prediction on a dataset of non coding rnas.
for comparison purposes, we also present the results obtained by using the recently described mipred classifier  <cit>  on the same data.
the datasets used here are described in further detail under methods.
the final cshmm structure, along with estimates of the transition probabilities, is shown in fig.
<dig>  results from the classification tree model built using the cshmm likelihood scores are presented here, alongside those obtained with mipred.
the 5-fold cross-validation estimate of predictive performance for our model on the human rna training data  is in table  <dig>  the cross-validation was done such that the mirnas belonging to the same family were kept in a single fold.
for mipred, the authors do not report the details of the 5-fold cross-validation results; only the overall accuracy is mentioned as  <dig> %.
results on the test set  for the respective classifiers are in table  <dig>  the cshmm-based classifier identified 94% of the total non-human mirnas  and 83% of the purged d <dig> set , and reported 4% of the non coding rnas  as mirnas.
the principal observations that we can make from the results are these:
the number in parentheses following each entry is the expected value of the entry under the hypothesis that the actual class is independent of the predicted one.
estimates of predictive accuracy, sensitivity and specificity from this table are  <dig>  ,  <dig>   and  <dig>   respectively.
the number in parentheses following each entry is the expected value of the entry under the hypothesis that the actual class is independent of the predicted one.
estimates of predictive accuracy, sensitivity and specificity of cshmm  from this table are  <dig>  ,  <dig>  , and  <dig>   respectively.
for mipred  these are  <dig>  ,  <dig>   and  <dig>   respectively.
the cshmm-based classifier performs as well as the svm-based model used by mipred: on both human and non-human pre-mirna test sets, our model's results are as good as or slightly better than those of mipred.
the primary advantage of the cshmm is that it is a generative model, as opposed to a discriminative model like the svm used by mipred.
this means that not only can we use the cshmm to identify likely pre-mirna sequences, but can also use it to predict the most likely secondary structure for a given pre-mirna candidate.
the cshmm specifies a probability distribution over all possible secondary structures.
the test results are largely in agreement with the 5-fold cross-validation estimates of table  <dig>  in particular, we see that both sensitivity and specificity values obtained on the human pre-mirna and "pseudo-hairpin" set  are very similar to the cross-validation estimates.
for nonhuman mirnas, the sensitivity observed is about 94% in comparison to sensitivity of 92% obtained with mipredon the whole set .
on removal of sequence similarities  the sensitivity is 83%.
we have also analysed other non coding rnas  for checking the specificity of the cshmm.
only 4% of the sequences were identified as mirnas, suggesting that the method discriminates well between actual mirnas and other ncrnas.
thus, in essence, only one feature  is effectively capturing all of the structural information encapsulated in the set of  <dig> features used by the mipredclassifier.
we do need to store all of the emission and transition probabilities, but these are parameters of the cshmm model as a whole, not features of each individual sequence.
once the cshmm model has been learnt, we only need to calculate one feature per sequence, which is the likelihood score from the alignment.
thus, the cshmm method greatly reduces the dimension of the feature space representation as compared to mipred's svm model: a key advantage of our model is that it offers a much simpler representation of mirna precursors.
rather than looking to use a lot of different folding measures like thermodynamic free energy, entropy, dinucleotide frequency etc.
to predict whether a sequence is a pre-mirna or not, the cshmm looks to statistically determine and encode the secondary structure features of actual mirna precursors.
by doing so, it not only allows us to make predictions on new sequences , but also provides the most likely secondary structure for any given sequence on the assumption that it is a pre-mirna.
the threshold used by the classification tree represents just one possible cutoff on the cshmm's likelihood score .
more generally, the performance of classifiers with different thresholds  can be summarised by a roc curve.
this is shown for holdout validation in fig.
<dig>  the curve shows a steep step-like slope, which usually suggests a good classifier across a range of thresholds.
identification of novel mirnas using the cshmm-based classifier
we are mainly interested in the identification of novel mirnas.
to this end, the cshmm-based classifier was used to scan the entire chromosome  <dig>  the classifier identified  <dig> out of the  <dig> known mirnas present on this chromosome .
around  <dig>  additional hairpins having high likelihood scores were taken as a candidate set and were subjected to post-prediction filters comprising checks for the presence of est matches and drosha cutting sites.
100% matches with untranslatable ests were shown by  <dig>  hairpins, out of which  <dig> harbored drosha cutting sites .
additional file  <dig> shows the sequences and the structures of these predicted novel mirnas.
we also carried out analysis of small rna sequences from normal human leukocytes .
flanking sequences of small rna reads originating from the intergenic and intronic regions of the human genome were extracted and were folded by the cshmm, cid-mirna and mirdeep .
the srnas falling within the same hairpin were classified as isomirs and star sequences  <cit>  and grouped into a family.
isomirs are srnas that fall within the same precursor sequence predicted and which have the same sequence but vary by a few nucleotides from each other on account of alternative dicer cutting.
star sequences are srna that also fall within the same hairpin but have a partially complementary sequence.
the member with the highest frequency  was deemed as a novel mirna.
the cshmm identified  <dig> srnas falling within hairpins out of which  <dig> were novel mirnas owing to their highest frequency in their respective family.
this was found to be comparable to that obtained by cid-mirna.
since mirdeep is likely to miss many valid mirnas due to a number of stringent criteria, such as expression level, used for prediction of novel mirnas, it is not surprising that it identified only  <dig> srnas falling in hairpins out of which  <dig> were novel mirnas.
the additional file  <dig> shows  <dig> srnas  grouped into families and their respective representative novel mirnas.
the additional file  <dig> shows the sequences and the structures of the  <dig> representative novel mirnas.
CONCLUSIONS
methods that can recognise mirnas without the restriction of sequence homology can help to focus the experimental effort for unknown families of mirnas.
in this paper, we have investigated one such method.
the recognition is achieved using a recently proposed extension to hidden markov models, which allows the development of probabilistic variants of context-sensitive grammars, which may be better suited to represent efficiently the "language" of mirna precursors.
specifically, we:  propose a context-sensitive hidden markov model  for recognizing mirna structures;  use known human mirna sequences to estimate transition and emission probabilities for the cshmm;  obtain the most likely secondary structure for a given sequence of nucleotides using the cshmm; and  use the likelihood values from the output of the cshmm to construct a recognizer  for mirnas.
the results suggest that we are able to develop a very simple classifier that shows a sensitivity of about 85% along with a specificity of about 97-98% on human mirna sequences.
although not trained using non-human sequences, the recogniser is able to identify a substantial proportion of a set of known mirnas from  <dig> different non-human species; the true-positive rate on these is around 83%.
in addition it can also differentiate mirnas from other ncrnas that form mirna-like secondary structures.
mature mirna derived from one of the predicted sequences was experimentally detected verifying the prediction .
the cshmm-based classifier constructed here is available as an applet online  <cit> .
competing interests
the authors declare that they have no competing interests.
authors' contributions
sa developed and implemented the cshmm, and conducted most of the computational experiments.
cv ran some of the applications, analyzed the genomic and small rna sequence data and organized the results.
ab planned the experimental part and helped to write sections of the manuscript.
as conceptualized the computational aspects of the problem and supervised sa.
supplementary material
additional file 1
methodological details of cshmm implementation and computational complexity estimation.
click here for file
additional file 2
analysis of known mirnas on chromosome  <dig>  this file contains the list of the known mirnas present on chromosome  <dig>   <dig> of these were predicted by cshmm.
click here for file
additional file 3
novel predicted mirnas on chromosome  <dig>  this file contains  <dig> intergenic and  <dig> intronic novel mirnas predicted by the cshmm along with their respective cshmm likelihood scores, est matches, drosha site prediction scores and mipred scores.
click here for file
additional file 4
secondary structures of the novel predicted mirnas on chromosome  <dig>
click here for file
additional file 5
novel mirnas from small rna sequence analysis.
the srnas are grouped into their respective isomir families as and when present.
the ones highlighted in blue are the representative novel mirnas, identified on the basis of highest frequency within the family.
click here for file
additional file 6
secondary structures of the  <dig> representative novel mirna from the srna sequence data.
click here for file
acknowledgements
the authors thank the department of biotechnology, government of india for support.
this article has been published as part of bmc bioinformatics volume  <dig> supplement  <dig>  2010: selected articles from the eighth asia-pacific bioinformatics conference .
the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2105/11?issue=s <dig>

 several classes of small "non-coding rna" have been discovered in the last decade and have been found to play a central role in biological processes. one such class of non-coding rna is microrna. mature mirna sequences are single stranded, typically 20- nucleotides long and encoded as a precursor molecule of about 60- nucleotides. these precursors are derived from processing of a pri-mirna by a ribonuclease, such as drosha. pre-mirnas are also further cleaved to generate active mature mirna with the help of dicer. computational approaches to identify mirnas are based on major properties of previously identified mirnas, such as presence of a hairpin-shaped stem loop like secondary structure, evolutionary conservation and low minimum free energy. most of these tools share the same overall strategy but use different approaches. some of the tools, such as mirscan, use a filtering criteria to pick out pre-mirnas from the initial set of candidate stem-loops based on gc content, minimum free energy and structural filters. this fails to identify all the known mirnas with a high level of accuracy. "homology-based" approaches exploit information from both sequence and structure to find new members of known mirna families but cannot detect new mirnas. examples of these are profile based erpin and miralign. promir, a probabilistic co-learning method that relies on the paired hmm, models characteristics of the stem portion of the stem-loop viewed as a paired sequence. it uses a set of additional filters like comparison to other vertebrate genomes. a number of svm-based machine learning methods have also been developed for prediction of mirnas. triplet-svm recognizes pre-mirnas based on the presence of small structural features. svm-based mirfinder was designed for analyzing genome-wide, pair-wise sequences from two related species and rnamicro uses twelve different features/descriptors, such as sequence composition, sequence conservation, structure, structure conservation and thermodynamic stability for svm classification. it uses a preprocessor that identifies conserved'almost-hairpins' in a multiple sequence alignment. mipred uses a set of features, consisting of global and intrinsic rna folding measures, to construct an svm classifier to distinguish between precursors and non-precursors. other kinds of learning-based prediction tools have also been developed, such as a random forest prediction technique mipred that uses a set of tree-based classifiers combining sampling of training data with random feature selection, and linear genetic programming-based mirpred. mirpred uses classifiers and an est match filter. these tools generally use pairwise/multiple alignments for scanning, except for triplet-svm and mirpred that use a single genome; and these have been evaluated on a single chromosome, or a part of a chromosome. hybrid approaches involving both experimentation and computation have also been used for large scale novel mirna discovery. one such approach is to sequence small rnas and then to analyse these in terms of known and novel mirnas using mirna prediction tools. mirdeep uses a probabilistic, additive scoring method to detect mirnas. however, some of the filters used for scoring are highly stringent and likely to miss many mirnas. this report describes a mirna prediction method which uses a context-sensitive hidden markov model and examines its application for predicting new mirnas in the human genome. methods datasets the following datasets were used for experiments in this paper: the primary and secondary structures of human mirna precursors; the primary structure of "pseudo-hairpin" sequences; i.e., sequences from human genic regions which can fold up into a hairpin structure, similar to pre-mirna. these are expected to contain no mirna precursors; the primary structures of non-human mirna precursors from different species; the non coding rna set. homo_sapiens.ncbi.ncrna.fa; small rna sequences obtained from normal human leukocytes. cross validation and hold out tests part of datasets d and d were used as the training data to construct the final classification tree. the remaining sequences from these two datasets, along with datasets d and d were used as test data on which predictions were made. to exclude the influence of same-family members on the test results, all human mirnas from a given text set which had a member of the same family in the training set were removed; additionally, for dataset d only one member of each family in a test set was kept. thus the remaining human precursors were purged of all the actual human pre-mirnas belonging to families that were also represented in the training set. the residual test set comprised human pre-mirnas and pseudo-hairpins. similarly the dataset d was reduced to sequences on removing family similarities. the known mirnas were removed from the non coding rna set d and the rest were used as a test set as many of the other ncrnas also form mirna-like secondary structures. for details of the cross validation see additional file representing mirna precursors regular hmms cannot be used to generate the language of mirna precursors: ignoring the loop, this language is that of palindromes with distant interactions between nucleotides and we need at least a context-free grammar to represent it. however, the idea of cshmms has been recently proposed. these are capable of representing such sequences. cshmms extend the idea of hmms by introducing a memory, in the form of a stack or a queue, between certain states in the model. the original idea was to have a pairwise-emission state, which would put a copy of every symbol emitted by it into the associated memory, and a single corresponding context-sensitive state, which would read a symbol from the memory, and based on it, would then decide what to emit and where to transit. to represent mirna structures, we have extended this idea slightly. the cshmm structure we propose has two context sensitive states which are linked to the same pairwise-emission state through a stack. this is because we need separate states to generate the stem and the symmetric bulges; yet both these states need information about what was emitted earlier. the structure of the cshmm we propose is shown in fig. here states labeled as p are pairwise-emission states, those labeled as c are context-sensitive ones, and those labeled as s are regular hmm states. identifying mirna precursors parameter estimation a complete cshmm consists not just of the structure, but also of probabilities for the symbols emitted and the probabilities of transition from one state to another. given data of known stem-loop structures, these probabilities can be estimated by keeping count of the different transition and emission events for all the states. with these counts, estimates of the emission and transition probabilities can be obtained using the following formulae: here, pe is the probability of emitting symbol σ in state q; and pt the probability of transiting from state q to q'. q is the set of all states in the models; Σ is the output alphabet, consisting in this case of a, c, g and u; ct and ce are the transition and emission counts obtained from the labeled data. for the two context-sensitive states, the symbol at the top of the stack also has to be taken into account. accordingly, we modify the formulae above as follows: discrimination given a complete cshmm, and any input sequence, an optimal alignment algorithm for computing the most likely sequence of states using the cshmm is known, we cannot, however, use this algorithm to discriminate between mirna precursors and other kinds of rna sequences. for each such sequence, the algorithm simply gives us two things: the most likely state sequence and the likelihood of obtaining that state sequence. nevertheless, if the parameters have been estimated using mirna precursors, we can expect relatively high likelihoods for such sequences. in addition, we would also expect to see a much closer match between the true secondary structure of mirna sequences and the structure predicted by the alignment algorithm. in this paper, we investigate a very simple discriminatory function that uses the results from the alignment algorithm. for our model, discrimination is a function only of the likelihood returned by the alignment algorithm. the form of the discriminatory function is thus just a single-node classification tree, which corresponds to a threshold on the likelihood score. the value of this threshold is estimated from sequences of mirna precursors and non-precursors. each sequence is provided to the alignment algorithm, which uses the cshmm from stage to return a likelihood value. a classification tree is then constructed to discriminate between the two sets of sequences, using just one feature: the likelihood value.  performance of the cshmm-based mirna classifier the performance of the two-stage procedure for identifying mirna precursors described here was assessed by: cross-validation estimates of predictive performance, predictions on an independent dataset of known mirna precursors, and prediction on a dataset of non coding rnas. for comparison purposes, we also present the results obtained by using the recently described mipred classifier on the same data. the datasets used here are described in further detail under methods. the final cshmm structure, along with estimates of the transition probabilities, is shown in fig. results from the classification tree model built using the cshmm likelihood scores are presented here, alongside those obtained with mipred. the 5-fold cross-validation estimate of predictive performance for our model on the human rna training data is in table the cross-validation was done such that the mirnas belonging to the same family were kept in a single fold. for mipred, the authors do not report the details of the 5-fold cross-validation results; only the overall accuracy is mentioned as %. results on the test set for the respective classifiers are in table the cshmm-based classifier identified 94% of the total non-human mirnas and 83% of the purged d set, and reported 4% of the non coding rnas as mirnas. the principal observations that we can make from the results are these: the number in parentheses following each entry is the expected value of the entry under the hypothesis that the actual class is independent of the predicted one. estimates of predictive accuracy, sensitivity and specificity from this table are, and respectively. the number in parentheses following each entry is the expected value of the entry under the hypothesis that the actual class is independent of the predicted one. estimates of predictive accuracy, sensitivity and specificity of cshmm from this table are,, and respectively. for mipred these are, and respectively. the cshmm-based classifier performs as well as the svm-based model used by mipred: on both human and non-human pre-mirna test sets, our model's results are as good as or slightly better than those of mipred. the primary advantage of the cshmm is that it is a generative model, as opposed to a discriminative model like the svm used by mipred. this means that not only can we use the cshmm to identify likely pre-mirna sequences, but can also use it to predict the most likely secondary structure for a given pre-mirna candidate. the cshmm specifies a probability distribution over all possible secondary structures. the test results are largely in agreement with the 5-fold cross-validation estimates of table in particular, we see that both sensitivity and specificity values obtained on the human pre-mirna and "pseudo-hairpin" set are very similar to the cross-validation estimates. for nonhuman mirnas, the sensitivity observed is about 94% in comparison to sensitivity of 92% obtained with mipredon the whole set. on removal of sequence similarities the sensitivity is 83%. we have also analysed other non coding rnas for checking the specificity of the cshmm. only 4% of the sequences were identified as mirnas, suggesting that the method discriminates well between actual mirnas and other ncrnas. thus, in essence, only one feature is effectively capturing all of the structural information encapsulated in the set of features used by the mipredclassifier. we do need to store all of the emission and transition probabilities, but these are parameters of the cshmm model as a whole, not features of each individual sequence. once the cshmm model has been learnt, we only need to calculate one feature per sequence, which is the likelihood score from the alignment. thus, the cshmm method greatly reduces the dimension of the feature space representation as compared to mipred's svm model: a key advantage of our model is that it offers a much simpler representation of mirna precursors. rather than looking to use a lot of different folding measures like thermodynamic free energy, entropy, dinucleotide frequency etc. to predict whether a sequence is a pre-mirna or not, the cshmm looks to statistically determine and encode the secondary structure features of actual mirna precursors. by doing so, it not only allows us to make predictions on new sequences, but also provides the most likely secondary structure for any given sequence on the assumption that it is a pre-mirna. the threshold used by the classification tree represents just one possible cutoff on the cshmm's likelihood score. more generally, the performance of classifiers with different thresholds can be summarised by a roc curve. this is shown for holdout validation in fig. the curve shows a steep step-like slope, which usually suggests a good classifier across a range of thresholds. identification of novel mirnas using the cshmm-based classifier we are mainly interested in the identification of novel mirnas. to this end, the cshmm-based classifier was used to scan the entire chromosome the classifier identified out of the known mirnas present on this chromosome. around additional hairpins having high likelihood scores were taken as a candidate set and were subjected to post-prediction filters comprising checks for the presence of est matches and drosha cutting sites. 100% matches with untranslatable ests were shown by hairpins, out of which harbored drosha cutting sites. additional file shows the sequences and the structures of these predicted novel mirnas. we also carried out analysis of small rna sequences from normal human leukocytes. flanking sequences of small rna reads originating from the intergenic and intronic regions of the human genome were extracted and were folded by the cshmm, cid-mirna and mirdeep. the srnas falling within the same hairpin were classified as isomirs and star sequences and grouped into a family. isomirs are srnas that fall within the same precursor sequence predicted and which have the same sequence but vary by a few nucleotides from each other on account of alternative dicer cutting. star sequences are srna that also fall within the same hairpin but have a partially complementary sequence. the member with the highest frequency was deemed as a novel mirna. the cshmm identified srnas falling within hairpins out of which were novel mirnas owing to their highest frequency in their respective family. this was found to be comparable to that obtained by cid-mirna. since mirdeep is likely to miss many valid mirnas due to a number of stringent criteria, such as expression level, used for prediction of novel mirnas, it is not surprising that it identified only srnas falling in hairpins out of which were novel mirnas. the additional file shows srnas grouped into families and their respective representative novel mirnas. the additional file shows the sequences and the structures of the representative novel mirnas.  methods that can recognise mirnas without the restriction of sequence homology can help to focus the experimental effort for unknown families of mirnas. in this paper, we have investigated one such method. the recognition is achieved using a recently proposed extension to hidden markov models, which allows the development of probabilistic variants of context-sensitive grammars, which may be better suited to represent efficiently the "language" of mirna precursors. specifically, we: propose a context-sensitive hidden markov model for recognizing mirna structures; use known human mirna sequences to estimate transition and emission probabilities for the cshmm; obtain the most likely secondary structure for a given sequence of nucleotides using the cshmm; and use the likelihood values from the output of the cshmm to construct a recognizer for mirnas. the results suggest that we are able to develop a very simple classifier that shows a sensitivity of about 85% along with a specificity of about 97-98% on human mirna sequences. although not trained using non-human sequences, the recogniser is able to identify a substantial proportion of a set of known mirnas from different non-human species; the true-positive rate on these is around 83%. in addition it can also differentiate mirnas from other ncrnas that form mirna-like secondary structures. mature mirna derived from one of the predicted sequences was experimentally detected verifying the prediction. the cshmm-based classifier constructed here is available as an applet online. competing interests the authors declare that they have no competing interests. authors' contributions sa developed and implemented the cshmm, and conducted most of the computational experiments. cv ran some of the applications, analyzed the genomic and small rna sequence data and organized the results. ab planned the experimental part and helped to write sections of the manuscript. as conceptualized the computational aspects of the problem and supervised sa. supplementary material additional file 1 methodological details of cshmm implementation and computational complexity estimation. click here for file additional file 2 analysis of known mirnas on chromosome this file contains the list of the known mirnas present on chromosome of these were predicted by cshmm. click here for file additional file 3 novel predicted mirnas on chromosome this file contains intergenic and intronic novel mirnas predicted by the cshmm along with their respective cshmm likelihood scores, est matches, drosha site prediction scores and mipred scores. click here for file additional file 4 secondary structures of the novel predicted mirnas on chromosome click here for file additional file 5 novel mirnas from small rna sequence analysis. the srnas are grouped into their respective isomir families as and when present. the ones highlighted in blue are the representative novel mirnas, identified on the basis of highest frequency within the family. click here for file additional file 6 secondary structures of the representative novel mirna from the srna sequence data. click here for file acknowledgements the authors thank the department of biotechnology, government of india for support. this article has been published as part of bmc bioinformatics volume supplement 2010: selected articles from the eighth asia-pacific bioinformatics conference. the full contents of the supplement are available online at http://www.biomedcentral.com/1471-2105/11?issue=s 
in this report, a "context-sensitive" hidden markov model to represent mirna structures has been proposed and tested extensively. the probabilities of the cshmm model were estimated using known human mirna sequences. however, it is expected that there may be many more mirnas encoded in the human genome. this pipeline was used to scan and identify potential mirnas from the human chromosome it was also used to identify novel mirnas from small rna sequences of human normal leukocytes obtained by the deep sequencing methodology. a total of and novel mirnas were predicted from chromosome and from the small rna sequences respectively. our pipeline, consisting of a cshmm and filters to reduce false positives shows promise as an approach for ab initio identification of novel mirnas. the results suggest that the cshmm performs better than these methods. the results suggest that the cshmm is likely to be a useful tool for mirna discovery either for analysis of individual sequences or for genome scan. in addition, the cshmm was used in a pipeline that includes filters that check for the presence of est matches and the presence of drosha cutting sites. a classifier for mirnas based on the likelihood score of this "trained" cshmm was evaluated by: cross-validation estimates using known human sequences, predictions on a dataset of known mirnas, and prediction on a dataset of non coding rnas.
 it has been apparent in the last few years that small non coding rnas play a very significant role in biological regulation. among these micrornas, 22- nucleotide small regulatory rnas, have been a major object of study as these have been found to be involved in some basic biological processes. so far about mirnas have been identified in humans alone. however, it is expected that there may be many more mirnas encoded in the human genome. in this report, a "context-sensitive" hidden markov model to represent mirna structures has been proposed and tested extensively. we also demonstrate how this model can be used in conjunction with filters as an ab initio method for mirna identification.  the probabilities of the cshmm model were estimated using known human mirna sequences. a classifier for mirnas based on the likelihood score of this "trained" cshmm was evaluated by: cross-validation estimates using known human sequences, predictions on a dataset of known mirnas, and prediction on a dataset of non coding rnas. the cshmm is compared with two recently developed methods, mipred and cid-mirna. the results suggest that the cshmm performs better than these methods. in addition, the cshmm was used in a pipeline that includes filters that check for the presence of est matches and the presence of drosha cutting sites. this pipeline was used to scan and identify potential mirnas from the human chromosome it was also used to identify novel mirnas from small rna sequences of human normal leukocytes obtained by the deep sequencing methodology. a total of and novel mirnas were predicted from chromosome and from the small rna sequences respectively.  the results suggest that the cshmm is likely to be a useful tool for mirna discovery either for analysis of individual sequences or for genome scan. our pipeline, consisting of a cshmm and filters to reduce false positives shows promise as an approach for ab initio identification of novel mirnas. 18- january the eighth asia pacific bioinformatics conference bangalore, india 