BACKGROUND
sequences of dna, rna and proteins are the fundamental currency of modern biological research, which link the different levels of the biological hierarchy, from genes to 3d structures  <cit> .
common features of species and functionally important residues can be identified through sequence mining.
rna, which stores information like dna and acts as an enzyme like proteins, may have supported cellular or pre-cellular life  <cit> , and is crucial to protein synthesis that plays a very important role in life.
there are many rnas with other roles in particular regulation of gene expression.
research shows that non-coding rna genes produce a functional rna product rather than a translated protein  <cit> .
the most startling recent development in the non-coding rna  field is the widespread importance of microrna .
in the past six years, accompanied with the development of experimental  <cit>  and computational  <cit>  mirnas detecting methods, the number of mirna genes registered in mirbase  <cit>  increased rapidly.
we explored mirbase from version  <dig> to version  <dig> and found that the number of known mirnas increased rapidly during the last several years .
a similar trend can also be seen in  <cit> .
it can be expected that with the use of next-generation sequencing technology  <cit> , more mirna genes will be identified.
mirnas  <cit> , belonging to the family of small non-coding rnas , are endogenous in many animal and plant genomes, and are now recognized as one of the major regulatory gene families in eukaryotic cells  <cit> .
they modulate diverse biological processes, including embryonic development, tissue differentiation, and tumorigenesis.
mirnas inhibit translation and promote mrna degradation via sequence-specific binding to the 3'utr regions of mrnas  <cit> .
mature mirnas are derived from longer precursors, each of which can fold into a hairpin structure that contains one or two mature mirnas in either or both its arms  <cit> .
the biogenesis of a mirna in animals consists of two steps.
in the first step, the primary mirna , which is several hundred nucleotides long, is processed in the nucleus by a multi-protein complex containing an enzyme called drosha to give rise to the ~ <dig> nt long mirna stem-loop precursor , which is then exported to the cytoplasm.
the second step takes place in the cytoplasm where the pre-mirna matures into a ~ <dig> nt long mirna:mirna* duplex, with each strand originating from the opposite arm of the stem-loop  <cit> .
then, the mirna strand of the mirna:mirna* duplex is loaded into a ribonucleoprotein complex known as the mirna-induced silencing complex   <cit> .
to date, the mirna* was thought to be peeled away and degraded.
however, some studies indicate that mirna* is also sorted into argonauts and might have a regular function in drosophila melanogaster  <cit> .
mirbase is the central online repository of mirna nomenclature, sequence data, annotation and target prediction, which first appeared in oct.  <dig>  <cit> .
release  <dig> contains  <dig> mirna loci from  <dig> species.
from version  <dig> , mirbase began to classify mirnas into different families.
this kind of information was stored in mifam.dat, which was freely available online http://www.mirbase.org.
these families were prepared manually.
essentially, it was done by using the single-linkage method to cluster the precursor sequences based on blast hits, and then adjusting  manually the clustered families by multiple sequence alignment.
the aim is to put mirnas that have a common ancestor into the same family.
rfam  <cit>  is another well known rna database.
it contains a collection of multiple sequence alignments and covariance models  that represent ncrna families.
the primary aim of rfam is to annotate new members of known rna families on nucleotide sequences, particularly complete genomes, by using sensitive blast filters in combination with cms.
both primary sequences and base-paired secondary structures are used to establish and annotate families.
release  <dig> contains  <dig> families, including  <dig> mirna families.
but the quality of multiple sequence alignments and secondary structures is still a challenge for rfam.
furthermore, rfam requires a lot of computing resources to establish the family structure, which is time consuming, especially when the number of sequences is huge.
since pre-mirnas can form stable hairpins, this specific structural property has been used to cluster or classify them by some ncrna clustering or classification methods  <cit> .
will et al.
<cit>  presented a structure-based clustering approach, locarna , which is capable of extracting putative rna classes from genome-wide survey of structured rnas.
the performance of locarna relies on the prediction accuracy of rna secondary structures.
however, current rna secondary structure energy models are not always able to predict native rna structures, even for short molecules  <cit> .
furthermore, hairpin secondary structure might be less effective in mirna classification since all mirnas can fold back into this type of structure.
by far, multiple sequence and/or structure alignments are still widely used in ncrna clustering and classification field.
but neither of them has completely solved the ncrna clustering or classification problem, especially for mirnas.
not to mention effectiveness, only efficiency is still far from being satisfactory, since these methods could be very time-consuming when applied to large-scale validation of mirna families.
as we know, mirnas are highly conserved in not only their primary sequences but also their secondary structures.
and mirnas in the same family always have consensus secondary structures and similar functions  <cit> .
hence, it is biologically significant to subsume mirnas with consensus second structures and similar functions to the same family.
in this paper, based on the family system provided by mirbase, we explored supervised learning techniques to accurately and automatically classify pre-mirna or mature sequences.
concretely, we propose an effective alignment free model named mirfam to classify newly detected mirnas.
first, it extracts n-grams as features from primary sequences.
then, these n-gram features are integrated into one feature vector by concentration.
finally, it trains a multiclass svm classifier svmmulticlass based on the families prepared by mirbase to classify new pre-mirna or mature sequences whose families are not yet known.
as a powerful tool, mirfam aims to classify new mirnas into their corresponding families.
it can not only support researchers who just obtained novel mirnas computationally or experimentally to go on exploring the function of these mirnas, but also enhance the utility of mirbase by providing higher automation and accuracy for mirna classification.
when measuring sequence similarity, unlike blast  <cit>  or other blast-based methods, mirfam uses shorter sequence segments, thus it has a much smaller search space, which allows it to run faster.
as the first mirna-oriented sncrna family classification method, mirfam has several advantages:  only primary information of mirnas is required, no other assumption  is imposed.
compared with multiple sequence alignment , mirfam is more efficient and accurate.
to classify ~ <dig>  pre-mirna sequences, msa will cost several hours while mirfam consumes only several minutes.
mirfam is insensitive to sequencing error and the exact position of pre-mirna in pri-mirna.
the change of several bases has very little effect on the feature vectors.
RESULTS
in order to evaluate the mirfam method, we designed a pipeline that is illustrated in figure  <dig>  the experiments were arranged into three groups: single family tests, multi-family tests and application-oriented large-scale mirbase family tests, which were conducted on a number of datasets whose details are presented in the methods section.
we started with single family tests, then multi-family tests and finally application-oriented large-scale mirbase family tests.
single family tests are classical binary classification, while the other tests are multi-class classification.
with mirfam, users can conveniently choose different combinations of n-grams.
according to our experience, unigrams, bigrams, trigrams and tetragrams are enough to classify all mirnas registered in mirbase.
for single family and multiple-family tests, even only unigrams, bigrams and trigrams are enough to achieve satisfactory classification performance.
all experimental results were achieved by 5-fold cross validation.
that is, each dataset is first randomly divided into five equally-sized partitions, each of which contains the same ratio of positive and negative examples.
and then any four partitions are merged as the training set to train mirfam, which is further evaluated with the fifth data partition.
this procedure is repeated five times with different combinations of training and testing sets, and the final classification performance is obtained by averaging the five tests' results.
single family tests
synthetic dataset test
the three biggest families in mirbase <dig> are let- <dig>  mir- <dig> and mir- <dig>  which contain  <dig>   <dig> and  <dig> members, respectively.
these three families were merged with three synthetic datasets r <dig>  r <dig> and r <dig>  respectively.
mirfam was then tested on these three merged datasets, which are denoted as "let-7+r1", "mir-17+r2" and "mir-9+r3".
our aim is to show that mirfam can distinguish real pre-mirnas from synthetic random sequences with similar base compositions.
as expected, the combination of n-gram and multiclass svm algorithm can precisely classify real mirnas and random sequences.
experimental results are presented in table  <dig>  from which we can see that the accuracy is higher than  <dig> % for all three families.
next, we took "let-7+r1", which gets the middle accuracy, as an example for further analysis.
in 5-fold cross validation, only four sequences  were misclassified.
mi <dig> and mi <dig> were first discovered from schistosoma japonicum by cloning and sequencing a small  rna cdna library from adult worms  <cit> .
we submitted these two real mirna sequences to rfam  separately, but no hit was obtained.
we then turned to clustal w <dig> to generate the msa with default parameters and viewed the guide tree by jalview <dig>  .
we found that mi <dig> and mi <dig> were located in separate branches, while random <dig> and random <dig> lied in the nearby branches.
results showed that these synthetic sequences were so similar to the real ones that they were indistinguishable by using mirfam and msa.
in order to give a more intuitive picture of these datasets, we calculated the euclidean distance  between the real and synthetic cluster centers, and we found that the larger the euclidean distance is, the better the classification performance is .
* only trigram and bigram features are considered in these experiments.
real dataset test
mirnas and snornas are two classes of small non-coding regulatory rnas, which have been extensively investigated in recent years.
although their functions in the cell are distinct, they share interesting genomic similarities.
recent sequencing projects have identified processed forms of snornas that resemble mirnas.
a comparison of the genomic locations of reported mirnas and snornas reveals an overlap of some specific members of these two classes  <cit> .
keeping this in mind, we evaluated mirfam on another three datasets, which were constructed by merging dataset s with the families let- <dig>  mir- <dig> and mir- <dig>  and were denoted as "let-7+s", "mir-17+s" and "mir-9+s", respectively.
the results are presented in table  <dig>  which shows that mirfam can easily distinguish mirnas from snornas, and the accuracies are higher than 99%.
a results of mirfam with unigram, bigram and trigram, without concentration factor.
bresults of mirfam with unigram, bigram and trigram, with concentration factor.
ccombination of t <dig>  g <dig> and g <dig>  all results are percentiles.
the effect of concentration factor
in this paper, we introduced the concentration factor to weight the features of family vectors .
intuitively, the longer fragments of sequences should be more informative than the shorter ones.
for example, with some exceptions  <cit> , a triplet codon in a nucleic acid sequence specifies a single amino acid.
and here, a trigram is exactly a triplet.
thus, in representing mirnas sequences, the longer n-grams should outweigh the shorter ones.
in what follows, we will see whether our concentration factor weighting scheme conforms to the above intuition and observation, by checking the centers  of the three families  and dataset s .
in summary, the analysis on the feature vectors of different families shows that the concentration factor weighting scheme can enhance the trigrams while restraining the bigrams and unigrams, which is reasonable and consistent to the intuition and observation.
most importantly, our extensive classification experiments in this and the later sections also show indirectly that the weighting scheme is effective.
multi-family tests
as mentioned before, with the development of powerful deep sequencing technology, more mirna genes will be identified in the future.
but the number of real mirnas in a certain genome is still unknown.
thus, a major concern is how well mirfam will perform if only a small number of known mirnas are available for some certain families and species.
in the previous single family tests, we have employed three types of n-grams  as features, so one natural question is how the different combinations of these types of n-grams will impact mirfam's performance.
furthermore, as mature mirnas and hairpin sequences are somehow a little different, it occurs to us whether mirfam will perform differently on them.
to answer these questions, we tested mirfam on three multi-family datasets constructed from mirbase  according to their family members.
t <dig> contains the top  <dig> biggest families in mirbase , while g <dig> and g <dig> contain those families whose members are around  <dig> and  <dig>  respectively.
here, the numbers  <dig> and  <dig> are randomly selected.
performance measurements like sensitivity and specificity are usually defined for binary classification.
here we actually deal with multi-class  classification, so we use accuracy  as the performance indicator.
the impact of training dataset size
all  <dig> precursor sequences in t <dig> were divided into ten equally-sized partitions.
first, we randomly took one partition  of the sequences as the training set, the remaining nine partitions  as the testing set.
then, we increased the training set by one partition , and accordingly the testing set was reduced by one partition .
this process continues iteratively till half of t <dig> was for training and the other half for testing.
at each round, mirfam was trained and tested, and its performance is evaluated by cross validation.
as shown in figure  <dig>  the accuracy is  <dig> % when only 10% of t <dig> is used for training.
with the increase of training samples, the accuracy stably goes up.
when the training set and the testing set are of equal size, the accuracy of mirfam is nearly 90%.
for a normal 5-fold cross validation on the whole dataset, i.e, training mirfam with 80% samples and testing it with the remaining 20%, the accuracy is  <dig> %.
the impact of the combination of different n-gram types
here, we examine how classification performance will be impacted by the different combinations of unigrams, bigrams and trigrams on these multi-family datasets .
actually, we also test mirfam with tetragrams, the results are presented in additional file  <dig>  table s <dig>
we found that mirfam performs better when more types of n-gram features were used.
even when only the trigrams were used to classify mirnas, the accuracy is around 90%.
for the g <dig> dataset, when features of unigram, bigram and trigram types were all included, the accuracy was surprisedly more than 99%.
further exploring the classification results, we also found that some abnormal sequences with noise bases  were also classified correctly in 5-fold cross validation , which means that mirfam is insensitive to base changes, such as single-nucleotide polymorphism  or sequencing error.
in addition, by transforming pre-mirna sequences to feature vectors, both normal and abnormal sequences were handled in a similar process, thus avoiding the cumbersome addition, deletion and modification operations used in msa.
test with mature mirnas
it has been shown that mirnas are modified after maturation  <cit> .
so, we also evaluated mirfam on mature mirnas contained in these multi-family datasets .
comparing to the results in table  <dig>  it can be seen that in most cases, mirfam performs better with mature mirnas than with all mirnas, which indicates that mirfam can accurately classify both hairpin and mature sequences.
in fact, for a mature mirna, the seed region is always much more functional than the other regions, it is the core functional region of its precursor.
thus, mirbase also prefers to put mirnas with similar mature sequences into the same families.
that is the reason why mirfam can achieve better performance with shorter maturity.
it is also more efficient to classify mature mirnas than to classify pre-mirnas, since matures usually contain no more than 30% bases of their precursors.
* two reasons why the numbers of mature sequences in multi-family datasets are less than that in hairpins.
first, different pre-mirnas may generate similar mature mirnas.
second, some pre-mirnas contain several mature mirnas, but only one is considered.
application-oriented large-scale families tests
a good model should not be data specific, instead it should be generally applicable.
although mirfam can achieve excellent results in single family tests and multi-family tests, what we really care about is its practical application performance.
based on this consideration, we evaluated mirfam on large-scale families from mirbase .
results are presented in table  <dig>
a families in mirbase whose members are no less than  <dig>
b all families in mirbase  <dig> are used.
c mirfam results with uni-, bi- and trigram features.
d mirfam results with uni-, bi-, tri- and tetragram features.
since 5-fold cross validation was employed, families that contain less than  <dig> members were not considered at first.
a detailed family distribution in mirbase could be found in figure s <dig> in the additional file  <dig>  from mirbase v <dig>  the  <dig> families that contain no less than  <dig> members were selected, which hold  <dig> %  pre-mirna sequences of the whole database.
on this dataset, mirfam achieved an accuracy of  <dig> %.
when we were preparing this manuscript, mirbase  was released in april  <dig>  this is a significant update, with over  <dig> new hairpin sequences and more than  <dig> new mature sequences.
from mirbase v <dig>   <dig> families were selected, each of which contains no less than  <dig> members.
these families constitute  <dig> %  hairpin sequences in the whole database.
even with such large-scale families, mirfam still got an accuracy of  <dig> %.
when dealing with mirbase v <dig>  there are still  <dig> pre-mirnas distributed in  <dig> families that were not processed .
among them,  <dig> families have only  <dig> members.
in the final experiment, we tested mirfam on the whole  <dig> families in mirbase v <dig>  for those families with less than  <dig> members, we randomly chose one member as the testing sample, and the remaining as training samples, mirfam still obtained an accuracy of  <dig> %, which was a surprisingly satisfactory result, considering that classifying a dataset with a large number of classes and the extremely uneven distributions of members in these classes is a well-recognized challenging task.
discussion
effectively classifying newly detected mirnas to their corresponding families is helpful for their further functional analysis.
however, only a few works have been done to address this issue, which is far from being established.
unlike existing alignment-based sncrna clustering or classification methods  <cit> , which can also be used to cluster or classify mirnas, the proposed mirfam bases on supervised learning techniques, which is more general and effective.
it does not require sequence- or structure-based alignment, thus it is free from the difficulty of choosing multiple parameters used in the alignment-based methods, and is also free from the quality issue of mirna secondary structure prediction.
certainly, mirfam is not completely parameter-free, it still has to set two parameters, i.e., the feature vector length l and the trade-off between training error and margin c. another advantage of the mirfam method is its efficiency, especially when the number of sequences is huge.
furthermore, mirfam can achieve satisfactory classification performance over the family system prepared by mirbase.
of all predictions made by mirfam, the accuracy is beyond 90%.
therefore, it can be used to replace the manual modification, which will greatly save time.
most known mirna sequences are evolutionary conserved  <cit> , mirna families may have consensus secondary structures  <cit> , and the microrna-target relationships are also conservative  <cit> .
as people's interest in the mirna world continuously grows, more and more datasets are going to appear.
correspondingly, there is an urgent need to classify the newly discovered mirnas into their corresponding families according to sequence and/or structure similarities.
with correct family classification, it is easier to elucidate the structures and functions of the new sequences, by using multiple sequence alignments.
apparently, more in-depth information can also be available, such as snps within pre-mirnas and mature mirnas  <cit> .
one potential limitation of the proposed approach is that it relies on a prepared family classification structure.
actually, this is a common problem with classification - a supervised machine learning approach, and the quality of training sets significantly influences classification accuracy.
to overcome this limitation, we can turn to clustering analysis, which is an unsupervised learning approach that can automatically group the mirna sequences into different categories based on their characteristics of sequences and/or structures.
we keep this issue as our future work.
CONCLUSIONS
sequence alignments are useful for the analysis of genomic data.
for example, mirna genes in newly sequenced organism can be detected based on their homology to genes in related and well-studied species  <cit> .
once homologous genes are detected, one can perform a msa with the hope of establishing mirna families.
however, msa is time consuming in doing this work, different msa algorithms may build quite different alignments, and choosing an appropriate alignment algorithm is crucial to the performance of family classification.
in this article, we developed a new approach mirfam to accurately and automatically classify mirna precursors by using n-grams and a multiple-class svm classifier.
to evaluate the mirfam method, we designed a pipeline, including single family tests, multi-family tests and large-scale families tests.
based on the experimental results, the following conclusions could be drawn:
<dig>  mirfam can effectively distinguish synthetic random sequences and similar snorna sequences from real pre-mirna sequences .
<dig>  even with a small number of training samples, mirfam can still achieve a high accuracy.
and with more types of n-gram features, mirfam can perform better .
<dig>  both precursors and mature mirnas can be used to infer mirna families.
with shorter mature sequences, mirfam can achieve better classification result .
<dig>  when the dataset contains more than  <dig> families and each family holds no less than  <dig> members, the classification accuracy is around 98%.
even with the entire mirbase , the accuracy surprisedly reaches 90% .
in summary, we proposed the first supervised learning based approach mirfam to automatically assign mirna precursors to their corresponding families with high accuracy.
it can be useful to help family classification, especially in the applications that previously have been done manually, such as mirbase.
additionally, due to its robustness, mirfam can be used in a wide range of scenarios, as long as an existing family assignment information is available.
certainly, its performance depends on the existing family assignment information.
however, as there is more and more study on mirna, it is foreseeable that more mirnas will be identified and registered in mirbase.
such a situation will certainly favor the existence and utilization of the mirfam method.
in return, mirfam will also contribute a lot to the efficient exploration of these newly discovered mirnas.

 sequences of dna, rna and proteins are the fundamental currency of modern biological research, which link the different levels of the biological hierarchy, from genes to 3d structures. common features of species and functionally important residues can be identified through sequence mining. rna, which stores information like dna and acts as an enzyme like proteins, may have supported cellular or pre-cellular life, and is crucial to protein synthesis that plays a very important role in life. there are many rnas with other roles in particular regulation of gene expression. research shows that non-coding rna genes produce a functional rna product rather than a translated protein. the most startling recent development in the non-coding rna field is the widespread importance of microrna. in the past six years, accompanied with the development of experimental and computational mirnas detecting methods, the number of mirna genes registered in mirbase increased rapidly. we explored mirbase from version to version and found that the number of known mirnas increased rapidly during the last several years. a similar trend can also be seen in. it can be expected that with the use of next-generation sequencing technology, more mirna genes will be identified. mirnas, belonging to the family of small non-coding rnas, are endogenous in many animal and plant genomes, and are now recognized as one of the major regulatory gene families in eukaryotic cells. they modulate diverse biological processes, including embryonic development, tissue differentiation, and tumorigenesis. mirnas inhibit translation and promote mrna degradation via sequence-specific binding to the 3'utr regions of mrnas. mature mirnas are derived from longer precursors, each of which can fold into a hairpin structure that contains one or two mature mirnas in either or both its arms. the biogenesis of a mirna in animals consists of two steps. in the first step, the primary mirna, which is several hundred nucleotides long, is processed in the nucleus by a multi-protein complex containing an enzyme called drosha to give rise to the ~ nt long mirna stem-loop precursor, which is then exported to the cytoplasm. the second step takes place in the cytoplasm where the pre-mirna matures into a ~ nt long mirna:mirna* duplex, with each strand originating from the opposite arm of the stem-loop. then, the mirna strand of the mirna:mirna* duplex is loaded into a ribonucleoprotein complex known as the mirna-induced silencing complex. to date, the mirna* was thought to be peeled away and degraded. however, some studies indicate that mirna* is also sorted into argonauts and might have a regular function in drosophila melanogaster. mirbase is the central online repository of mirna nomenclature, sequence data, annotation and target prediction, which first appeared in oct.. release contains mirna loci from species. from version, mirbase began to classify mirnas into different families. this kind of information was stored in mifam.dat, which was freely available online http://www.mirbase.org. these families were prepared manually. essentially, it was done by using the single-linkage method to cluster the precursor sequences based on blast hits, and then adjusting manually the clustered families by multiple sequence alignment. the aim is to put mirnas that have a common ancestor into the same family. rfam is another well known rna database. it contains a collection of multiple sequence alignments and covariance models that represent ncrna families. the primary aim of rfam is to annotate new members of known rna families on nucleotide sequences, particularly complete genomes, by using sensitive blast filters in combination with cms. both primary sequences and base-paired secondary structures are used to establish and annotate families. release contains families, including mirna families. but the quality of multiple sequence alignments and secondary structures is still a challenge for rfam. furthermore, rfam requires a lot of computing resources to establish the family structure, which is time consuming, especially when the number of sequences is huge. since pre-mirnas can form stable hairpins, this specific structural property has been used to cluster or classify them by some ncrna clustering or classification methods. will et al. presented a structure-based clustering approach, locarna, which is capable of extracting putative rna classes from genome-wide survey of structured rnas. the performance of locarna relies on the prediction accuracy of rna secondary structures. however, current rna secondary structure energy models are not always able to predict native rna structures, even for short molecules. furthermore, hairpin secondary structure might be less effective in mirna classification since all mirnas can fold back into this type of structure. by far, multiple sequence and/or structure alignments are still widely used in ncrna clustering and classification field. but neither of them has completely solved the ncrna clustering or classification problem, especially for mirnas. not to mention effectiveness, only efficiency is still far from being satisfactory, since these methods could be very time-consuming when applied to large-scale validation of mirna families. as we know, mirnas are highly conserved in not only their primary sequences but also their secondary structures. and mirnas in the same family always have consensus secondary structures and similar functions. hence, it is biologically significant to subsume mirnas with consensus second structures and similar functions to the same family. in this paper, based on the family system provided by mirbase, we explored supervised learning techniques to accurately and automatically classify pre-mirna or mature sequences. concretely, we propose an effective alignment free model named mirfam to classify newly detected mirnas. first, it extracts n-grams as features from primary sequences. then, these n-gram features are integrated into one feature vector by concentration. finally, it trains a multiclass svm classifier svmmulticlass based on the families prepared by mirbase to classify new pre-mirna or mature sequences whose families are not yet known. as a powerful tool, mirfam aims to classify new mirnas into their corresponding families. it can not only support researchers who just obtained novel mirnas computationally or experimentally to go on exploring the function of these mirnas, but also enhance the utility of mirbase by providing higher automation and accuracy for mirna classification. when measuring sequence similarity, unlike blast or other blast-based methods, mirfam uses shorter sequence segments, thus it has a much smaller search space, which allows it to run faster. as the first mirna-oriented sncrna family classification method, mirfam has several advantages: only primary information of mirnas is required, no other assumption is imposed. compared with multiple sequence alignment, mirfam is more efficient and accurate. to classify ~ pre-mirna sequences, msa will cost several hours while mirfam consumes only several minutes. mirfam is insensitive to sequencing error and the exact position of pre-mirna in pri-mirna. the change of several bases has very little effect on the feature vectors.  in order to evaluate the mirfam method, we designed a pipeline that is illustrated in figure the experiments were arranged into three groups: single family tests, multi-family tests and application-oriented large-scale mirbase family tests, which were conducted on a number of datasets whose details are presented in the methods section. we started with single family tests, then multi-family tests and finally application-oriented large-scale mirbase family tests. single family tests are classical binary classification, while the other tests are multi-class classification. with mirfam, users can conveniently choose different combinations of n-grams. according to our experience, unigrams, bigrams, trigrams and tetragrams are enough to classify all mirnas registered in mirbase. for single family and multiple-family tests, even only unigrams, bigrams and trigrams are enough to achieve satisfactory classification performance. all experimental results were achieved by 5-fold cross validation. that is, each dataset is first randomly divided into five equally-sized partitions, each of which contains the same ratio of positive and negative examples. and then any four partitions are merged as the training set to train mirfam, which is further evaluated with the fifth data partition. this procedure is repeated five times with different combinations of training and testing sets, and the final classification performance is obtained by averaging the five tests' results. single family tests synthetic dataset test the three biggest families in mirbase are let- mir- and mir- which contain and members, respectively. these three families were merged with three synthetic datasets r r and r respectively. mirfam was then tested on these three merged datasets, which are denoted as "let-7+r1", "mir-17+r2" and "mir-9+r3". our aim is to show that mirfam can distinguish real pre-mirnas from synthetic random sequences with similar base compositions. as expected, the combination of n-gram and multiclass svm algorithm can precisely classify real mirnas and random sequences. experimental results are presented in table from which we can see that the accuracy is higher than % for all three families. next, we took "let-7+r1", which gets the middle accuracy, as an example for further analysis. in 5-fold cross validation, only four sequences were misclassified. mi and mi were first discovered from schistosoma japonicum by cloning and sequencing a small rna cdna library from adult worms. we submitted these two real mirna sequences to rfam separately, but no hit was obtained. we then turned to clustal w to generate the msa with default parameters and viewed the guide tree by jalview. we found that mi and mi were located in separate branches, while random and random lied in the nearby branches. results showed that these synthetic sequences were so similar to the real ones that they were indistinguishable by using mirfam and msa. in order to give a more intuitive picture of these datasets, we calculated the euclidean distance between the real and synthetic cluster centers, and we found that the larger the euclidean distance is, the better the classification performance is. * only trigram and bigram features are considered in these experiments. real dataset test mirnas and snornas are two classes of small non-coding regulatory rnas, which have been extensively investigated in recent years. although their functions in the cell are distinct, they share interesting genomic similarities. recent sequencing projects have identified processed forms of snornas that resemble mirnas. a comparison of the genomic locations of reported mirnas and snornas reveals an overlap of some specific members of these two classes. keeping this in mind, we evaluated mirfam on another three datasets, which were constructed by merging dataset s with the families let- mir- and mir- and were denoted as "let-7+s", "mir-17+s" and "mir-9+s", respectively. the results are presented in table which shows that mirfam can easily distinguish mirnas from snornas, and the accuracies are higher than 99%. a results of mirfam with unigram, bigram and trigram, without concentration factor. bresults of mirfam with unigram, bigram and trigram, with concentration factor. ccombination of t g and g all results are percentiles. the effect of concentration factor in this paper, we introduced the concentration factor to weight the features of family vectors. intuitively, the longer fragments of sequences should be more informative than the shorter ones. for example, with some exceptions, a triplet codon in a nucleic acid sequence specifies a single amino acid. and here, a trigram is exactly a triplet. thus, in representing mirnas sequences, the longer n-grams should outweigh the shorter ones. in what follows, we will see whether our concentration factor weighting scheme conforms to the above intuition and observation, by checking the centers of the three families and dataset s. in summary, the analysis on the feature vectors of different families shows that the concentration factor weighting scheme can enhance the trigrams while restraining the bigrams and unigrams, which is reasonable and consistent to the intuition and observation. most importantly, our extensive classification experiments in this and the later sections also show indirectly that the weighting scheme is effective. multi-family tests as mentioned before, with the development of powerful deep sequencing technology, more mirna genes will be identified in the future. but the number of real mirnas in a certain genome is still unknown. thus, a major concern is how well mirfam will perform if only a small number of known mirnas are available for some certain families and species. in the previous single family tests, we have employed three types of n-grams as features, so one natural question is how the different combinations of these types of n-grams will impact mirfam's performance. furthermore, as mature mirnas and hairpin sequences are somehow a little different, it occurs to us whether mirfam will perform differently on them. to answer these questions, we tested mirfam on three multi-family datasets constructed from mirbase according to their family members. t contains the top biggest families in mirbase, while g and g contain those families whose members are around and respectively. here, the numbers and are randomly selected. performance measurements like sensitivity and specificity are usually defined for binary classification. here we actually deal with multi-class classification, so we use accuracy as the performance indicator. the impact of training dataset size all precursor sequences in t were divided into ten equally-sized partitions. first, we randomly took one partition of the sequences as the training set, the remaining nine partitions as the testing set. then, we increased the training set by one partition, and accordingly the testing set was reduced by one partition. this process continues iteratively till half of t was for training and the other half for testing. at each round, mirfam was trained and tested, and its performance is evaluated by cross validation. as shown in figure the accuracy is % when only 10% of t is used for training. with the increase of training samples, the accuracy stably goes up. when the training set and the testing set are of equal size, the accuracy of mirfam is nearly 90%. for a normal 5-fold cross validation on the whole dataset, i.e, training mirfam with 80% samples and testing it with the remaining 20%, the accuracy is %. the impact of the combination of different n-gram types here, we examine how classification performance will be impacted by the different combinations of unigrams, bigrams and trigrams on these multi-family datasets. actually, we also test mirfam with tetragrams, the results are presented in additional file table s we found that mirfam performs better when more types of n-gram features were used. even when only the trigrams were used to classify mirnas, the accuracy is around 90%. for the g dataset, when features of unigram, bigram and trigram types were all included, the accuracy was surprisedly more than 99%. further exploring the classification results, we also found that some abnormal sequences with noise bases were also classified correctly in 5-fold cross validation, which means that mirfam is insensitive to base changes, such as single-nucleotide polymorphism or sequencing error. in addition, by transforming pre-mirna sequences to feature vectors, both normal and abnormal sequences were handled in a similar process, thus avoiding the cumbersome addition, deletion and modification operations used in msa. test with mature mirnas it has been shown that mirnas are modified after maturation. so, we also evaluated mirfam on mature mirnas contained in these multi-family datasets. comparing to the results in table it can be seen that in most cases, mirfam performs better with mature mirnas than with all mirnas, which indicates that mirfam can accurately classify both hairpin and mature sequences. in fact, for a mature mirna, the seed region is always much more functional than the other regions, it is the core functional region of its precursor. thus, mirbase also prefers to put mirnas with similar mature sequences into the same families. that is the reason why mirfam can achieve better performance with shorter maturity. it is also more efficient to classify mature mirnas than to classify pre-mirnas, since matures usually contain no more than 30% bases of their precursors. * two reasons why the numbers of mature sequences in multi-family datasets are less than that in hairpins. first, different pre-mirnas may generate similar mature mirnas. second, some pre-mirnas contain several mature mirnas, but only one is considered. application-oriented large-scale families tests a good model should not be data specific, instead it should be generally applicable. although mirfam can achieve excellent results in single family tests and multi-family tests, what we really care about is its practical application performance. based on this consideration, we evaluated mirfam on large-scale families from mirbase. results are presented in table a families in mirbase whose members are no less than b all families in mirbase are used. c mirfam results with uni-, bi- and trigram features. d mirfam results with uni-, bi-, tri- and tetragram features. since 5-fold cross validation was employed, families that contain less than members were not considered at first. a detailed family distribution in mirbase could be found in figure s in the additional file from mirbase v the families that contain no less than members were selected, which hold % pre-mirna sequences of the whole database. on this dataset, mirfam achieved an accuracy of %. when we were preparing this manuscript, mirbase was released in april this is a significant update, with over new hairpin sequences and more than new mature sequences. from mirbase v families were selected, each of which contains no less than members. these families constitute % hairpin sequences in the whole database. even with such large-scale families, mirfam still got an accuracy of %. when dealing with mirbase v there are still pre-mirnas distributed in families that were not processed. among them, families have only members. in the final experiment, we tested mirfam on the whole families in mirbase v for those families with less than members, we randomly chose one member as the testing sample, and the remaining as training samples, mirfam still obtained an accuracy of %, which was a surprisingly satisfactory result, considering that classifying a dataset with a large number of classes and the extremely uneven distributions of members in these classes is a well-recognized challenging task. discussion effectively classifying newly detected mirnas to their corresponding families is helpful for their further functional analysis. however, only a few works have been done to address this issue, which is far from being established. unlike existing alignment-based sncrna clustering or classification methods, which can also be used to cluster or classify mirnas, the proposed mirfam bases on supervised learning techniques, which is more general and effective. it does not require sequence- or structure-based alignment, thus it is free from the difficulty of choosing multiple parameters used in the alignment-based methods, and is also free from the quality issue of mirna secondary structure prediction. certainly, mirfam is not completely parameter-free, it still has to set two parameters, i.e., the feature vector length l and the trade-off between training error and margin c. another advantage of the mirfam method is its efficiency, especially when the number of sequences is huge. furthermore, mirfam can achieve satisfactory classification performance over the family system prepared by mirbase. of all predictions made by mirfam, the accuracy is beyond 90%. therefore, it can be used to replace the manual modification, which will greatly save time. most known mirna sequences are evolutionary conserved, mirna families may have consensus secondary structures, and the microrna-target relationships are also conservative. as people's interest in the mirna world continuously grows, more and more datasets are going to appear. correspondingly, there is an urgent need to classify the newly discovered mirnas into their corresponding families according to sequence and/or structure similarities. with correct family classification, it is easier to elucidate the structures and functions of the new sequences, by using multiple sequence alignments. apparently, more in-depth information can also be available, such as snps within pre-mirnas and mature mirnas. one potential limitation of the proposed approach is that it relies on a prepared family classification structure. actually, this is a common problem with classification - a supervised machine learning approach, and the quality of training sets significantly influences classification accuracy. to overcome this limitation, we can turn to clustering analysis, which is an unsupervised learning approach that can automatically group the mirna sequences into different categories based on their characteristics of sequences and/or structures. we keep this issue as our future work.  sequence alignments are useful for the analysis of genomic data. for example, mirna genes in newly sequenced organism can be detected based on their homology to genes in related and well-studied species. once homologous genes are detected, one can perform a msa with the hope of establishing mirna families. however, msa is time consuming in doing this work, different msa algorithms may build quite different alignments, and choosing an appropriate alignment algorithm is crucial to the performance of family classification. in this article, we developed a new approach mirfam to accurately and automatically classify mirna precursors by using n-grams and a multiple-class svm classifier. to evaluate the mirfam method, we designed a pipeline, including single family tests, multi-family tests and large-scale families tests. based on the experimental results, the following conclusions could be drawn: mirfam can effectively distinguish synthetic random sequences and similar snorna sequences from real pre-mirna sequences. even with a small number of training samples, mirfam can still achieve a high accuracy. and with more types of n-gram features, mirfam can perform better. both precursors and mature mirnas can be used to infer mirna families. with shorter mature sequences, mirfam can achieve better classification result. when the dataset contains more than families and each family holds no less than members, the classification accuracy is around 98%. even with the entire mirbase, the accuracy surprisedly reaches 90%. in summary, we proposed the first supervised learning based approach mirfam to automatically assign mirna precursors to their corresponding families with high accuracy. it can be useful to help family classification, especially in the applications that previously have been done manually, such as mirbase. additionally, due to its robustness, mirfam can be used in a wide range of scenarios, as long as an existing family assignment information is available. certainly, its performance depends on the existing family assignment information. however, as there is more and more study on mirna, it is foreseeable that more mirnas will be identified and registered in mirbase. such a situation will certainly favor the existence and utilization of the mirfam method. in return, mirfam will also contribute a lot to the efficient exploration of these newly discovered mirnas. 
we first employed n-grams to extract features from known precursor sequences, and then trained a multiclass svm classifier to classify new mirnas. when the testing dataset contains more than families, the classification accuracy is around 98%. given an established mirna family system, this paper addresses the problem of automatically and accurately classifying newly found mirnas to their corresponding families by supervised learning techniques. based on experimental results, we argue that mirfam is suitable for application as an automated method of family classification, and it is an important supplementary tool to the existing alignment-based small non-coding rna classification methods, since it only requires primary sequence information. comparing with mirbase's sequence alignment and manual modification, our study shows that the application of machine learning techniques to mirna family classification is a general and more effective approach. concretely, we propose an effective method, mirfam, which uses only primary information of pre-mirnas or mature mirnas and a multiclass svm, to automatically classify mirna genes.
 micrornas are ~ nt long integral elements responsible for post-transcriptional control of gene expressions. after the identification of thousands of mirnas, the challenge is now to explore their specific biological functions. to this end, it will be greatly helpful to construct a reasonable organization of these mirnas according to their homologous relationships. given an established mirna family system, this paper addresses the problem of automatically and accurately classifying newly found mirnas to their corresponding families by supervised learning techniques. concretely, we propose an effective method, mirfam, which uses only primary information of pre-mirnas or mature mirnas and a multiclass svm, to automatically classify mirna genes.  an existing mirna family system prepared by mirbase was downloaded online. we first employed n-grams to extract features from known precursor sequences, and then trained a multiclass svm classifier to classify new mirnas. comparing with mirbase's sequence alignment and manual modification, our study shows that the application of machine learning techniques to mirna family classification is a general and more effective approach. when the testing dataset contains more than families, the classification accuracy is around 98%. even with the entire mirbase, the accuracy surprisingly reaches 90%.  based on experimental results, we argue that mirfam is suitable for application as an automated method of family classification, and it is an important supplementary tool to the existing alignment-based small non-coding rna classification methods, since it only requires primary sequence information. availability the source code of mirfam, written in c++, is freely and publicly available at: http://admis.fudan.edu.cn/projects/mirfam.htm. 