BACKGROUND
one of the important challenges in the post-genome era is determining the functional role of all genes in the cell although about one-third of the genes have been annotated and deposited in database such go  <cit> .
with the recent invention of several large-scale experimental methods, a wealth of functional genomic data was accumulated, including sequence, micro-array expression profile and protein-protein interaction data.
these large data-sets have fueled an interest in computational approaches to gene function prediction, which promises to harness the information present in these large collections of data to automatically deduce accurate gene annotations  <cit> .
furthermore, many works have shown that integration of different kinds of data sources can considerably improve prediction results  <cit> .
go is a widely-used set of functional terms with which some genes are annotated, we also call functional terms as functional classes in related to classification problem from machine learning.
go functional annotation associates each gene or gene product to some functional terms.
for an unknown gene, predicting its functions will assign some go functional terms to it, which is called multi-label classification problem in machine learning community.
the mainstream approach is to transform it into a binary classification task for each functional class, which focuses on training a classifier such as svm  with some labeled positive and negative examples.
however, the available information from the annotation databases, such as go  <cit> , is only about positive examples, i.e.
for a functional class, we only know which gene is assigned to it, but we are not sure that a gene has no this function except for too few genes.
as a result, when training classifier for a functional class, we can only obtain labeled positive examples and many unlabeled ones.
in other words, for a functional class, we need to learn a classifier from positive and unlabeled examples.
thus, an important step is to select a suitable set of negative examples from unlabeled examples before training classifier.
some approaches to select negative examples have been proposed.
for example, lanckriet et.
al labeled the annotated genes as positive examples and the remaining ones as negative ones for each functional class  <cit> .
carter et.al randomly selected the negative examples with the same size as the positive examples from the unlabeled examples  <cit> .
we call these two methods twoclass and twoclassbal algorithm respectively.
chunlin wang et.al selected a set of negative examples in two steps: firstly, identifying genes which are far from each other and the most dissimilar to positive examples as initial negative examples set.
then, using iteratively svm to expanse negative examples and stopping while the remaining unlabeled examples are less than given threshold.
their method is called psol and its detail can be found in  <cit> .
above approaches can be divided into two categories and some problems can occur when only few positive examples and major unlabeled ones are given:  <dig>  regarding all unlabeled examples as negative examples  <cit> .
on the one hand, it may lead to class imbalance problem because of few positive examples  <cit> .
on the other hand, the false negative noise may seriously decrease the prediction accuracy.
<dig>  selecting negative examples with same size as positive examples  <cit> .
these methods eliminate the impact of imbalanced problem, but, only few negative examples can be selected, as a result, the classifier is trained on a small training set and easily leads to over-fitting.
when we use go annotation, many functional classes have few annotated genes, which will lead to a lower prediction accuracy and need to be solved  <cit> .
in this paper, aiming at both imbalance and over-fitting problem for genes function prediction with only few positive examples and unlabeled examples, we propose a novel strategy for predicting genes function using svm.
firstly, we create some synthetic positive examples with few negative noises to enlarge positive examples set p. secondly, we extract a representative negative example set rn from unlabeled genes u using svm iteratively.
finally, an optimal svm classifier with rbf  is trained by using grid-search technique.
this method is called spe_rne.
RESULTS
experiment setting
data sets
gene annotation
we used gene ontology and corresponding gene function association of yeast  <cit>  released in april  <dig>  gene association file contained  <dig>  genes ,the number of known and unknown genes is  <dig>  and  <dig>  respectively.
we up-propagate the gene annotation along go hierarchical structure and obtained a reduced go which has only  <dig> go terms under guidance of biological experts.
to compare the algorithm performance, we divide them into four groups according to number of annotated genes as shown in table  <dig>  there are  <dig> functional classes with annotated genes less than  <dig> among total  <dig> terms.
<dig> functional terms are divided into four groups according to number of annotated genes.
the first row are four groups with interval of genes number.
the second row is number of terms.
protein sequence
the protein sequence of all of the yeast genes were downloaded from sgd  <cit> .we applied the smith-waterman pairwise sequence alignment algorithm  <cit>  to these sequences.
each protein is represented as a vector of smith-waterman log e-values, and computed with respect to all  <dig>  yeast genes.
a 5873* <dig> similar matrix is obtained.
microarray expression profile
microarray datasets are real-valued matrices measuring gene expression levels under different experimental conditions.
we use gene expression microarray data from the stanford microarray database  <cit>  containing results from several publications, providing a total of  <dig> real-valued features for all  <dig>  genes.
microarray entries typically include missing values due to experimental imperfections.
we estimate such entries using the widely accepted knnimpute algorithm  <cit>  with default k value.
then, we computed similarity between two genes using gauss kernel with γ =  <dig>  the second 5873* <dig> gene similar matrix is generated.
protein–protein interaction
we downloaded the protein-protein interaction data from biogrid <dig> .
<dig>  <cit> .
protein-protein interaction data is described as a graph in which nodes denote protein and edges denote interaction and diffusion kernel  <cit>  with diffusion constant β =  <dig> is used to measure the similarity between two proteins.
each gene is also represented as a vector of similarity with respect to all  <dig>  genes.
the third gene similar matrix is computed.
several previous researches have shown that integrating various genomic data to predict gene function can improve prediction accuracy  <cit> .
in this paper, we add three similar matrices and obtain a sum matrix.
it is noticeable that each matrix should be centralized and normalized to eliminate the effect from major data before adding them  <cit> .
while training svm classifier, this pre-computed kernel matrix is used.
experiment setting and evaluation
we used libsvm  <cit>  to implement spe-rne and related algorithms two class svm twoclass, two class balanced svm and psol in matlab.
first, we divided  <dig> known genes into training set and validation set, after training svm classifier on training set, the generalized performance of algorithms were compared on validation set.
widely-accepted measures, including precision rate p, recall rate r and their combination f <dig>  are used.
their definitions are as follows:
where tp,fp and fn denote the number of true positive, false positive and false negative respectively.
then, using  <dig>  unknown genes released in april  <dig> as test examples, we predict their functions and evaluate roc  score with gene function association released in december  <dig> as annotation standard.
performance comparison on known genes
for each functional class,  <dig> genes are in two categories: genes assigned to this functional class and unlabeled genes.
we randomly select  <dig> percent from these two categories as validation set, the others are training set.
svm classifiers are learned on training set and used to predict genes functions on validation set to evaluate generalized performance of algorithms.
when the number of negative examples is far more than positive examples, imbalanced problem occurs and the algorithm can not recall any true positive examples for some functional classes.
as a result, p =  <dig> and r =  <dig> result in f <dig> = nan  in matlab.
table  <dig> shows the number of nan for each functional group.
when the number of negative examples is far more than positive examples, imbalanced problem occurs and the algorithm can not recall any true positive examples for some functional classes.
as a result, p =  <dig> and r =  <dig> result in f <dig> = nan  in matlab.
table  <dig> shows the number of nan for each functional group.
as shown by table  <dig>  twoclass has the most serious imbalance and psol has more serious imbalance, but our method spe-rne, like twoclassbal, doesn’t suffer from imbalanced problem at all because we select reasonable quantity of negative examples after enlarging the positive examples set.
in addition, functional classes with few annotated genes have more serious imbalance.
for twoclassbal algorithm, while serious imbalance does not occur, the over-fitting may arise to affect prediction performance due to few training examples.
to evaluate the algorithm fairly, we set f <dig> = nan to f <dig> =  <dig>  for each algorithm and functional group, the means and variances of f <dig> are listed in table  <dig> and table  <dig> respectively.
in table  <dig>  although twoclassbal has not class imbalance problem, but it has worst performance because it has too few training examples, which easily causes over-fitting.
for functional classes with few annotated genes, the existed algorithms, like twoclass, twoclassbal, psol have lower f <dig> values, our algorithm significantly improves the f <dig> values in this case.
for functional classes with more annotated genes, our algorithm has better performance too.
while only few training examples are used to learn svm classifier, over-fitting problem may occur and make algorithms unstable.
we compute the variances of f <dig> for each functional group to evaluate the stability of algorithm.
table  <dig> shows that our algorithm has good stability.
predicting performance on unknown genes
since april  <dig>  some of  <dig> unknown genes have been annotated with some functions.
we consider these  <dig> genes as test examples and use trained svm classifier to predict function for them.
the go function association released in december  <dig> is regarded as complete annotation, that is, for each functional class, if a gene is assigned to it, the label is set to  <dig>  otherwise - <dig>  for each algorithm, the roc score, which is area under roc, is evaluated as comparison measures.
in previous section, we use f <dig> to evaluate algorithm performance because we think that go function association released in april  <dig> is incomplete.
the roc scores are listed in table  <dig>
roc score, that is area under roc curve, is a widely-accepted performance measure for prediction classification problem.
the larger roc score is, the better the performance of classification algorithm is.
for group  <dig> and  <dig>  our algorithm significantly improve the roc score, which illustrates better prediction performance for unknown genes.
for group  <dig>  we only add synthetic examples as many as positive examples, and for group  <dig>  we don’t create any synthetic positive examples.
but, our algorithm for extracting representative negative examples slightly improve the roc score too.
the average number of correctly predicted genes and true average number are displayed in figure  <dig> for each group.
in each group, our algorithm can recall more positive genes on average.
fig.
<dig> the average number of correctly predicted genes according to go association released in december  <dig> for unknown gene in april  <dig> in figure  <dig>  the height of bar denotes the average number of genes predicted correctly by four algorithms and average true number of genes on different groups.
predicting result on unknown genes
we list predicted functional classes for ten genes with most predicted functional terms in table  <dig>  these genes were unknown in april  <dig>  but they were annotated with one or multiple functional classes in december  <dig>
CONCLUSIONS
in this paper, we propose a novel approach to predicting gene function for genes with few positive examples and unlabeled ones spe-rne: creating synthetic examples to enlarge the set of positive examples, extracting representative negative examples from unlabeled examples and training svm classifier using grid-search technique.
for spe-rne, the validation on known gene data set shows its best f <dig> value and good stability.
prediction on unknown genes set illustrates its higher roc scores and better prediction performance than several classic algorithms.
all the algorithms run in a sum matrix which is obtained by adding simply several similarity matrixes from heterogeneous data sources, which may loss some information.
how to integrate effectively these heterogeneous data to predict gene function is our next research subject in future.
in addition, our method can also be used for other organisms such as human.

 one of the important challenges in the post-genome era is determining the functional role of all genes in the cell although about one-third of the genes have been annotated and deposited in database such go. with the recent invention of several large-scale experimental methods, a wealth of functional genomic data was accumulated, including sequence, micro-array expression profile and protein-protein interaction data. these large data-sets have fueled an interest in computational approaches to gene function prediction, which promises to harness the information present in these large collections of data to automatically deduce accurate gene annotations. furthermore, many works have shown that integration of different kinds of data sources can considerably improve prediction results. go is a widely-used set of functional terms with which some genes are annotated, we also call functional terms as functional classes in related to classification problem from machine learning. go functional annotation associates each gene or gene product to some functional terms. for an unknown gene, predicting its functions will assign some go functional terms to it, which is called multi-label classification problem in machine learning community. the mainstream approach is to transform it into a binary classification task for each functional class, which focuses on training a classifier such as svm with some labeled positive and negative examples. however, the available information from the annotation databases, such as go, is only about positive examples, i.e. for a functional class, we only know which gene is assigned to it, but we are not sure that a gene has no this function except for too few genes. as a result, when training classifier for a functional class, we can only obtain labeled positive examples and many unlabeled ones. in other words, for a functional class, we need to learn a classifier from positive and unlabeled examples. thus, an important step is to select a suitable set of negative examples from unlabeled examples before training classifier. some approaches to select negative examples have been proposed. for example, lanckriet et. al labeled the annotated genes as positive examples and the remaining ones as negative ones for each functional class. carter et.al randomly selected the negative examples with the same size as the positive examples from the unlabeled examples. we call these two methods twoclass and twoclassbal algorithm respectively. chunlin wang et.al selected a set of negative examples in two steps: firstly, identifying genes which are far from each other and the most dissimilar to positive examples as initial negative examples set. then, using iteratively svm to expanse negative examples and stopping while the remaining unlabeled examples are less than given threshold. their method is called psol and its detail can be found in. above approaches can be divided into two categories and some problems can occur when only few positive examples and major unlabeled ones are given: regarding all unlabeled examples as negative examples. on the one hand, it may lead to class imbalance problem because of few positive examples. on the other hand, the false negative noise may seriously decrease the prediction accuracy. selecting negative examples with same size as positive examples. these methods eliminate the impact of imbalanced problem, but, only few negative examples can be selected, as a result, the classifier is trained on a small training set and easily leads to over-fitting. when we use go annotation, many functional classes have few annotated genes, which will lead to a lower prediction accuracy and need to be solved. in this paper, aiming at both imbalance and over-fitting problem for genes function prediction with only few positive examples and unlabeled examples, we propose a novel strategy for predicting genes function using svm. firstly, we create some synthetic positive examples with few negative noises to enlarge positive examples set p. secondly, we extract a representative negative example set rn from unlabeled genes u using svm iteratively. finally, an optimal svm classifier with rbf is trained by using grid-search technique. this method is called spe_rne.  experiment setting data sets gene annotation we used gene ontology and corresponding gene function association of yeast released in april gene association file contained genes,the number of known and unknown genes is and respectively. we up-propagate the gene annotation along go hierarchical structure and obtained a reduced go which has only go terms under guidance of biological experts. to compare the algorithm performance, we divide them into four groups according to number of annotated genes as shown in table there are functional classes with annotated genes less than among total terms. functional terms are divided into four groups according to number of annotated genes. the first row are four groups with interval of genes number. the second row is number of terms. protein sequence the protein sequence of all of the yeast genes were downloaded from sgd.we applied the smith-waterman pairwise sequence alignment algorithm to these sequences. each protein is represented as a vector of smith-waterman log e-values, and computed with respect to all yeast genes. a 5873* similar matrix is obtained. microarray expression profile microarray datasets are real-valued matrices measuring gene expression levels under different experimental conditions. we use gene expression microarray data from the stanford microarray database containing results from several publications, providing a total of real-valued features for all genes. microarray entries typically include missing values due to experimental imperfections. we estimate such entries using the widely accepted knnimpute algorithm with default k value. then, we computed similarity between two genes using gauss kernel with γ = the second 5873* gene similar matrix is generated. protein–protein interaction we downloaded the protein-protein interaction data from biogrid.. protein-protein interaction data is described as a graph in which nodes denote protein and edges denote interaction and diffusion kernel with diffusion constant β = is used to measure the similarity between two proteins. each gene is also represented as a vector of similarity with respect to all genes. the third gene similar matrix is computed. several previous researches have shown that integrating various genomic data to predict gene function can improve prediction accuracy. in this paper, we add three similar matrices and obtain a sum matrix. it is noticeable that each matrix should be centralized and normalized to eliminate the effect from major data before adding them. while training svm classifier, this pre-computed kernel matrix is used. experiment setting and evaluation we used libsvm to implement spe-rne and related algorithms two class svm twoclass, two class balanced svm and psol in matlab. first, we divided known genes into training set and validation set, after training svm classifier on training set, the generalized performance of algorithms were compared on validation set. widely-accepted measures, including precision rate p, recall rate r and their combination f are used. their definitions are as follows: where tp,fp and fn denote the number of true positive, false positive and false negative respectively. then, using unknown genes released in april as test examples, we predict their functions and evaluate roc score with gene function association released in december as annotation standard. performance comparison on known genes for each functional class, genes are in two categories: genes assigned to this functional class and unlabeled genes. we randomly select percent from these two categories as validation set, the others are training set. svm classifiers are learned on training set and used to predict genes functions on validation set to evaluate generalized performance of algorithms. when the number of negative examples is far more than positive examples, imbalanced problem occurs and the algorithm can not recall any true positive examples for some functional classes. as a result, p = and r = result in f = nan in matlab. table shows the number of nan for each functional group. when the number of negative examples is far more than positive examples, imbalanced problem occurs and the algorithm can not recall any true positive examples for some functional classes. as a result, p = and r = result in f = nan in matlab. table shows the number of nan for each functional group. as shown by table twoclass has the most serious imbalance and psol has more serious imbalance, but our method spe-rne, like twoclassbal, doesn’t suffer from imbalanced problem at all because we select reasonable quantity of negative examples after enlarging the positive examples set. in addition, functional classes with few annotated genes have more serious imbalance. for twoclassbal algorithm, while serious imbalance does not occur, the over-fitting may arise to affect prediction performance due to few training examples. to evaluate the algorithm fairly, we set f = nan to f = for each algorithm and functional group, the means and variances of f are listed in table and table respectively. in table although twoclassbal has not class imbalance problem, but it has worst performance because it has too few training examples, which easily causes over-fitting. for functional classes with few annotated genes, the existed algorithms, like twoclass, twoclassbal, psol have lower f values, our algorithm significantly improves the f values in this case. for functional classes with more annotated genes, our algorithm has better performance too. while only few training examples are used to learn svm classifier, over-fitting problem may occur and make algorithms unstable. we compute the variances of f for each functional group to evaluate the stability of algorithm. table shows that our algorithm has good stability. predicting performance on unknown genes since april some of unknown genes have been annotated with some functions. we consider these genes as test examples and use trained svm classifier to predict function for them. the go function association released in december is regarded as complete annotation, that is, for each functional class, if a gene is assigned to it, the label is set to otherwise - for each algorithm, the roc score, which is area under roc, is evaluated as comparison measures. in previous section, we use f to evaluate algorithm performance because we think that go function association released in april is incomplete. the roc scores are listed in table roc score, that is area under roc curve, is a widely-accepted performance measure for prediction classification problem. the larger roc score is, the better the performance of classification algorithm is. for group and our algorithm significantly improve the roc score, which illustrates better prediction performance for unknown genes. for group we only add synthetic examples as many as positive examples, and for group we don’t create any synthetic positive examples. but, our algorithm for extracting representative negative examples slightly improve the roc score too. the average number of correctly predicted genes and true average number are displayed in figure for each group. in each group, our algorithm can recall more positive genes on average. fig. the average number of correctly predicted genes according to go association released in december for unknown gene in april in figure the height of bar denotes the average number of genes predicted correctly by four algorithms and average true number of genes on different groups. predicting result on unknown genes we list predicted functional classes for ten genes with most predicted functional terms in table these genes were unknown in april but they were annotated with one or multiple functional classes in december  in this paper, we propose a novel approach to predicting gene function for genes with few positive examples and unlabeled ones spe-rne: creating synthetic examples to enlarge the set of positive examples, extracting representative negative examples from unlabeled examples and training svm classifier using grid-search technique. for spe-rne, the validation on known gene data set shows its best f value and good stability. prediction on unknown genes set illustrates its higher roc scores and better prediction performance than several classic algorithms. all the algorithms run in a sum matrix which is obtained by adding simply several similarity matrixes from heterogeneous data sources, which may loss some information. how to integrate effectively these heterogeneous data to predict gene function is our next research subject in future. in addition, our method can also be used for other organisms such as human. 
a large amount of functional genomic data have provided enough knowledge in predicting gene function computationally, which uses known functional annotations and relationship between unknown genes and known ones to map unknown genes to go functional terms. however, from various annotation database, we can only obtain few positive genes annotation for most offunctional terms, that is, there are only few positive examples for training classifier, which makes predicting directly gene function infeasible. in test data and unknown genes data, we compute average and variant of measure f. the experiments showthat our approach has better generalized performance and practical prediction capacity. training binary classifier needs both positive examples and negative ones that have almost the same size. secondly, representative negative examples are selected by training svm iteratively to move classification hyperplane to a appropriate place. on combined kernel ofyeast protein sequence, microarray expression, protein-protein interaction and go functional annotation data, we compare spe_rne with other three typical methods in three classical performance measures recall r, precise p and their combination f: twoclass considers all unlabeled genes as negative examples, twoclassbal selects randomly same number negative examples from unlabeled gene, psol selects a negative examples set that are far from positive examples and far from each other. lastly, an optimal svm classifier are trained by using grid search technique. firstly, positive examples set is enlarged by creating synthetic positive examples.
 a large amount of functional genomic data have provided enough knowledge in predicting gene function computationally, which uses known functional annotations and relationship between unknown genes and known ones to map unknown genes to go functional terms. the prediction procedure is usually formulated as binary classification problem. training binary classifier needs both positive examples and negative ones that have almost the same size. however, from various annotation database, we can only obtain few positive genes annotation for most offunctional terms, that is, there are only few positive examples for training classifier, which makes predicting directly gene function infeasible.  we propose a novel approach spe_rne to train classifier for each functional term. firstly, positive examples set is enlarged by creating synthetic positive examples. secondly, representative negative examples are selected by training svm iteratively to move classification hyperplane to a appropriate place. lastly, an optimal svm classifier are trained by using grid search technique. on combined kernel ofyeast protein sequence, microarray expression, protein-protein interaction and go functional annotation data, we compare spe_rne with other three typical methods in three classical performance measures recall r, precise p and their combination f: twoclass considers all unlabeled genes as negative examples, twoclassbal selects randomly same number negative examples from unlabeled gene, psol selects a negative examples set that are far from positive examples and far from each other.  in test data and unknown genes data, we compute average and variant of measure f. the experiments showthat our approach has better generalized performance and practical prediction capacity. in addition, our method can also be used for other organisms such as human. 13– july the international conference on bioinformatics & computational biology las vegas, nv, usa 