BACKGROUND
genomic sequence classification assigns a given sequence into its related group of known sequences with similar properties, traits or characteristics.
it is a fundamental practice in different research areas of microbiology yielding major challenges in comparative genomics.
accurate genomic sequence classification and typing could help to enhance the phylogenetics and functional studies of viruses  <cit> .
they also help in determining pathogenicity, developing vaccines, studying epidemiology and drug resistance  <cit> .
recent advances in dna sequencing and molecular biology techniques provide an immense collection of genomic information.
such data volume raises challenges for genetic-based classification techniques.
three main approaches have been designed and implemented to classify different types of viruses based on their genomic sequence characteristics.
the first is sequence alignment-based approach which is widely used, e.g.
in similarity search methods  and in pairwise distance based-methods .
the second is phylogenetic-based approach.
it is implemented in several tools, e.g.
rega  <cit>  and pplacer  <cit> .
the aim of these methods is to place an unknown sequence on an existing phylogenetic tree of a set of reference sequences.
each time a given sequence has to be classified, it is realigned with the set of reference sequences.
then, either a new phylogenetic tree is inferred or the given sequence is placed in the existing tree.
the third is alignment-free approach including methods based on nucleotide correlations  <cit>  and sequence composition  <cit> .
it transforms sequences or their relationships to feature vectors and then constructs a phylogeny, a statistical model or a machine learning model  <cit> .
these methods are reviewed in vinga and almeida  <cit> , mantaci et al.
<cit> , xing et al.
<cit>  and bonham-carter et al.
<cit> .
restriction fragment length polymorphism , a molecular biology technique  <cit> , is used to type different virus strains .
several algorithmic approaches have tackled theoretical and experimental problems related to the restriction enzyme data such as restriction mapping problem , phylogeny estimation , snp genotyping  <cit>  and analysis of rflp digitized gel images  <cit> .
however, large scale computational sequence classification based on the rflp technique is not yet covered in literature.
due to the genetic polymorphism in dna sequences, fragments resulting from enzyme digestions are different in terms of number and length between individuals or types.
a set of restriction enzymes grounds a fragment pattern signature for each sequence.
therefore, similar sequences ought to have similar fragment patterns and thus similar restriction site distributions.
this a priori knowledge could be used to build a machine learning model where sequences are represented by restriction site distributions as a feature vector and a class feature corresponding to a taxonomic level .
in this paper we introduce castor, a machine learning web platform, to classify and type sequences.
castor integrates a new alignment-free method based on the rflp principle.
our in silico method is independent of the sequence structure or function and is also not organism-specific.
castor is designed to facilitate the reuse, sharing and reproducibility of sequence classification experiments.
methods
overview of the approach
in this paper, we propose an in silico approach to identify and classify viral dna sequences based on their restriction enzyme sites using supervised machine learning techniques.
like other supervised learning approaches, the proposed one is divided into two main units .
the classifier construction unit builds and trains classification models .
it requires a set of reference viral genomic sequences, their classes and a list of restriction enzyme patterns.
it starts by creating a training set including a group of feature vectors.
the latter is computed from the distribution of the restriction site patterns on the given dna sequences and then refined by feature selection methods.
a collection of learning classifiers are then trained and evaluated using 10-fold cross validation in order to choose the best classifier.
the second unit  is intended to predict the classes or annotations of given viral sequences.
the inputs of this unit are a classifier, a set of dna sequences and the same list of restriction enzyme patterns used to train the classifier.
fig.
<dig> overview of castor kernel architecture.
the kernel is composed of two main units .
white rectangles represent input and output data; grey and curved rectangles represent processes.
ts and vs are training set and validation set, respectively
restriction fragment pattern-based features
here, we propose a set of features simulating the outcome of the rflp technique.
from rebase database  <cit> , we extracted a list of  <dig> type ii restriction enzymes and their recognition sites.
type ii family cleaves  dna sequences precisely on each occurrence of the recognition site.
then, the restriction digestion of dna sequences is computationally simulated.
in order to build a training set, for a sequence s and enzyme z we compute two metrics representing the distribution of the digested fragments: the number of cuts of the enzyme ) and the root mean square of digested fragment lengths ) calculated as
<dig> rms=1n∑i=1nli <dig>
where n is the number of fragments +1) and l
i is the length of the i
th fragment in linear genomes.
for circular genomes n=c
u
t. other metrics could be easily computed from the fragment digestion to construct the feature vectors.
feature selection methods
the selection of an optimal subset of features improves the learning efficiency and increases the predictive performance.
feature selection techniques reduce the learning set dimension by pruning irrelevant and redundant features.
two relevant methods of feature reduction are provided.
the first method  ranks the features according to their information gain  <cit>  and selects a subset of top-k features.
information gain estimates the mutual information between a feature and the target class.
the second method  uses the spearman’s rank correlation coefficient to construct a set of uncorrelated features.
the correlation coefficient between two feature ranking vectors u and v of size n is computed as follows:
<dig> ρ=1−6∑i=1n2n.
a two-tailed p-value is computed to test the null hypothesis which states that two feature vectors are uncorrelated.
in order to remove one of the two correlated features, two strategies could be used: discarding the feature with the largest sum of absolute correlation coefficients or the one with the smallest information gain score.
learning and evaluation
we explored three types of classifiers:  symbolic methods   <cit>  and random forests   <cit> ),  statistical methods   <cit> , support vector machine   <cit>  and k-nearest neighbors   <cit> ) and  ensemble methods   <cit>  and bagging   <cit>  both combined with j48); see additional file 1: table s <dig> for more details.
a 10-fold cross-validation strategy is used to assess the performance of the trained classifiers.
performance measures are weighted according to the number of instances and computed for the overall classification.
the performance measures are:
3)   ,fpr=fp/,precision=tp/,f−measure=2×tpr×precisiontpr+precision.
where tp, tn, fp, and fn are the number of true positive, true negative, false positive and false negative predictions, respectively.
tpr and fpr are the true positive rate and the false positive rate, respectively.
we used weka data mining program to perform the training and the evaluation  <cit> .
to include a negative class in the training sets, two approaches could be used.
first, provide manually constructed negative class from collected relevant data.
second, build it with the provided negative class generator.
this generator constructs altered sequences data from a sampling with replacement of the positive set sequences.
to alter the sampled sequences, we reshape the rflp length distribution of the training set by randomly shrinking, expanding or keeping unchanged the length of the sampled sequences.
then, each sequence is randomly shuffled while preserving k-mer counts.
datasets
in this study, we applied our approach to a wide range of viruses.
we selected one dsdna virus ), one dsdna-rt virus ) and one ssrna-rt virus ).
hpvs have a circular double stranded dna genome of ∼ <dig> bp and belong to five genera .
hpvs belonging to a genus share over 53% identity of their complete genomes and ones in the same species level share over 62% of identity  <cit> .
we assessed the performance of hpv classification in the genus and species taxonomic levels.
at the species level, we selected only the alpha hpv genus representing the most abundant and diverse genomes in databases.
it is divided into thirteen species .
unfortunately, some hpv genera  and alpha hpv species  were underrepresented and were therefore discarded.
hbv genomes are smaller  and are circular partly double stranded dna.
hbvs are classified into eight genotypes  with at least 8% divergence among their genomic sequences  <cit> .
we evaluated the performances of our method for the genotyping of hbv strains.
hpv and hbv complete genome sequences were downloaded from the ncbi refseq database  <cit> .
the taxonomic annotations were extracted from the ncbi taxonomy database  <cit> .
hiv- <dig> genomes have two copies of positive-sense single-stranded rna with ∼ <dig> bp.
phylogenetically, hiv- <dig> strains are divided into four groups: m, n, o and p  <cit> .
m group strains are worldwide prevalent.
they are categorized into pure subtypes  and recombinant forms .
genetic variations among subtypes are about 20–30% for env gene, 7–20% for gag gene and 10% for pol gene  <cit> .
for hiv- <dig> classification, we studied complete genomes  and fragments covering pol gene from the position  <dig> to  <dig> with respect to hxb <dig> reference sequence and having a minimum size of  <dig> kbp .
hiv- <dig> sequences were extracted from the los alamos hiv sequence database .
for all the datasets, only complete, curated and well-annotated sequences were selected.
moreover, each class ought to have an adequate number of genomic sequences in order to have a representative genetic diversity.
simulation studies
raw viral sequence datasets, described above, were class-size imbalanced, i.e., the difference in the number of genome sequences belonging to each class was relatively large.
generally, epidemiological studies are conducted on host-specific viruses  with the highest prevalence and pathogenicity  <cit> .
this leads to more data for some groups of viruses over others.
usually, training standard classifiers on imbalanced datasets affects their performance  and misleads the interpretation of their accuracy  <cit> .
under-sampling majority class approach has been shown to perform well  <cit>  and could be used with standard algorithms.
hence, from each previous dataset, we randomly performed under-sampling, without replacement, of the larger classes to have relatively the same sizes as the other classes.
in order to identify the best parameters of the classifiers, we randomly sampled  <dig> datasets for each of the hpv genera, hpv alpha species, hbv genotypes, hiv- <dig> m subtypes cgs and hiv- <dig> m subtypes pol fragments data.
for each obtained sample, we performed a 10-fold cross-validation study with different classifiers built as follows.
we constructed all the combinations of the two metrics , the two feature selection methods  and the seven learning algorithms.
this construction yielded  <dig> c
o
m
b
i
n
a
t
i
o
n
s∗ <dig> d
a
t
a
s
e
t
s= <dig> e
x
p
e
r
i
m
e
n
t
s for each virus classification.
RESULTS
the results section is divided into four parts: first, we show how the rflp signatures are suitable for viral classification; second, we assess the performance of several competing classification algorithms on different virus datasets; third, we compare the prediction made by castor against widely used methods for hiv- <dig> datasets, one of the most difficult to classify and fourth, we present the castor web platform.
classification with rflp signatures in virus familiesi
l
h
o
u
e
t
t
e a in hpv alpha  <dig>   <dig> and hpv gamma .
with castor, the best hpv alpha species classification obtains a tpr of  <dig>  and fpr of  <dig>  in 10-fold cross-validation analyses of  <dig> instances .
the power of rflp cuts in classification of viruses could be observed in hbv genotypes heatmap .
hbv highlights three genotypes  with c
o
h
e
s
i
o
n
i
n
d
e
x
e
s for most instances above  <dig>  indicating very coherent classes.
but b and c genotypes have values between  <dig>  and  <dig> .
the s
i
l
h
o
u
e
t
t
e
i
n
d
e
x plots show several instances of b, c, e and g genotypes that have an striking disagreement with their assigned classes .
even with these constraints, castor achieves the genotyping of  <dig> hbv instances with tpr of  <dig>  and fpr of  <dig>  according to a 10-fold cross-validation study .
the hiv- <dig> cut site patterns have more variability among pure subtypes and crfs .
likely, the mds plot shows a moderate subtype clustering for the main hiv- <dig> subtypes.
but this clustering is not well separated compared to hpv and hbv.
this variability among classes is reflected in low values of the c
o
h
e
s
i
o
n
i
n
d
e
x .
all, suggesting either variability, noise or mislabelling.
for instance, >30% of hiv- <dig> b and hiv- <dig> c instances tend to have rflp cut patterns of other subtypes .
with castor, the subtyping of hiv- <dig> group m within  <dig> main subtypes was assessed for  <dig> instances with a tpr of  <dig>  and fpr of  <dig> .
fig.
<dig> class cohesion of three virus datasets.
the four columns illustrate the separability and compactness of three virus complete genomes datasets based on  <dig> restriction enzyme cuts.
the first column shows heatmaps of cut clustered by x-axis.
the samples in the y-axis are grouped by studied classes followed by intra-class clusterings.
the second column shows mds of the cut distances between samples.
the third and fourth column represent, respectively, the cohesion and silhouette indexes of the classes.
a classes in hpv are alpha species, beta and gamma genera.
b classes in hbv are a-h genotypes c classes in hiv- <dig> are m pure subtypes and crfs
tpr
fpr
f-measure
this table contains the best results of the experimental study performed on the different datasets.
the evaluation measures are obtained with 10-fold cross-validation analysis.
the column classifier id contains the corresponding models available in castor platform
previously, it has been clearly shown that rflp has a power for classification in several viruses such as hpv  <cit> , hbv  <cit>  and hiv  <cit> .
but these studies are mostly limited to two to five classes.
to the best of our knowledge, our study constitutes the first large scale and multi-class analyses of rflp cut for classification.
it provides the basis to explore large and various types of classifications, in particular those based on machine learning methods.
machine learning classifier tuning and performance
the castor platform relies on machine learning methods for the classification of viruses based on rflp signatures of nucleotide sequences.
the platform is detailed in the castor web platform section.
three important parameters constitute the kernel of each castor classifier: a metric, a feature selection method and a learning algorithm.
to assess the different combination of the models, we performed a 10-fold cross-validation of the  <dig> experiments associated to each of the five datasets .
from the overall results of the five virus classifications, it is not obvious to distinguish the best candidate between cut and rms metrics.
in the genotyping of hbv, cut performs better than rms  while in the hpv genera and species classifications rms performs better than cut  .
however the mean of weighted f-measures for both methods is in all cases ≥ <dig>  .
the same analyses were performed on hiv- <dig> cgs and pol fragments.
cut performs slightly better than rms in both datasets when comparing the mean of weighted f-measures .
due to the variability of hiv- <dig>  the mean of weighted f-measures falls to  <dig>  in cgs and  <dig>  in pol fragments .
hence for the remaining of our study, we will fix the rflp metric according to its performance on the corresponding datasets.
additional file 1: figure s <dig> presents the comparative analyses of the two feature selection methods  in the  <dig> experiments for each dataset.
the mean of weighted f-measures of the two feature selection methods are not statistically different in all datasets .
in fact, the results of the two methods are correlated for the three viruses with the spearman’s rank correlation coefficient ranging between  <dig>  and  <dig>  .
in these simulations, the seven learning algorithms have various performances according to the different datasets.
the algorithm j <dig> has the worst weighted f-measure values .
however, its performance improves when combined with rft or bag algorithms.
in general, svm performs better in four of five datasets with mean of weighted f-measures >  <dig>  and ranks number one in hpv alpha species, hbv genotypes and hiv- <dig> subtypes classifications and four in hpv genera classification.
it is followed by rft, nba and ibk.
however, rft and nba are affected by a large variance .
these rankings are clearly observable on additional file 1: figure s <dig> and figure s <dig> presenting respectively the correlations cut/rms and topattribute/correlation grouped by algorithms.
while most algorithms have similar performance with cut or rms, naive bayes surprisingly performs better with cut.
fig.
<dig> learning algorithm evaluation on five datasets.
this figure illustrates the f-measure distribution  of seven learning algorithms on the prediction of a hpv genera, b hpv alpha species, c hbv genotypes, d hiv- <dig> m subtypes with complete genomes e hiv- <dig> m subtypes with pol fragments.
hpv and hbv datasets are complete genomes.
the number below each boxplot corresponds to the statistically discriminative rank of the algorithms.
the ranking is performed with paired student’s t test.
μ, σ are the mean and the standard deviation of the overall f-measures, respectively.
p is the p-value of the statistically significance of the weighted f-measure mean differences among the algorithms computed with the wilcoxon/kruskal-wallis test
assessing the performance castor on hiv- <dig> data
castor exhibits high accuracy for different hiv- <dig> classificationtable  <dig> evaluation of hiv- <dig> classification with castor
tpr
fpr
f-measure
this table contains the tpr, fpr and f-measure of  <dig> hiv- <dig> classifications obtained with 10-fold cross-validation analysis.
for each classification, the number of corresponding classes and instances are given.
the range  indicates the interval of instance frequencies per class used during the training of each model.
the column classifier id contains the corresponding models available in castor platform
comparing comet, rega and castor
next, we compared the performance of castor against the most powerful and widely used hiv- <dig> specific predictors namely comet  <cit>  and rega version  <dig>   <cit>  .
these comparisons are based on cg as well as pol fragment data.
it is important to notice that these programs are fixed and do not allow neither any change on the trained classes nor new training samples.
here the actual training of comet and rega includes respectively  <dig> and  <dig> classes for either cg or pol fragments.
to avoid under-represented classes, castor was trained on  <dig> classes for cgs and  <dig> classes for pol fragments .
we performed three comparisons .
the first, named complete sampling, assesses the performance of each method on  <dig> percent of randomly sampled los alamos hiv data.
this sampling permits to assess the performance of the predictors to fit realistic data with unknown classes.
the second, named specific subtypes, focuses, for each method, only on the corresponding trained subtypes.
the third, named common subtypes, compares the performance of the methods on the intersection of the  <dig> trained subtypes.
this strategy is used due to the fact that the training of comet and rega cannot be changed.
thus, it is difficult to adapt or perform other classification studies or larger benchmark analyses.
figure  <dig> shows that for cgs, rega performs the best followed by castor and for pol fragments comet outperforms, followed again by castor.
in the two types of data, when not performing the best, rega or comet performance drops drastically by more than 10% and ranks at the third position .
meanwhile castor ranks second in both two types of data.
with cgs, castor obtains a correct classification of  <dig> % against the sampling of los alamos hiv data when rega obtains  <dig> %.
but when testing predictors on their trained classes, the percentage of correct classification drastically increases to  <dig>  and  <dig> % respectively for rega and castor.
this result remains almost the same when comparing only the common trained classes among the three predictors .
these common classes cover  <dig> and 93% of the overall instances of the sampling of cgs and pol fragments, respectively.
the mean tpr of castor is higher than  <dig>  in the case of either pure subtypes or crfs.
the tpr of rega drops to  <dig>  when assessing crfs and remains almost perfect for pure subtypes .
in pol fragments, comet outperforms castor and rega in all comparisons.
applying the three methods, comet, rega and castor, on 10% random sampling of los alamos hiv data, the percentages of correct classification were  <dig> ,  <dig>  and  <dig> %, respectively.
this result is confirmed when comparing only the common trained classes where comet reaches  <dig> % and castor  <dig> %.
note that rega could not perform higher than 76% and has a mean tpr of  <dig>  for pure subtypes competing with comet.
in crf instances, comet and castor obtain almost an equal mean of tpr around  <dig>  .
rega cannot perform well in crf classification and has a mean of tpr equal to  <dig> .
castor has higher fpr values compared to the two other programs in overall classifications.
this fact is not surprising since rega and comet are specifically tuned to predict hiv data.
their predictions with lower scores tend to be discarded or ambiguous.
for instance, comet has 32% of its cg predictions that are unassigned as well as 5% of its pol fragment predictions.
hence, these numbers are higher than the false positive values of castor, but they are not included in the fpr computation.
however, it will be interesting to include in castor a threshold of inclusion of a given sequence into a class.
this could help reducing the fpr but it would require deeper analyses.
it also should be associated to the open-set classification problem that is beyond the scope of this paper.
fig.
<dig> performance of castor with comet and rega predictors on hiv- <dig> datasets.
the panels a and b show the percentage of correct classifications for hiv- <dig> complete genomes and hiv- <dig> pol fragments, respectively.
the number of instances and the associated classes for each sampling is presented above the panels.
complete sampling corresponds to 10% of los alamos hiv data selected randomly.
in specific subtypes sampling, the predictors are assessed against their trained classes.
in common subtypes sampling, the predictors are assessed against the intersection of the classes of the three trained predictors
tpr
fpr
f-measure
tpr
fpr
f-measure
tpr
fpr
f-measure
this table contains tpr, fpr and f-measure of comet, rega and castor on the prediction of hiv- <dig> m pure subtypes and cfrs complete genomes.
the shown classes belong to the common subtypes sampling.
the castor model used in this evaluation is pmshiv02
tpr
fpr
f-measure
tpr
fpr
f-measure
tpr
fpr
f-measure
this table contains tpr, fpr and f-measure of comet, rega and castor on the prediction of hiv- <dig> m pure subtypes and cfrs pol fragments.
the shown classes belong to the common subtypes sampling.
the castor model used in this evaluation is pmshiv03
even though castor is not a specific hiv- <dig> classifier, it competes with the most powerful methods in hiv- <dig>  unlike comet and rega, castor provides an easy way of performing several types of classification .
it also has no restriction on the size of data and is time efficient.
hence, we completed the analysis by performing a test on the whole los alamos hiv dataset .
for cgs , castor completes the test in  <dig> min  <dig> s with an accuracy of  <dig> %.
while for the pol fragments , it requires 20min10s with an accuracy of  <dig> %.
it shows that castor takes  <dig> s to process a sequence that is far more efficient than the time results indicated in  <cit>  for rega , but 10-fold less efficient than comet   <cit> .
furthermore, due to size issues, it is not possible to perform such large analyses in actual version of comet server.
overall, castor highlights a good accuracy on the classification of the three studied viruses.
however this accuracy is slightly lower than specific virus predictors as shown previously.
but it exhibits more analysis capacity, permitting several and highly accurate set of classifications.
as shown in table  <dig>  this accuracy is higher than 90% for almost all studies except for comparing hiv- <dig> m pure subtypes vs crfs.
for less complex genomes such as hpv and hbv, the mean of weighted f-measures is higher than  <dig> .
castor will allow to increase the class representatives, to add or remove classes and also to benchmark several types of classification.
for viruses without existing predictors, it could accurately cover the needs as it is for hpv, instead of relying on the similarity sequence search such as blast  <cit>  or usearch  <cit> .
sequence search is generally not recommended for subtyping since it will not allow the identification of novel forms, it cannot also aggregate common attributes of a class while predicting  <cit> .
castor web platform
castor is available as a public web platform.
it is composed of four main applications.
castor-build allows users to create and train new classifiers from a set of labeled virus sequences.
it contains default parameters and advanced options letting users to customize the classifier parameters.
it can be used also to update the parameters or input sequences of an already built classifier.
the constructed classifiers can be saved in an exportable file locally or published to the community via castor-database described below.
castor-optimize constructs improved classifiers.
unlike castor-build that allows users to define metrics, algorithms and feature selection techniques, it assesses all combinations of the classification parameters and provides the best fitting classifier according to the input data.
castor-predict is the kernel application that allows users to annotate viral sequences according to a chosen classifier.
also, it serves as an evaluation module for classifiers with labeled test sets.
the results are provided with enriched graphics and performance measures  castor-database is a public database of classifiers which allows the community to share their expertise and models.
it facilitates experiment reproducibility and model refinement.
a characteristic viewer and a search engine of the published classifiers are also implemented.
hence, from the interface of castor-database, users can download, reuse, update and comment the classifiers.
to the best of our knowledge, castor constitutes the first rflp-based prediction platform for the classification of viral sequences.
CONCLUSIONS
in this paper, we have shown that rflp has a great performance in large scale sequence classification.
we also provide castor, the first viral sequence classification platform based on rflp.
we claim that castor can perform well for different types of viruses  with mean of weighted f-measures >  <dig>  in most cases .
in the future, we will attempt to increase the performance by modelling the boundaries of the classes and including an open-set approach to deal with instances from unknown classes.
the castor platform implements several metrics and classifiers, allowing generic and diverse analyses within the same environment.
castor allows the storage of models enabling reproducible experiments and open data access.
even though castor is scaled for viruses, it can be used and extended easily for other types of organisms, including whole genome and partial sequences.
in the future, more models will be included, in particular those specialized in less studied organisms and/or without dedicated tools.
in addition, scientists could add their tuned models helping castor to enhance the predictions.
we will also optimize the platform to allow other types of classification such as functional, disease related and geographical classifications.
hence, castor could quickly become a reference in comparative genomics focusing on various types of sequence classification.
additional file
additional file  <dig> supplementary data.
this pdf file contains supplementary table s <dig> and supplementary figures s1–s <dig>
abbreviations
adaadaboost
bagbagging
dnadeoxyribonucleic acid
fnfalse negative
fpfalse positive
fprfalse positive rate
hbvhepatitis b viruses
hivhuman immunodeficiency viruses
hpvhuman papillomaviruses
ibkk-nearest neighbors
j48c4
<dig> decision tree; mdsmultidimensional scaling nba: naive bayes classifier
rflprestriction fragment length polymorphism
rftrandom forests
rmsroot mean square
svmsupport vector machine
tntrue negative
tptrue positive
tprtrue positive rate

 genomic sequence classification assigns a given sequence into its related group of known sequences with similar properties, traits or characteristics. it is a fundamental practice in different research areas of microbiology yielding major challenges in comparative genomics. accurate genomic sequence classification and typing could help to enhance the phylogenetics and functional studies of viruses. they also help in determining pathogenicity, developing vaccines, studying epidemiology and drug resistance. recent advances in dna sequencing and molecular biology techniques provide an immense collection of genomic information. such data volume raises challenges for genetic-based classification techniques. three main approaches have been designed and implemented to classify different types of viruses based on their genomic sequence characteristics. the first is sequence alignment-based approach which is widely used, e.g. in similarity search methods and in pairwise distance based-methods. the second is phylogenetic-based approach. it is implemented in several tools, e.g. rega and pplacer. the aim of these methods is to place an unknown sequence on an existing phylogenetic tree of a set of reference sequences. each time a given sequence has to be classified, it is realigned with the set of reference sequences. then, either a new phylogenetic tree is inferred or the given sequence is placed in the existing tree. the third is alignment-free approach including methods based on nucleotide correlations and sequence composition. it transforms sequences or their relationships to feature vectors and then constructs a phylogeny, a statistical model or a machine learning model. these methods are reviewed in vinga and almeida, mantaci et al., xing et al. and bonham-carter et al.. restriction fragment length polymorphism, a molecular biology technique, is used to type different virus strains. several algorithmic approaches have tackled theoretical and experimental problems related to the restriction enzyme data such as restriction mapping problem, phylogeny estimation, snp genotyping and analysis of rflp digitized gel images. however, large scale computational sequence classification based on the rflp technique is not yet covered in literature. due to the genetic polymorphism in dna sequences, fragments resulting from enzyme digestions are different in terms of number and length between individuals or types. a set of restriction enzymes grounds a fragment pattern signature for each sequence. therefore, similar sequences ought to have similar fragment patterns and thus similar restriction site distributions. this a priori knowledge could be used to build a machine learning model where sequences are represented by restriction site distributions as a feature vector and a class feature corresponding to a taxonomic level. in this paper we introduce castor, a machine learning web platform, to classify and type sequences. castor integrates a new alignment-free method based on the rflp principle. our in silico method is independent of the sequence structure or function and is also not organism-specific. castor is designed to facilitate the reuse, sharing and reproducibility of sequence classification experiments. methods overview of the approach in this paper, we propose an in silico approach to identify and classify viral dna sequences based on their restriction enzyme sites using supervised machine learning techniques. like other supervised learning approaches, the proposed one is divided into two main units. the classifier construction unit builds and trains classification models. it requires a set of reference viral genomic sequences, their classes and a list of restriction enzyme patterns. it starts by creating a training set including a group of feature vectors. the latter is computed from the distribution of the restriction site patterns on the given dna sequences and then refined by feature selection methods. a collection of learning classifiers are then trained and evaluated using 10-fold cross validation in order to choose the best classifier. the second unit is intended to predict the classes or annotations of given viral sequences. the inputs of this unit are a classifier, a set of dna sequences and the same list of restriction enzyme patterns used to train the classifier. fig. overview of castor kernel architecture. the kernel is composed of two main units. white rectangles represent input and output data; grey and curved rectangles represent processes. ts and vs are training set and validation set, respectively restriction fragment pattern-based features here, we propose a set of features simulating the outcome of the rflp technique. from rebase database, we extracted a list of type ii restriction enzymes and their recognition sites. type ii family cleaves dna sequences precisely on each occurrence of the recognition site. then, the restriction digestion of dna sequences is computationally simulated. in order to build a training set, for a sequence s and enzyme z we compute two metrics representing the distribution of the digested fragments: the number of cuts of the enzyme ) and the root mean square of digested fragment lengths ) calculated as rms=1n∑i=1nli where n is the number of fragments +1) and l i is the length of the i th fragment in linear genomes. for circular genomes n=c u t. other metrics could be easily computed from the fragment digestion to construct the feature vectors. feature selection methods the selection of an optimal subset of features improves the learning efficiency and increases the predictive performance. feature selection techniques reduce the learning set dimension by pruning irrelevant and redundant features. two relevant methods of feature reduction are provided. the first method ranks the features according to their information gain and selects a subset of top-k features. information gain estimates the mutual information between a feature and the target class. the second method uses the spearman’s rank correlation coefficient to construct a set of uncorrelated features. the correlation coefficient between two feature ranking vectors u and v of size n is computed as follows: ρ=1−6∑i=1n2n. a two-tailed p-value is computed to test the null hypothesis which states that two feature vectors are uncorrelated. in order to remove one of the two correlated features, two strategies could be used: discarding the feature with the largest sum of absolute correlation coefficients or the one with the smallest information gain score. learning and evaluation we explored three types of classifiers: symbolic methods and random forests ), statistical methods, support vector machine and k-nearest neighbors ) and ensemble methods and bagging both combined with j48); see additional file 1: table s for more details. a 10-fold cross-validation strategy is used to assess the performance of the trained classifiers. performance measures are weighted according to the number of instances and computed for the overall classification. the performance measures are: 3),fpr=fp/,precision=tp/,f−measure=2×tpr×precisiontpr+precision. where tp, tn, fp, and fn are the number of true positive, true negative, false positive and false negative predictions, respectively. tpr and fpr are the true positive rate and the false positive rate, respectively. we used weka data mining program to perform the training and the evaluation. to include a negative class in the training sets, two approaches could be used. first, provide manually constructed negative class from collected relevant data. second, build it with the provided negative class generator. this generator constructs altered sequences data from a sampling with replacement of the positive set sequences. to alter the sampled sequences, we reshape the rflp length distribution of the training set by randomly shrinking, expanding or keeping unchanged the length of the sampled sequences. then, each sequence is randomly shuffled while preserving k-mer counts. datasets in this study, we applied our approach to a wide range of viruses. we selected one dsdna virus ), one dsdna-rt virus ) and one ssrna-rt virus ). hpvs have a circular double stranded dna genome of ∼ bp and belong to five genera. hpvs belonging to a genus share over 53% identity of their complete genomes and ones in the same species level share over 62% of identity. we assessed the performance of hpv classification in the genus and species taxonomic levels. at the species level, we selected only the alpha hpv genus representing the most abundant and diverse genomes in databases. it is divided into thirteen species. unfortunately, some hpv genera and alpha hpv species were underrepresented and were therefore discarded. hbv genomes are smaller and are circular partly double stranded dna. hbvs are classified into eight genotypes with at least 8% divergence among their genomic sequences. we evaluated the performances of our method for the genotyping of hbv strains. hpv and hbv complete genome sequences were downloaded from the ncbi refseq database. the taxonomic annotations were extracted from the ncbi taxonomy database. hiv- genomes have two copies of positive-sense single-stranded rna with ∼ bp. phylogenetically, hiv- strains are divided into four groups: m, n, o and p. m group strains are worldwide prevalent. they are categorized into pure subtypes and recombinant forms. genetic variations among subtypes are about 20–30% for env gene, 7–20% for gag gene and 10% for pol gene. for hiv- classification, we studied complete genomes and fragments covering pol gene from the position to with respect to hxb reference sequence and having a minimum size of kbp. hiv- sequences were extracted from the los alamos hiv sequence database. for all the datasets, only complete, curated and well-annotated sequences were selected. moreover, each class ought to have an adequate number of genomic sequences in order to have a representative genetic diversity. simulation studies raw viral sequence datasets, described above, were class-size imbalanced, i.e., the difference in the number of genome sequences belonging to each class was relatively large. generally, epidemiological studies are conducted on host-specific viruses with the highest prevalence and pathogenicity. this leads to more data for some groups of viruses over others. usually, training standard classifiers on imbalanced datasets affects their performance and misleads the interpretation of their accuracy. under-sampling majority class approach has been shown to perform well and could be used with standard algorithms. hence, from each previous dataset, we randomly performed under-sampling, without replacement, of the larger classes to have relatively the same sizes as the other classes. in order to identify the best parameters of the classifiers, we randomly sampled datasets for each of the hpv genera, hpv alpha species, hbv genotypes, hiv- m subtypes cgs and hiv- m subtypes pol fragments data. for each obtained sample, we performed a 10-fold cross-validation study with different classifiers built as follows. we constructed all the combinations of the two metrics, the two feature selection methods and the seven learning algorithms. this construction yielded c o m b i n a t i o n s∗ d a t a s e t s= e x p e r i m e n t s for each virus classification.  the results section is divided into four parts: first, we show how the rflp signatures are suitable for viral classification; second, we assess the performance of several competing classification algorithms on different virus datasets; third, we compare the prediction made by castor against widely used methods for hiv- datasets, one of the most difficult to classify and fourth, we present the castor web platform. classification with rflp signatures in virus familiesi l h o u e t t e a in hpv alpha and hpv gamma. with castor, the best hpv alpha species classification obtains a tpr of and fpr of in 10-fold cross-validation analyses of instances. the power of rflp cuts in classification of viruses could be observed in hbv genotypes heatmap. hbv highlights three genotypes with c o h e s i o n i n d e x e s for most instances above indicating very coherent classes. but b and c genotypes have values between and. the s i l h o u e t t e i n d e x plots show several instances of b, c, e and g genotypes that have an striking disagreement with their assigned classes. even with these constraints, castor achieves the genotyping of hbv instances with tpr of and fpr of according to a 10-fold cross-validation study. the hiv- cut site patterns have more variability among pure subtypes and crfs. likely, the mds plot shows a moderate subtype clustering for the main hiv- subtypes. but this clustering is not well separated compared to hpv and hbv. this variability among classes is reflected in low values of the c o h e s i o n i n d e x. all, suggesting either variability, noise or mislabelling. for instance, >30% of hiv- b and hiv- c instances tend to have rflp cut patterns of other subtypes. with castor, the subtyping of hiv- group m within main subtypes was assessed for instances with a tpr of and fpr of. fig. class cohesion of three virus datasets. the four columns illustrate the separability and compactness of three virus complete genomes datasets based on restriction enzyme cuts. the first column shows heatmaps of cut clustered by x-axis. the samples in the y-axis are grouped by studied classes followed by intra-class clusterings. the second column shows mds of the cut distances between samples. the third and fourth column represent, respectively, the cohesion and silhouette indexes of the classes. a classes in hpv are alpha species, beta and gamma genera. b classes in hbv are a-h genotypes c classes in hiv- are m pure subtypes and crfs tpr fpr f-measure this table contains the best results of the experimental study performed on the different datasets. the evaluation measures are obtained with 10-fold cross-validation analysis. the column classifier id contains the corresponding models available in castor platform previously, it has been clearly shown that rflp has a power for classification in several viruses such as hpv, hbv and hiv. but these studies are mostly limited to two to five classes. to the best of our knowledge, our study constitutes the first large scale and multi-class analyses of rflp cut for classification. it provides the basis to explore large and various types of classifications, in particular those based on machine learning methods. machine learning classifier tuning and performance the castor platform relies on machine learning methods for the classification of viruses based on rflp signatures of nucleotide sequences. the platform is detailed in the castor web platform section. three important parameters constitute the kernel of each castor classifier: a metric, a feature selection method and a learning algorithm. to assess the different combination of the models, we performed a 10-fold cross-validation of the experiments associated to each of the five datasets. from the overall results of the five virus classifications, it is not obvious to distinguish the best candidate between cut and rms metrics. in the genotyping of hbv, cut performs better than rms while in the hpv genera and species classifications rms performs better than cut. however the mean of weighted f-measures for both methods is in all cases ≥. the same analyses were performed on hiv- cgs and pol fragments. cut performs slightly better than rms in both datasets when comparing the mean of weighted f-measures. due to the variability of hiv- the mean of weighted f-measures falls to in cgs and in pol fragments. hence for the remaining of our study, we will fix the rflp metric according to its performance on the corresponding datasets. additional file 1: figure s presents the comparative analyses of the two feature selection methods in the experiments for each dataset. the mean of weighted f-measures of the two feature selection methods are not statistically different in all datasets. in fact, the results of the two methods are correlated for the three viruses with the spearman’s rank correlation coefficient ranging between and. in these simulations, the seven learning algorithms have various performances according to the different datasets. the algorithm j has the worst weighted f-measure values. however, its performance improves when combined with rft or bag algorithms. in general, svm performs better in four of five datasets with mean of weighted f-measures > and ranks number one in hpv alpha species, hbv genotypes and hiv- subtypes classifications and four in hpv genera classification. it is followed by rft, nba and ibk. however, rft and nba are affected by a large variance. these rankings are clearly observable on additional file 1: figure s and figure s presenting respectively the correlations cut/rms and topattribute/correlation grouped by algorithms. while most algorithms have similar performance with cut or rms, naive bayes surprisingly performs better with cut. fig. learning algorithm evaluation on five datasets. this figure illustrates the f-measure distribution of seven learning algorithms on the prediction of a hpv genera, b hpv alpha species, c hbv genotypes, d hiv- m subtypes with complete genomes e hiv- m subtypes with pol fragments. hpv and hbv datasets are complete genomes. the number below each boxplot corresponds to the statistically discriminative rank of the algorithms. the ranking is performed with paired student’s t test. μ, σ are the mean and the standard deviation of the overall f-measures, respectively. p is the p-value of the statistically significance of the weighted f-measure mean differences among the algorithms computed with the wilcoxon/kruskal-wallis test assessing the performance castor on hiv- data castor exhibits high accuracy for different hiv- classificationtable evaluation of hiv- classification with castor tpr fpr f-measure this table contains the tpr, fpr and f-measure of hiv- classifications obtained with 10-fold cross-validation analysis. for each classification, the number of corresponding classes and instances are given. the range indicates the interval of instance frequencies per class used during the training of each model. the column classifier id contains the corresponding models available in castor platform comparing comet, rega and castor next, we compared the performance of castor against the most powerful and widely used hiv- specific predictors namely comet and rega version. these comparisons are based on cg as well as pol fragment data. it is important to notice that these programs are fixed and do not allow neither any change on the trained classes nor new training samples. here the actual training of comet and rega includes respectively and classes for either cg or pol fragments. to avoid under-represented classes, castor was trained on classes for cgs and classes for pol fragments. we performed three comparisons. the first, named complete sampling, assesses the performance of each method on percent of randomly sampled los alamos hiv data. this sampling permits to assess the performance of the predictors to fit realistic data with unknown classes. the second, named specific subtypes, focuses, for each method, only on the corresponding trained subtypes. the third, named common subtypes, compares the performance of the methods on the intersection of the trained subtypes. this strategy is used due to the fact that the training of comet and rega cannot be changed. thus, it is difficult to adapt or perform other classification studies or larger benchmark analyses. figure shows that for cgs, rega performs the best followed by castor and for pol fragments comet outperforms, followed again by castor. in the two types of data, when not performing the best, rega or comet performance drops drastically by more than 10% and ranks at the third position. meanwhile castor ranks second in both two types of data. with cgs, castor obtains a correct classification of % against the sampling of los alamos hiv data when rega obtains %. but when testing predictors on their trained classes, the percentage of correct classification drastically increases to and % respectively for rega and castor. this result remains almost the same when comparing only the common trained classes among the three predictors. these common classes cover and 93% of the overall instances of the sampling of cgs and pol fragments, respectively. the mean tpr of castor is higher than in the case of either pure subtypes or crfs. the tpr of rega drops to when assessing crfs and remains almost perfect for pure subtypes. in pol fragments, comet outperforms castor and rega in all comparisons. applying the three methods, comet, rega and castor, on 10% random sampling of los alamos hiv data, the percentages of correct classification were, and %, respectively. this result is confirmed when comparing only the common trained classes where comet reaches % and castor %. note that rega could not perform higher than 76% and has a mean tpr of for pure subtypes competing with comet. in crf instances, comet and castor obtain almost an equal mean of tpr around. rega cannot perform well in crf classification and has a mean of tpr equal to. castor has higher fpr values compared to the two other programs in overall classifications. this fact is not surprising since rega and comet are specifically tuned to predict hiv data. their predictions with lower scores tend to be discarded or ambiguous. for instance, comet has 32% of its cg predictions that are unassigned as well as 5% of its pol fragment predictions. hence, these numbers are higher than the false positive values of castor, but they are not included in the fpr computation. however, it will be interesting to include in castor a threshold of inclusion of a given sequence into a class. this could help reducing the fpr but it would require deeper analyses. it also should be associated to the open-set classification problem that is beyond the scope of this paper. fig. performance of castor with comet and rega predictors on hiv- datasets. the panels a and b show the percentage of correct classifications for hiv- complete genomes and hiv- pol fragments, respectively. the number of instances and the associated classes for each sampling is presented above the panels. complete sampling corresponds to 10% of los alamos hiv data selected randomly. in specific subtypes sampling, the predictors are assessed against their trained classes. in common subtypes sampling, the predictors are assessed against the intersection of the classes of the three trained predictors tpr fpr f-measure tpr fpr f-measure tpr fpr f-measure this table contains tpr, fpr and f-measure of comet, rega and castor on the prediction of hiv- m pure subtypes and cfrs complete genomes. the shown classes belong to the common subtypes sampling. the castor model used in this evaluation is pmshiv02 tpr fpr f-measure tpr fpr f-measure tpr fpr f-measure this table contains tpr, fpr and f-measure of comet, rega and castor on the prediction of hiv- m pure subtypes and cfrs pol fragments. the shown classes belong to the common subtypes sampling. the castor model used in this evaluation is pmshiv03 even though castor is not a specific hiv- classifier, it competes with the most powerful methods in hiv- unlike comet and rega, castor provides an easy way of performing several types of classification. it also has no restriction on the size of data and is time efficient. hence, we completed the analysis by performing a test on the whole los alamos hiv dataset. for cgs, castor completes the test in min s with an accuracy of %. while for the pol fragments, it requires 20min10s with an accuracy of %. it shows that castor takes s to process a sequence that is far more efficient than the time results indicated in for rega, but 10-fold less efficient than comet. furthermore, due to size issues, it is not possible to perform such large analyses in actual version of comet server. overall, castor highlights a good accuracy on the classification of the three studied viruses. however this accuracy is slightly lower than specific virus predictors as shown previously. but it exhibits more analysis capacity, permitting several and highly accurate set of classifications. as shown in table this accuracy is higher than 90% for almost all studies except for comparing hiv- m pure subtypes vs crfs. for less complex genomes such as hpv and hbv, the mean of weighted f-measures is higher than. castor will allow to increase the class representatives, to add or remove classes and also to benchmark several types of classification. for viruses without existing predictors, it could accurately cover the needs as it is for hpv, instead of relying on the similarity sequence search such as blast or usearch. sequence search is generally not recommended for subtyping since it will not allow the identification of novel forms, it cannot also aggregate common attributes of a class while predicting. castor web platform castor is available as a public web platform. it is composed of four main applications. castor-build allows users to create and train new classifiers from a set of labeled virus sequences. it contains default parameters and advanced options letting users to customize the classifier parameters. it can be used also to update the parameters or input sequences of an already built classifier. the constructed classifiers can be saved in an exportable file locally or published to the community via castor-database described below. castor-optimize constructs improved classifiers. unlike castor-build that allows users to define metrics, algorithms and feature selection techniques, it assesses all combinations of the classification parameters and provides the best fitting classifier according to the input data. castor-predict is the kernel application that allows users to annotate viral sequences according to a chosen classifier. also, it serves as an evaluation module for classifiers with labeled test sets. the results are provided with enriched graphics and performance measures castor-database is a public database of classifiers which allows the community to share their expertise and models. it facilitates experiment reproducibility and model refinement. a characteristic viewer and a search engine of the published classifiers are also implemented. hence, from the interface of castor-database, users can download, reuse, update and comment the classifiers. to the best of our knowledge, castor constitutes the first rflp-based prediction platform for the classification of viral sequences.  in this paper, we have shown that rflp has a great performance in large scale sequence classification. we also provide castor, the first viral sequence classification platform based on rflp. we claim that castor can perform well for different types of viruses with mean of weighted f-measures > in most cases. in the future, we will attempt to increase the performance by modelling the boundaries of the classes and including an open-set approach to deal with instances from unknown classes. the castor platform implements several metrics and classifiers, allowing generic and diverse analyses within the same environment. castor allows the storage of models enabling reproducible experiments and open data access. even though castor is scaled for viruses, it can be used and extended easily for other types of organisms, including whole genome and partial sequences. in the future, more models will be included, in particular those specialized in less studied organisms and/or without dedicated tools. in addition, scientists could add their tuned models helping castor to enhance the predictions. we will also optimize the platform to allow other types of classification such as functional, disease related and geographical classifications. hence, castor could quickly become a reference in comparative genomics focusing on various types of sequence classification. additional file additional file supplementary data. this pdf file contains supplementary table s and supplementary figures s1–s abbreviations adaadaboost bagbagging dnadeoxyribonucleic acid fnfalse negative fpfalse positive fprfalse positive rate hbvhepatitis b viruses hivhuman immunodeficiency viruses hpvhuman papillomaviruses ibkk-nearest neighbors j48c4 decision tree; mdsmultidimensional scaling nba: naive bayes classifier rflprestriction fragment length polymorphism rftrandom forests rmsroot mean square svmsupport vector machine tntrue negative tptrue positive tprtrue positive rate 
results reveal true positive rates of 99%, 99% and 98% for hpv alpha species, hbv genotyping and hiv- m subtyping, respectively. here, we introduce a virus classification platform, castor, based on machine learning methods. the castor web platform provides an open access, collaborative and reproducible machine learning classifiers. castor is inspired by a well-known technique in molecular biology: restriction fragment length polymorphism. it simulates, in silico, the restriction digestion of genomic material by different enzymes into fragments. furthermore, castor shows a competitive performance compared to well-known hiv- specific classifiers on whole genomes and pol fragments.
 advances in cloning and sequencing technology are yielding a massive number of viral genomes. the classification and annotation of these genomes constitute important assets in the discovery of genomic variability, taxonomic characteristics and disease mechanisms. existing classification methods are often designed for specific well-studied family of viruses. thus, the viral comparative genomic studies could benefit from more generic, fast and accurate tools for classifying and typing newly sequenced strains of diverse virus families.  here, we introduce a virus classification platform, castor, based on machine learning methods. castor is inspired by a well-known technique in molecular biology: restriction fragment length polymorphism. it simulates, in silico, the restriction digestion of genomic material by different enzymes into fragments. it uses two metrics to construct feature vectors for machine learning algorithms in the classification step. we benchmark castor for the classification of distinct datasets of human papillomaviruses, hepatitis b viruses and human immunodeficiency viruses type. results reveal true positive rates of 99%, 99% and 98% for hpv alpha species, hbv genotyping and hiv- m subtyping, respectively. furthermore, castor shows a competitive performance compared to well-known hiv- specific classifiers on whole genomes and pol fragments.  the performance of castor, its genericity and robustness could permit to perform novel and accurate large scale virus studies. the castor web platform provides an open access, collaborative and reproducible machine learning classifiers. castor can be accessed at http://castor.bioinfo.uqam.ca. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords sequence classificationpredictionvirus classificationissue-copyright-statement© the author 2017 