BACKGROUND
over the last twenty years the genes underlying more than a thousand classically mendelian disorders have been successfully identified.
by contrast, only a relatively small number of genetic components of complex traits have been characterized  <cit> .
regions of interest identified through complex-trait linkage studies regularly exceed  <dig> centimorgans in size and can contain hundreds of genes.
the traditional candidate-gene approach to reducing this number of genes to a manageable level involves attempting to match functional annotation to knowledge of the disease or phenotype under investigation.
unfortunately this approach has been characterized by unsubstantiated and unreplicated claims  <cit> .
problems arise firstly because the link between genotype and phenotype in complex disorders tends to be weak; matching a single gene's functional annotation to a phenotype is unlikely to be successful unless the gene in question is clearly related to some known pathogenesis of the disease.
secondly, functional annotation of the human genome is incomplete and biased towards better studied genes which have higher levels of annotation.
furthermore, assigning functional annotation is a time-consuming process which is unavoidably error-prone  <cit>  and, if taken at face value, misannotated genes can mislead or delay researchers  <cit> .
van driel et al.
developed a web-based system for automating the annotation based candidate-gene approach  <cit>  that collates expression and phenotypic data from nine different databases and returns genes that conform to investigator-defined criteria.
recently several other candidate-gene identification systems that rely on grouping gene ontology  terms have been described  <cit> , notably pocus  <cit> , which finds genes across multiple susceptibility loci that share interpro  <cit>  domains and go terms.
these systems all rely on functional annotation to make correct predictions, but given that such annotation is incomplete and inherently biased towards a particular subset of genes, a more robust option might be to use sequence-based features instead.
it has been suggested that the genes underlying human hereditary disease share certain distinctive, sequence-based features such as larger gene size  <cit> .
by using machine learning algorithms we aimed to discover such common patterns that could be applied to create an automatic classification scheme capable of identifying genes more likely than not to be involved in disease.
machine learning has moved rapidly from the field of experimental artificial intelligence to that of applied science.
bioinformatics researchers have been quick to adopt machine learning algorithms in a variety of different situations and their use is now widespread  <cit> .
lopez-bigas et al.
recently presented a relatively successful decision tree created using such techniques  <cit>  which used amino-acid length and a measure of sequence conservation across species of genes as features to predict genes likely to be involved in hereditary disease.
our approach was related but examined a broader set of features and algorithms, producing a significantly more successful classifier that is able to predict genes involved in both mendelian and more complex traits.
we have also created a web interface to allow researchers to easily classify individual genes or whole regions of the genome and made it freely accessible at .
RESULTS
defining features and building the training set
a set of features was chosen based on a comparative study of ~  <dig>  known genes from ensembl  <cit>  which are not known to be involved in human disease and the  <dig>  ensembl genes also listed in online mendelian inheritance in man   <cit> .
the feature set  reflects the structure, content and phylogenetic extent  of each gene examined.
we included signal peptide and transmembrane domain predictions; though these are strictly speaking functional attributes they can be calculated with a high degree of accuracy directly from sequence.
we also found novel differences between the two sets of genes.
there was a small difference  in the number of cpg islands at the 5' end of genes listed in omim and those not, with slightly more genes listed in omim having 5' cpg islands, which are associated with both housekeeping genes and to a lesser extent tissue specific genes  <cit> .
there was also a significant difference  in the length of the 3' utr between genes listed in omim  and those not involved in disease .
there was also a significant disparity  in the distance to the nearest neighbouring gene – genes listed in omim had a median distance of  <dig> kb to their neighbours while genes not known to be involved in disease had a median distance of  <dig> kb.
to our knowledge these features have not been previously reported.
graphs showing the different distributions of selected features in the two sets are shown in figure  <dig>  though some of the differences we found have previously been described in literature, the discrepancy in 3' utr length has to our knowledge not been examined before and cannot be easily explained in terms of correlation to other, known feature differences.
two other novel features are the distance to the nearest neighbouring gene and the number of exons; both of these are quite strongly correlated to gene size .
we also studied the number of interpro domains in each set of genes and found significant differences but concluded that a bias existed towards better studied genes.
therefore we excluded this feature from our study .
automatic classifiers are created by being trained on a set of genes that has already been classified manually.
our training set of genes was made up of the  <dig>  genes found in both omim and ensembl  and  <dig>  ensembl genes not known to be involved in disease  which were selected at random from the larger set of ~  <dig>  as a representative sample.
choosing an algorithm
we used weka  <cit>  as the platform for our machine learning experiments.
a variety of different machine learning methods were examined but the alternating decision tree algorithm was chosen as the basis of our classification scheme as it couples high accuracy with a relatively small set of rules  <cit> .
the advantage of decision tree based schemes over other popular algorithms such as k-nearest neighbour, support vector machines and bayesian networks is that the rules that are produced for classifying instances can be interpreted more easily by non-expert users.
this is particularly true for the alternating decision tree algorithm, which typically produces trees that are just as predictive as those created by more traditional decision tree algorithms but that are far more concise and thus easier to understand.
alternating decision trees also allowed us to measure the contribution of each feature to the final classification of a gene, which might provide insight into the essential differences between those genes more and less likely to be involved in disease.
alternating decision trees are created by adding rules to the tree in an iterative fashion in the order of their predictive power, with the more effective rules being added first.
these rules are automatically derived from the differences between the disease and control genes in the training set provided.
a new rule is added to the tree either as a new "node" or as a child of an existing node.
with weka, the number of nodes to add to the tree is specified by the user before training begins.
too few nodes and the tree will be sparse, without enough cumulative discriminatory power to make confident classifications.
too many nodes, on the other hand, will result in an overly-complex tree where later nodes with weak predictive power can distort the effects of earlier, more predictive nodes.
on the basis of past experience we chose to limit the size of our alternating decision tree to fifteen nodes, which is a good balance of predictive power and complexity.
as each node represents a rule that tests a single sequence feature, this meant that of the two dozen sequence features available a maximum of fifteen would be used in the final tree.
an alternating decision tree with fifteen nodes was produced by training on the training set of genes and is shown in figure  <dig>  we also produced trees with ten and twenty nodes for comparison and discovered using the measurements described below that classifier performance was indeed poorer than with the fifteen node version .
the alternating decision tree
a gene is classified with the tree in figure  <dig> by beginning at the node marked "start" and then following each branch in turn.
upon reaching a node that contains an assumption – for example, that the gene length is larger than a given number – the "yes" or "no" branch is followed as appropriate.
if the relevant feature – the paralog percentage identity, for example – is "unknown", neither branch is followed.
adding up each of the numbers in rectangles that are encountered along the way results in a final score that reflects the relative confidence of the classification.
the classification itself is based on the sign of the score – if negative the gene is generally more likely to be involved in hereditary disease, if positive the gene is generally less likely to be involved in hereditary disease.
we tested the classifier on our training set of genes.
77% of the disease genes were correctly identified .
in contrast, 42% of the  <dig>  control genes were classified as disease genes .
as this is a predictive approach – we cannot say a priori how much of the genome and thus the representative sample in the training set is made up of genes that are involved in disease but are not yet characterized – at least some of these apparently incorrect classifications are likely to be correct.
we ran a tenfold cross-validation test to get a conservative estimate of how our classifier might perform on unseen data.
tenfold cross-validation is a widely used technique in machine learning and involves partitioning the whole training set into ten independent "folds" each with the same balance of disease genes and control genes.
the classifier is trained on nine of the partitions and tested on the remaining partition.
this is repeated until each partition has been tested on a new classifier built with the remainder of the training set and simulates the performance of the chosen algorithm and feature set on unseen data.
on average, 70% of the disease genes were correctly identified during cross-validation with 43% of control genes classified as false positives.
this is comparable to the results obtained by lopez-bigas et al.
<cit>  during cross-validation.
table  <dig> contains more detailed statistics relating to classifier performance.
as the alternating decision tree outputs a score that can be thresholded, it is a relatively simple matter to increase specificity  at the expense of sensitivity .
receiver operating characteristic  curves can be used to visualise classifier performance with different combinations of specificity and sensitivity.
the x-axis of a roc curve represents the fraction of false positives and the y-axis the fraction of true positives in the classifier results.
as the number of true positives  increases, so too does the number of false positives .
figure  <dig> shows the roc curves for the classifier on the training set and the two test sets which are described below.
we implemented our classifier as a standalone script in perl and designed an associated web interface to aid in the interpretation of the results produced.
the resulting software is named prospectr  and is freely accessible together with training and test sets of genes at .
the web interface allows researchers to quickly obtain scores for regions of the genome or individual genes of interest.
further testing
evaluating classifier performance on the training set alone is potentially misleading as over-fitting may have occurred.
over-fitting happens when a classifier generalises only to the extent necessary to work well on the training data, resulting in poor performance on data that was not seen during the training process.
cross-validation provides a measure of the performance of our approach in general, but doesn't reflect actual prospectr performance accurately as the alternating decision trees created for each fold are different.
we therefore created two test sets independent of the training set.
the first independent test set  contained  <dig> genes associated with disease listed in the human gene mutation database  <cit>  and  <dig> genes not known to be involved in disease that were picked at random from ensembl.
the second  contained  <dig> genes not known to be involved in disease and picked at random from ensembl and  <dig> genes not listed in omim but associated with different oligogenic disorders including inflammatory bowel disease, parkinsons, retinitis pigmentosa and autosomal recessive limb-girdle muscular dystrophy.
we were unable to obtain a sizeable, reliable set of genes involved in complex traits; this meant that classifier performance could not be tested on the components of complex disease.
this may change in the future as resources such as the genetic association database  <cit>  develop further and more association data becomes accessible.
71%  of the disease genes from the hgmd set and 72%  of the genes from the oligogenic set were correctly identified by the classifier, with 42%  and 41%  of control genes misclassified respectively.
these results are similar to those obtained on the training set, suggesting that over-fitting did not occur.
they also suggest that our sequence-based approach works equally well for finding genes involved in both oligogenic and monogenic disorders.
lopez-bigas et al  <cit>  used a larger set of disease genes during training.
only  <dig> of the genes from the hgmd set were independent of the training sets of both prospectr and the lopez-bigas classifier.
as a comparative measure, these  <dig> genes were scored using both classifiers.
prospectr correctly identified 72%  of the disease genes while the lopez-bigas classifier identified 47% .
prospectr, however, had a higher false positive rate, categorising ~ 44% of the whole human genome as likely to be involved in disease while the lopez-bigas classifier categorised ~ 31% of the whole human genome as likely to be involved in disease.
to see how this might have affected recall we calculated the kappa statistic  <cit>  for the results from both classifiers.
the kappa statistic is a measurement of agreement between predicted and actual classifications and takes false positive rates into account.
it is a number between  <dig>  and  <dig> .
on the independent hgmd set of  <dig> genes and assuming a false positive rate of 31%, the lopez-bigas classifier had a kappa statistic of  <dig>  while prospectr assuming a false positive rate of 44% had a kappa statistic of  <dig> , a factor of almost twofold.
this suggests that prospectr is substantially more adept than the lopez-bigas classifier at correctly classifying unseen data.
by ranking genes by score in descending order, it is possible for prospectr to create a list of genes for any given locus the top of which is enriched for genes that have a higher probability of being involved in disease.
to test this we took the hgmd set and for each gene created an artificial locus  <dig> mb in size consisting of the gene from the hgmd set and all known genes within  <dig> mb on either side on the same chromosome.
the gene taken from the hgmd set was in each case designated the "target gene" and by scoring each gene in the artificial locus and then ranking them we were able to see where the target gene appeared in the ordered list that was created.
for the  <dig> genes from the hgmd set the average number of genes per list was  <dig>  target genes were in the top 5% of the ordered list  <dig> times , top 10%  <dig> times , top 50%  <dig> times  and the top 75%  <dig> times .
we repeated the procedure for the  <dig>  genes listed in omim from our training set.
the average number of genes per list was  <dig> and target genes were in the top 5%  <dig> times out of  <dig>  and the top 50%  <dig> times .
the genes from the training and hgmd sets are mostly mendelian monogenic disorders; to see if the classifier was equally successful at enriching loci involved in more complex diseases we took the list of  <dig> genes likely to be involved in oligogenic disorders used as a test set by pocus  <cit> .
for these  <dig> genes involved in oligogenic disorders the average number of genes per list was  <dig> and the target gene was in the top 5%  <dig> times  and the top 50%  <dig> times .
figure  <dig> shows a graphical representation of these results.
performance on different types of mutation
gene records from the hgmd contain information about the number of different mutations associated with any phenotypes linked to that gene, split into three types: nucleotide substitutions, micro-lesions and gross lesions .
for example, the huntington gene  is recorded as being implicated in huntington disease, which is associated with a gross lesion.
the haemoglobin beta gene  is recorded as being implicated in sickle cell anaemia, associated with nucleotide substitutions.
of the hgmd set we used to test performance,  <dig> genes were associated with nucleotide substitutions only,  <dig> with gross lesions only and  <dig> with micro-lesions only.
we tested each subset separately to determine if the underlying cause of disease influenced prospectr's performance.
we found that 75% and 77% of the genes involved in disease and associated only with nucleotide substitutions or only with micro-lesions, respectively, were correctly identified by prospectr.
however, only 54% of the genes involved in disease and associated only with gross lesions were identified.
this suggests that the decision tree used by prospectr is better at identifying genes likely to be involved in disease because of small or point mutations than genes involved in disease because of more drastic events like gross deletions, insertions and chromosomal aberrations.
whole genome analysis
prospectr was used to score every known gene in the ensembl database on the likelihood that it is involved in human hereditary disease.
we normalised the score α given to each gene with the equation
where gamma  represents euler's constant so that it fell between  <dig> and  <dig> with higher scores suggesting a higher likelihood of involvement in disease.
<dig> genes had a score over  <dig> , of which  <dig>  are listed in either the hgmd or omim and are thus already known to be involved in disease .
by contrast, in the set of  <dig>  genes which scored less than  <dig>  only ~  <dig> %  are already known to be involved in disease.
a list of the  <dig> genes that scored higher than  <dig>  but are not already known to be involved in disease is included as supplementary material .
by searching for references in pubmed we discovered that  <dig> of these genes  are already candidates for involvement in diseases including alzheimers , osteoporosis  and schizophrenia .
discussion
relative performance
prospectr has a number of advantages over existing classification schemes designed to differentiate between genes more and less likely to be involved in disease.
prospectr appears to perform significantly better on unseen data than the decision tree classifier presented by lopez-bigas et al.
the lopez-bigas classifier is less likely to be useful as a predictive tool for two, related reasons: firstly, it achieves perfect accuracy when tested on the training set, even though the training set is known to be inconsistent.
the lopez-bigas classifier suggests that ~ 31% of the genome is made up of predicted disease genes.
thus if genes were picked at random to make up the control set during training it should be assumed that ~ 31% of them are actually disease genes which have not yet been characterized.
perfect accuracy on the training set is therefore undesirable – by ignoring the possibility that the set of control genes might contain disease genes the classifier loses flexibility and predictive power.
secondly, the fact that all uncharacterized disease genes were predicted as being control despite their presumed strong similarity  to other disease genes suggests that it is highly likely that at least some degree of overfitting occurred, which would further impair performance on novel data.
prospectr's use of a spread of sequence-based features representing the structure, content and phylogenetic extent of candidate genes allows investigators to see exactly which features are contributing the most towards a particular classification.
in addition, it requires no detailed phenotypic knowledge of the disease in question and can score whole chromosomes in minutes.
the use of sequence-based features avoids the bias inherent in current functional annotation, where better studied genes are far more likely to have better and more extensive annotation.
furthermore, by relying less on phylogenetic conservation we reduce the amount of potential bias from imperfect homology prediction .
classifier mechanics
other researchers have examined some of the sequence-based differences between genes listed in omim and genes not known to be involved in disease but there have been no comprehensive studies.
the data we present here collates all of the known sequence-based differences and introduces some new ones – for example, the differences in 3' utr length between the two sets of genes are statistically significant and, though a correlation with gene size exists, it is relatively weak .
further research is needed to suggest how all of these differences might relate to, for example, a gene's relative importance or position in a protein-protein interaction map or biological pathway.
the length of the 3' utr is thought to be related to translational efficiency and mrna stability  <cit> , which in turn affects the level of expression of the gene.
two other novel sequence-based features where we found significant differences between disease and non-disease genes – the distance to the nearest neighbouring gene and the number of exons – might also be directly related to expression levels  <cit> .
in this work we were able to confirm the suggestions from previous studies that there is a significant difference in tissue specificity between disease and non-disease genes  <cit>  – perhaps similar differences exist between the two sets in patterns of overall gene expression levels.
it seems remarkable that disease genes would share sequence features to such an extent.
in particular gene length and protein length when taken together as features for an alternating decision tree classifier with fifteen nodes can be reasonably predictive .
a complex web of correlations exists between gene and protein size, levels of expression and rates of evolution, which perhaps explains why predictive power remains relatively high after removing features other than gene and protein size.
additionally, larger genes might simply be bigger targets for mutation  <cit> , or be more likely to have sequence features like overlapping gene groups, multiple amino acid runs  <cit>  and motifs associated with mutational hotspots which might increase the chance of them succumbing to some disease causing mutation.
an alternative hypothesis is that prospectr does not predict genes likely to be involved in disease at all, but the opposite: it derives its predictive power from discounting those genes which are unlikely to be involved in disease as mutations usually result in a phenotype which is either lethal , undetectable  or very weak .
we have shown that prospectr performs well on an oligogenic test set.
however, one might expect the biological mechanisms of cause and effect to differ between simple mendelian and more complex traits and therefore the classifiers dealing with either type may also have to differ.
currently no sizeable dataset of genes involved in complex disease exists; until one is created and examined we cannot tell how prospectr will perform when used to find the genes underlying complex disease.
we would thus advise caution when using prospectr to search for genes involved in complex traits.
future directions
prospectr can create lists of genes the tops of which are enriched for those genes that are likely to be involved in human disease.
substantial enrichment is highly likely with this sequence-based approach, although investigators still need to carry out functional comparisons and fine scale mapping to reduce lists to one or two candidates for each region of interest.
by contrast, functional classifiers might present only a handful of high quality suggestions for each of the regions studied but equally might not return the target gene at all as their threshold for successful detection is too high.
one way of speeding the candidate gene discovery process further without sacrificing accuracy might be to combine existing techniques that use functional annotation with a sequence-based approach similar to the one we describe here.
it may be possible to create a combined classifier greater than the sum of its parts by lowering the threshold of a successful functional annotation based classifier and then dismissing false positives using a sequence-based approach.
the alternating decision tree used in prospectr was trained using all genes from omim and as such is suited for general use.
however, there might well be some value in creating custom classifiers targeted to a particular area of interest; for example, genes involved in neurological disorders.
if the training set was still sufficiently large enough to be representative then one might expect more precision when scoring candidate genes in similar disorders.
as a first step towards this we have made instructions for creating custom classifiers available on the prospectr website.
CONCLUSIONS
on average, prospectr successfully enriches lists of candidate genes 2-fold ~ 77% of the time, 5-fold ~ 37% of the time and 25-fold ~ 11% of the time.
it does so for both monogenic and oligogenic disorders and on the basis of a compact set of rules which look at sequence-based features.
these features reflect the structure and content of the genes in question as well as the phylogenetic extent and are much less likely to be biased towards better studied genes than manual annotation.
the rules involved are easily interpretable which gives some insight into how the classifier works and the importance of various features relative to each other, signposting new avenues of investigation into the differences between the types of disease and non-disease genes.
we predict that the growing availability of relevant protein-protein interaction data and better functional annotation will greatly improve candidate identification techniques for oligogenic and complex disorders, as shared or compensated pathways become clearer.
however, robust genome-wide functional annotation is still some way off.
in the meantime, using prospectr as a quick, unbiased method to rank genes in order of their likelihood of involvement in disease could save investigators much time and effort when examining larger regions of interest, prioritizing candidates for more in-depth functional characterization, mutation detection and case control studies.
our implementation of prospectr is readily available on the web at .

 over the last twenty years the genes underlying more than a thousand classically mendelian disorders have been successfully identified. by contrast, only a relatively small number of genetic components of complex traits have been characterized. regions of interest identified through complex-trait linkage studies regularly exceed centimorgans in size and can contain hundreds of genes. the traditional candidate-gene approach to reducing this number of genes to a manageable level involves attempting to match functional annotation to knowledge of the disease or phenotype under investigation. unfortunately this approach has been characterized by unsubstantiated and unreplicated claims. problems arise firstly because the link between genotype and phenotype in complex disorders tends to be weak; matching a single gene's functional annotation to a phenotype is unlikely to be successful unless the gene in question is clearly related to some known pathogenesis of the disease. secondly, functional annotation of the human genome is incomplete and biased towards better studied genes which have higher levels of annotation. furthermore, assigning functional annotation is a time-consuming process which is unavoidably error-prone and, if taken at face value, misannotated genes can mislead or delay researchers. van driel et al. developed a web-based system for automating the annotation based candidate-gene approach that collates expression and phenotypic data from nine different databases and returns genes that conform to investigator-defined criteria. recently several other candidate-gene identification systems that rely on grouping gene ontology terms have been described, notably pocus, which finds genes across multiple susceptibility loci that share interpro domains and go terms. these systems all rely on functional annotation to make correct predictions, but given that such annotation is incomplete and inherently biased towards a particular subset of genes, a more robust option might be to use sequence-based features instead. it has been suggested that the genes underlying human hereditary disease share certain distinctive, sequence-based features such as larger gene size. by using machine learning algorithms we aimed to discover such common patterns that could be applied to create an automatic classification scheme capable of identifying genes more likely than not to be involved in disease. machine learning has moved rapidly from the field of experimental artificial intelligence to that of applied science. bioinformatics researchers have been quick to adopt machine learning algorithms in a variety of different situations and their use is now widespread. lopez-bigas et al. recently presented a relatively successful decision tree created using such techniques which used amino-acid length and a measure of sequence conservation across species of genes as features to predict genes likely to be involved in hereditary disease. our approach was related but examined a broader set of features and algorithms, producing a significantly more successful classifier that is able to predict genes involved in both mendelian and more complex traits. we have also created a web interface to allow researchers to easily classify individual genes or whole regions of the genome and made it freely accessible at.  defining features and building the training set a set of features was chosen based on a comparative study of ~ known genes from ensembl which are not known to be involved in human disease and the ensembl genes also listed in online mendelian inheritance in man. the feature set reflects the structure, content and phylogenetic extent of each gene examined. we included signal peptide and transmembrane domain predictions; though these are strictly speaking functional attributes they can be calculated with a high degree of accuracy directly from sequence. we also found novel differences between the two sets of genes. there was a small difference in the number of cpg islands at the 5' end of genes listed in omim and those not, with slightly more genes listed in omim having 5' cpg islands, which are associated with both housekeeping genes and to a lesser extent tissue specific genes. there was also a significant difference in the length of the 3' utr between genes listed in omim and those not involved in disease. there was also a significant disparity in the distance to the nearest neighbouring gene – genes listed in omim had a median distance of kb to their neighbours while genes not known to be involved in disease had a median distance of kb. to our knowledge these features have not been previously reported. graphs showing the different distributions of selected features in the two sets are shown in figure though some of the differences we found have previously been described in literature, the discrepancy in 3' utr length has to our knowledge not been examined before and cannot be easily explained in terms of correlation to other, known feature differences. two other novel features are the distance to the nearest neighbouring gene and the number of exons; both of these are quite strongly correlated to gene size. we also studied the number of interpro domains in each set of genes and found significant differences but concluded that a bias existed towards better studied genes. therefore we excluded this feature from our study. automatic classifiers are created by being trained on a set of genes that has already been classified manually. our training set of genes was made up of the genes found in both omim and ensembl and ensembl genes not known to be involved in disease which were selected at random from the larger set of ~ as a representative sample. choosing an algorithm we used weka as the platform for our machine learning experiments. a variety of different machine learning methods were examined but the alternating decision tree algorithm was chosen as the basis of our classification scheme as it couples high accuracy with a relatively small set of rules. the advantage of decision tree based schemes over other popular algorithms such as k-nearest neighbour, support vector machines and bayesian networks is that the rules that are produced for classifying instances can be interpreted more easily by non-expert users. this is particularly true for the alternating decision tree algorithm, which typically produces trees that are just as predictive as those created by more traditional decision tree algorithms but that are far more concise and thus easier to understand. alternating decision trees also allowed us to measure the contribution of each feature to the final classification of a gene, which might provide insight into the essential differences between those genes more and less likely to be involved in disease. alternating decision trees are created by adding rules to the tree in an iterative fashion in the order of their predictive power, with the more effective rules being added first. these rules are automatically derived from the differences between the disease and control genes in the training set provided. a new rule is added to the tree either as a new "node" or as a child of an existing node. with weka, the number of nodes to add to the tree is specified by the user before training begins. too few nodes and the tree will be sparse, without enough cumulative discriminatory power to make confident classifications. too many nodes, on the other hand, will result in an overly-complex tree where later nodes with weak predictive power can distort the effects of earlier, more predictive nodes. on the basis of past experience we chose to limit the size of our alternating decision tree to fifteen nodes, which is a good balance of predictive power and complexity. as each node represents a rule that tests a single sequence feature, this meant that of the two dozen sequence features available a maximum of fifteen would be used in the final tree. an alternating decision tree with fifteen nodes was produced by training on the training set of genes and is shown in figure we also produced trees with ten and twenty nodes for comparison and discovered using the measurements described below that classifier performance was indeed poorer than with the fifteen node version. the alternating decision tree a gene is classified with the tree in figure by beginning at the node marked "start" and then following each branch in turn. upon reaching a node that contains an assumption – for example, that the gene length is larger than a given number – the "yes" or "no" branch is followed as appropriate. if the relevant feature – the paralog percentage identity, for example – is "unknown", neither branch is followed. adding up each of the numbers in rectangles that are encountered along the way results in a final score that reflects the relative confidence of the classification. the classification itself is based on the sign of the score – if negative the gene is generally more likely to be involved in hereditary disease, if positive the gene is generally less likely to be involved in hereditary disease. we tested the classifier on our training set of genes. 77% of the disease genes were correctly identified. in contrast, 42% of the control genes were classified as disease genes. as this is a predictive approach – we cannot say a priori how much of the genome and thus the representative sample in the training set is made up of genes that are involved in disease but are not yet characterized – at least some of these apparently incorrect classifications are likely to be correct. we ran a tenfold cross-validation test to get a conservative estimate of how our classifier might perform on unseen data. tenfold cross-validation is a widely used technique in machine learning and involves partitioning the whole training set into ten independent "folds" each with the same balance of disease genes and control genes. the classifier is trained on nine of the partitions and tested on the remaining partition. this is repeated until each partition has been tested on a new classifier built with the remainder of the training set and simulates the performance of the chosen algorithm and feature set on unseen data. on average, 70% of the disease genes were correctly identified during cross-validation with 43% of control genes classified as false positives. this is comparable to the results obtained by lopez-bigas et al. during cross-validation. table contains more detailed statistics relating to classifier performance. as the alternating decision tree outputs a score that can be thresholded, it is a relatively simple matter to increase specificity at the expense of sensitivity. receiver operating characteristic curves can be used to visualise classifier performance with different combinations of specificity and sensitivity. the x-axis of a roc curve represents the fraction of false positives and the y-axis the fraction of true positives in the classifier results. as the number of true positives increases, so too does the number of false positives. figure shows the roc curves for the classifier on the training set and the two test sets which are described below. we implemented our classifier as a standalone script in perl and designed an associated web interface to aid in the interpretation of the results produced. the resulting software is named prospectr and is freely accessible together with training and test sets of genes at. the web interface allows researchers to quickly obtain scores for regions of the genome or individual genes of interest. further testing evaluating classifier performance on the training set alone is potentially misleading as over-fitting may have occurred. over-fitting happens when a classifier generalises only to the extent necessary to work well on the training data, resulting in poor performance on data that was not seen during the training process. cross-validation provides a measure of the performance of our approach in general, but doesn't reflect actual prospectr performance accurately as the alternating decision trees created for each fold are different. we therefore created two test sets independent of the training set. the first independent test set contained genes associated with disease listed in the human gene mutation database and genes not known to be involved in disease that were picked at random from ensembl. the second contained genes not known to be involved in disease and picked at random from ensembl and genes not listed in omim but associated with different oligogenic disorders including inflammatory bowel disease, parkinsons, retinitis pigmentosa and autosomal recessive limb-girdle muscular dystrophy. we were unable to obtain a sizeable, reliable set of genes involved in complex traits; this meant that classifier performance could not be tested on the components of complex disease. this may change in the future as resources such as the genetic association database develop further and more association data becomes accessible. 71% of the disease genes from the hgmd set and 72% of the genes from the oligogenic set were correctly identified by the classifier, with 42% and 41% of control genes misclassified respectively. these results are similar to those obtained on the training set, suggesting that over-fitting did not occur. they also suggest that our sequence-based approach works equally well for finding genes involved in both oligogenic and monogenic disorders. lopez-bigas et al used a larger set of disease genes during training. only of the genes from the hgmd set were independent of the training sets of both prospectr and the lopez-bigas classifier. as a comparative measure, these genes were scored using both classifiers. prospectr correctly identified 72% of the disease genes while the lopez-bigas classifier identified 47%. prospectr, however, had a higher false positive rate, categorising ~ 44% of the whole human genome as likely to be involved in disease while the lopez-bigas classifier categorised ~ 31% of the whole human genome as likely to be involved in disease. to see how this might have affected recall we calculated the kappa statistic for the results from both classifiers. the kappa statistic is a measurement of agreement between predicted and actual classifications and takes false positive rates into account. it is a number between and. on the independent hgmd set of genes and assuming a false positive rate of 31%, the lopez-bigas classifier had a kappa statistic of while prospectr assuming a false positive rate of 44% had a kappa statistic of, a factor of almost twofold. this suggests that prospectr is substantially more adept than the lopez-bigas classifier at correctly classifying unseen data. by ranking genes by score in descending order, it is possible for prospectr to create a list of genes for any given locus the top of which is enriched for genes that have a higher probability of being involved in disease. to test this we took the hgmd set and for each gene created an artificial locus mb in size consisting of the gene from the hgmd set and all known genes within mb on either side on the same chromosome. the gene taken from the hgmd set was in each case designated the "target gene" and by scoring each gene in the artificial locus and then ranking them we were able to see where the target gene appeared in the ordered list that was created. for the genes from the hgmd set the average number of genes per list was target genes were in the top 5% of the ordered list times, top 10% times, top 50% times and the top 75% times. we repeated the procedure for the genes listed in omim from our training set. the average number of genes per list was and target genes were in the top 5% times out of and the top 50% times. the genes from the training and hgmd sets are mostly mendelian monogenic disorders; to see if the classifier was equally successful at enriching loci involved in more complex diseases we took the list of genes likely to be involved in oligogenic disorders used as a test set by pocus. for these genes involved in oligogenic disorders the average number of genes per list was and the target gene was in the top 5% times and the top 50% times. figure shows a graphical representation of these results. performance on different types of mutation gene records from the hgmd contain information about the number of different mutations associated with any phenotypes linked to that gene, split into three types: nucleotide substitutions, micro-lesions and gross lesions. for example, the huntington gene is recorded as being implicated in huntington disease, which is associated with a gross lesion. the haemoglobin beta gene is recorded as being implicated in sickle cell anaemia, associated with nucleotide substitutions. of the hgmd set we used to test performance, genes were associated with nucleotide substitutions only, with gross lesions only and with micro-lesions only. we tested each subset separately to determine if the underlying cause of disease influenced prospectr's performance. we found that 75% and 77% of the genes involved in disease and associated only with nucleotide substitutions or only with micro-lesions, respectively, were correctly identified by prospectr. however, only 54% of the genes involved in disease and associated only with gross lesions were identified. this suggests that the decision tree used by prospectr is better at identifying genes likely to be involved in disease because of small or point mutations than genes involved in disease because of more drastic events like gross deletions, insertions and chromosomal aberrations. whole genome analysis prospectr was used to score every known gene in the ensembl database on the likelihood that it is involved in human hereditary disease. we normalised the score α given to each gene with the equation where gamma represents euler's constant so that it fell between and with higher scores suggesting a higher likelihood of involvement in disease. genes had a score over, of which are listed in either the hgmd or omim and are thus already known to be involved in disease. by contrast, in the set of genes which scored less than only ~ % are already known to be involved in disease. a list of the genes that scored higher than but are not already known to be involved in disease is included as supplementary material. by searching for references in pubmed we discovered that of these genes are already candidates for involvement in diseases including alzheimers, osteoporosis and schizophrenia. discussion relative performance prospectr has a number of advantages over existing classification schemes designed to differentiate between genes more and less likely to be involved in disease. prospectr appears to perform significantly better on unseen data than the decision tree classifier presented by lopez-bigas et al. the lopez-bigas classifier is less likely to be useful as a predictive tool for two, related reasons: firstly, it achieves perfect accuracy when tested on the training set, even though the training set is known to be inconsistent. the lopez-bigas classifier suggests that ~ 31% of the genome is made up of predicted disease genes. thus if genes were picked at random to make up the control set during training it should be assumed that ~ 31% of them are actually disease genes which have not yet been characterized. perfect accuracy on the training set is therefore undesirable – by ignoring the possibility that the set of control genes might contain disease genes the classifier loses flexibility and predictive power. secondly, the fact that all uncharacterized disease genes were predicted as being control despite their presumed strong similarity to other disease genes suggests that it is highly likely that at least some degree of overfitting occurred, which would further impair performance on novel data. prospectr's use of a spread of sequence-based features representing the structure, content and phylogenetic extent of candidate genes allows investigators to see exactly which features are contributing the most towards a particular classification. in addition, it requires no detailed phenotypic knowledge of the disease in question and can score whole chromosomes in minutes. the use of sequence-based features avoids the bias inherent in current functional annotation, where better studied genes are far more likely to have better and more extensive annotation. furthermore, by relying less on phylogenetic conservation we reduce the amount of potential bias from imperfect homology prediction. classifier mechanics other researchers have examined some of the sequence-based differences between genes listed in omim and genes not known to be involved in disease but there have been no comprehensive studies. the data we present here collates all of the known sequence-based differences and introduces some new ones – for example, the differences in 3' utr length between the two sets of genes are statistically significant and, though a correlation with gene size exists, it is relatively weak. further research is needed to suggest how all of these differences might relate to, for example, a gene's relative importance or position in a protein-protein interaction map or biological pathway. the length of the 3' utr is thought to be related to translational efficiency and mrna stability, which in turn affects the level of expression of the gene. two other novel sequence-based features where we found significant differences between disease and non-disease genes – the distance to the nearest neighbouring gene and the number of exons – might also be directly related to expression levels. in this work we were able to confirm the suggestions from previous studies that there is a significant difference in tissue specificity between disease and non-disease genes – perhaps similar differences exist between the two sets in patterns of overall gene expression levels. it seems remarkable that disease genes would share sequence features to such an extent. in particular gene length and protein length when taken together as features for an alternating decision tree classifier with fifteen nodes can be reasonably predictive. a complex web of correlations exists between gene and protein size, levels of expression and rates of evolution, which perhaps explains why predictive power remains relatively high after removing features other than gene and protein size. additionally, larger genes might simply be bigger targets for mutation, or be more likely to have sequence features like overlapping gene groups, multiple amino acid runs and motifs associated with mutational hotspots which might increase the chance of them succumbing to some disease causing mutation. an alternative hypothesis is that prospectr does not predict genes likely to be involved in disease at all, but the opposite: it derives its predictive power from discounting those genes which are unlikely to be involved in disease as mutations usually result in a phenotype which is either lethal, undetectable or very weak. we have shown that prospectr performs well on an oligogenic test set. however, one might expect the biological mechanisms of cause and effect to differ between simple mendelian and more complex traits and therefore the classifiers dealing with either type may also have to differ. currently no sizeable dataset of genes involved in complex disease exists; until one is created and examined we cannot tell how prospectr will perform when used to find the genes underlying complex disease. we would thus advise caution when using prospectr to search for genes involved in complex traits. future directions prospectr can create lists of genes the tops of which are enriched for those genes that are likely to be involved in human disease. substantial enrichment is highly likely with this sequence-based approach, although investigators still need to carry out functional comparisons and fine scale mapping to reduce lists to one or two candidates for each region of interest. by contrast, functional classifiers might present only a handful of high quality suggestions for each of the regions studied but equally might not return the target gene at all as their threshold for successful detection is too high. one way of speeding the candidate gene discovery process further without sacrificing accuracy might be to combine existing techniques that use functional annotation with a sequence-based approach similar to the one we describe here. it may be possible to create a combined classifier greater than the sum of its parts by lowering the threshold of a successful functional annotation based classifier and then dismissing false positives using a sequence-based approach. the alternating decision tree used in prospectr was trained using all genes from omim and as such is suited for general use. however, there might well be some value in creating custom classifiers targeted to a particular area of interest; for example, genes involved in neurological disorders. if the training set was still sufficiently large enough to be representative then one might expect more precision when scoring candidate genes in similar disorders. as a first step towards this we have made instructions for creating custom classifiers available on the prospectr website.  on average, prospectr successfully enriches lists of candidate genes 2-fold ~ 77% of the time, 5-fold ~ 37% of the time and 25-fold ~ 11% of the time. it does so for both monogenic and oligogenic disorders and on the basis of a compact set of rules which look at sequence-based features. these features reflect the structure and content of the genes in question as well as the phylogenetic extent and are much less likely to be biased towards better studied genes than manual annotation. the rules involved are easily interpretable which gives some insight into how the classifier works and the importance of various features relative to each other, signposting new avenues of investigation into the differences between the types of disease and non-disease genes. we predict that the growing availability of relevant protein-protein interaction data and better functional annotation will greatly improve candidate identification techniques for oligogenic and complex disorders, as shared or compensated pathways become clearer. however, robust genome-wide functional annotation is still some way off. in the meantime, using prospectr as a quick, unbiased method to rank genes in order of their likelihood of involvement in disease could save investigators much time and effort when examining larger regions of interest, prioritizing candidates for more in-depth functional characterization, mutation detection and case control studies. our implementation of prospectr is readily available on the web at. 
prospectr could save investigators looking at large regions of interest time and effort by prioritizing positional candidate genes for mutation detection and case-control association studies. we examined a variety of sequence-based features and found that for many of them there are significant differences between the sets of genes known to be involved in human hereditary disease and those not known to be involved in disease. traditionally this number is reduced by matching functional annotation to knowledge of the disease or phenotype in question. however, here we show that disease genes share patterns of sequence-based features that can provide a good basis for automatic prioritization of candidates by machine learning. it performs markedly better than the single existing sequence-based classifier on novel data. on average, prospectr enriches lists for disease genes two-fold 77% of the time, five-fold 37% of the time and twenty-fold 11% of the time. we have created an automatic classifier called prospectr based on those features using the alternating decision tree algorithm which ranks genes in the order of likelihood of involvement in disease. prospectr is a simple and effective way to identify genes involved in mendelian and oligogenic disorders.
 regions of interest identified through genetic linkage studies regularly exceed centimorgans in size and can contain hundreds of genes. traditionally this number is reduced by matching functional annotation to knowledge of the disease or phenotype in question. however, here we show that disease genes share patterns of sequence-based features that can provide a good basis for automatic prioritization of candidates by machine learning.  we examined a variety of sequence-based features and found that for many of them there are significant differences between the sets of genes known to be involved in human hereditary disease and those not known to be involved in disease. we have created an automatic classifier called prospectr based on those features using the alternating decision tree algorithm which ranks genes in the order of likelihood of involvement in disease. on average, prospectr enriches lists for disease genes two-fold 77% of the time, five-fold 37% of the time and twenty-fold 11% of the time.  prospectr is a simple and effective way to identify genes involved in mendelian and oligogenic disorders. it performs markedly better than the single existing sequence-based classifier on novel data. prospectr could save investigators looking at large regions of interest time and effort by prioritizing positional candidate genes for mutation detection and case-control association studies. 