chronic infection with hepatitis c virus ( hcv ) is a global health problem affecting a significant proportion of world s population .
the world health organization estimated that in 1999 there were 170 million hcv carriers worldwide , with 34 million new cases appearing each year .
a 48-week course of peg - ifn- with rbv is the recommended treatment for patients with hcv involves , but many patients will not be cured by it [ 35 ] .
it also has side effects that prevent some patients from completing therapy . for these reasons , identification of the determinants of responsiveness to the peg - ifn- with rbv treatment is a matter of high priority .
recent genome - wide association studies performed in order to identify human genetic contributions to anti - hcv treatment response have indicated that genetic polymorphisms near the il28b gene are associated with responses to hcv treatment [ 711 ] .
tanaka et al . reported that , within a japanese population of patients with hcv genotype 1 , those with minor alleles ( tg and gg ) of snp rs8099917 were more strongly associated with null virological response ( nvr ) than were those with major alleles ( tt ) ( p  =  2.65    10 ) .
they also reported a logistic regression model based on snp , age , gender , re - treatment , platelet count , aminotransferase level , fibrosis stage , and hcv - rna level indicated that rs8099917 is the most significant factor for nvr .
ge and his colleagues reported not only that a genetic polymorphism near the il28b gene , encoding interferon--3 ( ifn--3 ) , is associated with an approximately twofold change in responsiveness to treatment , both among african - american patients ( p  =  2.06    10 ) and among patients of european ancestry ( p  =  1.06    10 ) but also that a polymorphism on chromosome 19 , rs12979860 , is strongly associated with sustained virologic ( svr ) in all patient groups ( p  =  1.37    10 ) [ 810 ] .
they also noted that their regression model showed that the cc genotype is associated with a more substantial difference in responsiveness rate than was any of the other known baseline predictors included in the model .
reported an association to svr within the gene region encoding interleukin il28b ( rs8099917 combined p  =  9.25    10 , or  =  1.98 , 95% ci  =  1.572.52 ) and indicated that host genetics may be useful for predicting drug responsiveness .
the recent reports made clear that genetic polymorphisms near the il28b gene are associated with the responses of patients with hcv genotype 1 to the recommended drug treatment and indicated that predicting responsiveness to the treatment is an urgent necessity .
although the virological responses of patients with hcv genotype 1 to peg - ifn- with rbv have been reported to be strongly associated with genetic polymorphisms , there is no report of responsiveness being predicted from the polymorphisms .
it is quite important to know whether or not a new patient with hcv genotype 1 will be cured by peg - ifn- with rbv before beginning the treatment .
predicting patient s responsiveness from the related snps would help to reduce side effects and treatment costs .
the method we propose for predicting responsiveness uses decision tree learning based on the genome - wide snps .
decision tree learning is a method that uses inductive inference to approximate a target function that will produce discrete values .
it is generally best suited to problems in which instances are represented by attribute - value pairs and the target function has discrete output values .
a decision tree classifies each example into a class corresponding to one of the output values .
individual snps and their alleles ( major , hetero , and minor genotypes ) in the genome - wide association study ( gwas ) were used as attributes .
142 japanese hcv genotype 1 patients ( 64 with virologic responses ( vrs ) and 78 with null virologic responses ( nvrs ) ) were used as training instances . to carry out the supervised learning for their classification , we partitioned the training instances into two data sets : training data for growing the decision tree , and testing data for pruning the decision tree .
the classification processes were carried out in two phases : one for growing it and the other for pruning it .
the sliq / sprint algorithm uses a two - branch ( yes / no ) approach , so for two combinations we selected the three types of branches listed in table 1 .
the previous analyses of genome - wide drug responses for hcv genotype 1 patients indicated that specific snps are closely associated with vrs / nvrs [ 711 ] . to analyze snp contributions to the drug effects ,
one first needs to calculate an evaluation function ( such as the gini diversity index ( gdi ) ) for three types of branches of individual snps and determine the maximum value of that function .
each snp has three gdis for individual alleles , and each gdi can be computed in the following way : ( 1)gdi=1l=1kp(cl)2m=1jam1l=1kp(cml)2am = nmn  ( m=1,2, ... ,j ) ,  m=1jam=1where k is the number of classes ( in this case k  =  2 , vr and nvr ) , p(cl ) is the probability of l class for each snp in the instances , j is a number of branches ( j  =  2 in the sliq / sprint algorithm ) , p(cml ) is the probability of l class in the branch m , nm is a number of the instances for the branch m , and n is the total number of the snp instances ( in the first case all instances are used , that is , n  =  142 ) .
a node is introduced for partitioning the instances in the decision tree , and in this article an snp in the instances is used as a node .
the processes for growing the decision tree are , in outline , as follows:(1)the decision tree starts as a single node representing the hcv patient instances.(2)if the instances are all of the same class , the node becomes a leaf and is labeled with that class.(3)otherwise , the attribute that will best separate the instances into individual classes is selected by calculating the gdi for each attribute .
the node is labeled with this attribute.(4)two branches are created for the node attribute , and the instances are partitioned accordingly.(5)the same processes are carried out recursively to form a decision tree for the instances at each partition.(6)the recursive partitioning stops only when one of the following conditions is met:all instances for a given node belong to the same class , orthere are no remaining attributes on which the instances may be further partitioned .
if the instances are all of the same class , the node becomes a leaf and is labeled with that class .
otherwise , the attribute that will best separate the instances into individual classes is selected by calculating the gdi for each attribute .
two branches are created for the node attribute , and the instances are partitioned accordingly .
the same processes are carried out recursively to form a decision tree for the instances at each partition .
the recursive partitioning stops only when one of the following conditions is met:all instances for a given node belong to the same class , orthere are no remaining attributes on which the instances may be further partitioned .
all instances for a given node belong to the same class , or there are no remaining attributes on which the instances may be further partitioned . working backward from the bottom of the tree , the subtree starting at each non - terminal
if removing a subtree improves the error ( misclassification ) rate on the testing data , the subtree is removed .
this process continues until no further improvement is made . after completing the growth and pruning of the decision tree ,
that is , the individual leaves are labeled with the most common classes ( vr and nvr ) in the instances .
in addition , vr and nvr classes are assembled as the total vrs and nvrs for predicting vr and nvr ratios .
the vr ratio predicted from the decision tree learning based on the snp information is given by(2)pvr = dvrivrwhere dvr is the total number of vrs in the predicted vr class and ivr is the number of vr instances .
the nvr ratio predicted from the decision tree learning is given by(3)pnvr = dnvrinvrwhere dnvr is the total number of nvrs in the predicted nvr class and invr is the number of nvr instances .
the total number of vrs and nvrs predicted from the decision tree learning is based on eqs .
( 3 ) and ( 4 ) and is given by(4)pvr+nvr = dvr+dnvraiwhere ai is the total number of instances ( all the hcv patients ) .
individual snps and their alleles ( major , hetero , and minor genotypes ) in the genome - wide association study ( gwas ) were used as attributes . 142 japanese hcv genotype 1 patients ( 64 with virologic responses ( vrs ) and 78 with null virologic responses ( nvrs ) )
were used as training instances . to carry out the supervised learning for their classification , we partitioned the training instances into two data sets : training data for growing the decision tree , and testing data for pruning the decision tree .
the classification processes were carried out in two phases : one for growing it and the other for pruning it .
the sliq / sprint algorithm uses a two - branch ( yes / no ) approach , so for two combinations we selected the three types of branches listed in table 1 .
the previous analyses of genome - wide drug responses for hcv genotype 1 patients indicated that specific snps are closely associated with vrs / nvrs [ 711 ] . to analyze snp contributions to the drug effects ,
one first needs to calculate an evaluation function ( such as the gini diversity index ( gdi ) ) for three types of branches of individual snps and determine the maximum value of that function .
each snp has three gdis for individual alleles , and each gdi can be computed in the following way : ( 1)gdi=1l=1kp(cl)2m=1jam1l=1kp(cml)2am = nmn  ( m=1,2, ... ,j ) ,  m=1jam=1where k is the number of classes ( in this case k  =  2 , vr and nvr ) , p(cl ) is the probability of l class for each snp in the instances , j is a number of branches ( j  =  2 in the sliq / sprint algorithm ) , p(cml ) is the probability of l class in the branch m , nm is a number of the instances for the branch m , and n is the total number of the snp instances ( in the first case all instances are used , that is , n  =  142 ) .
a node is introduced for partitioning the instances in the decision tree , and in this article an snp in the instances is used as a node .
the processes for growing the decision tree are , in outline , as follows:(1)the decision tree starts as a single node representing the hcv patient instances.(2)if the instances are all of the same class , the node becomes a leaf and is labeled with that class.(3)otherwise , the attribute that will best separate the instances into individual classes is selected by calculating the gdi for each attribute .
the node is labeled with this attribute.(4)two branches are created for the node attribute , and the instances are partitioned accordingly.(5)the same processes are carried out recursively to form a decision tree for the instances at each partition.(6)the recursive partitioning stops only when one of the following conditions is met:all instances for a given node belong to the same class , orthere are no remaining attributes on which the instances may be further partitioned .
if the instances are all of the same class , the node becomes a leaf and is labeled with that class .
otherwise , the attribute that will best separate the instances into individual classes is selected by calculating the gdi for each attribute .
two branches are created for the node attribute , and the instances are partitioned accordingly .
the same processes are carried out recursively to form a decision tree for the instances at each partition . the recursive partitioning stops only when one of the following conditions is met:all instances for a given node belong to the same class , orthere are no remaining attributes on which the instances may be further partitioned .
all instances for a given node belong to the same class , or there are no remaining attributes on which the instances may be further partitioned .
working backward from the bottom of the tree , the subtree starting at each non - terminal node is examined .
if removing a subtree improves the error ( misclassification ) rate on the testing data , the subtree is removed .
after completing the growth and pruning of the decision tree , majority voting is carried out for individual leaves .
that is , the individual leaves are labeled with the most common classes ( vr and nvr ) in the instances .
in addition , vr and nvr classes are assembled as the total vrs and nvrs for predicting vr and nvr ratios .
the vr ratio predicted from the decision tree learning based on the snp information is given by(2)pvr = dvrivrwhere dvr is the total number of vrs in the predicted vr class and ivr is the number of vr instances .
the nvr ratio predicted from the decision tree learning is given by(3)pnvr = dnvrinvrwhere dnvr is the total number of nvrs in the predicted nvr class and invr is the number of nvr instances .
the total number of vrs and nvrs predicted from the decision tree learning is based on eqs .
( 3 ) and ( 4 ) and is given by(4)pvr+nvr = dvr+dnvraiwhere ai is the total number of instances ( all the hcv patients ) .
one hundred and forty - two japanese patients with hcv ( 78 nvr and 64 vr ) receiving peg - ifn-/rbv treatment were analyzed by using the snps evaluated in a previous gwas study . although a total of 621,220 snps were used for the genome - wide association analysis , approximately 500 of those with the lowest p - values calculated by using a  test for allele frequencies were selected for the decision tree learning .
the node with the largest gdi was selected as the root node of the decision tree . in the first case ,
that is , 142 japanese hcv patients were divided into two branches based on rs8099917 .
1 , where one sees that the  yes  and  no  branches from the root node b1 were , respectively , het  +  mm and mm .
the numbers of instances in the two branches divided by rs8099917 were , respectively , 65 in the  yes  branch and 77 in the  no  branch .
as the most instances in the  yes  branch node were nvrs ( 59 of 65 , or 90.8% ) , this node was labeled as the leaf node . from the descendent node on the  no  branch
, a new descendant of the node was obtained using the processes described in section 2.2 .
after the decision tree was grown , it was pruned as described in section 2.3 .
the decision tree learning was carried out for the 142 japanese hcv patients with the 500 lowest - p snps , and the predicted vr and nvr ratios were calculated using eqs .
( 2 ) and ( 3):pvr=48 + 764=5564=0.859pnvr=59 + 1478=7378=0.936the predicted total number of vrs and nvrs was also calculated using eq .
( 4):pvr+nvr=55 + 73142=0.901before the decision tree learning by the snp information , we knew only that 64 of the japanese hcv patients were vr for the drug response and 78 were nvr .
therefore , all we can calculate is that the vr and nvr response rates for those patients are respectively 0.451 ( 64/142 ) and 0.549 ( 78/142 ) . after the decision tree learning , however
, we can predict that the vr and nvr drug responses are respectively 0.859 and 0.936 and can predict that the drug response rate for the total 142 samples is 0.901 ( ( 55  +  73)/142 ) .
this means that if a new hcv genotype 1 patient wants to know whether or not he / she is vr / nvr for the drug treatment , he / she can predict his / her vr / nvr ratio by checking his / her snp information in the decision tree shown in fig .
, suppose a new male hcv patient having rs8099917 , rs4906195 , and rs3816768 alleles that are , respectively , 
, it is predicted that he will be vr for the recommended hcv drug treatment . on the other hand ,
, it is predicted that she will mostly likely be nvr for the recommended hcv drug treatment .
it is important to increase the prediction ratio in the decision tree learning . the higher the prediction ratio , the better the drug treatment response for a new hcv patient is predicted . in the decision tree model
we therefore also generated decision tree models by using root nodes based on the snps having the 30 highest gdis .
as a result , we got two decision trees that can predict ratios higher than that of the first decision tree . they are shown in figs . 2 and 3 .
the results of prediction ratios ( probabilities predicted ) for these decision tree models and the individual snp attributes used in the models are listed in table 2 .
this is 2.8 percentage points higher than that of model 1 . as the root node plays an important role , we examined what chromosome the root node belongs to in each model .
the chromosomes with individual root nodes in the models 1 , 2 , and 3 were , respectively , 19 , 1 , and 8 ( table 2 ) .
although snps near the il28b gene on chromosome 19 were recently reported to be the most significant factors , the root nodes in models 2 and 3 are on other chromosomes .
other snps used in the models 2 and 3 are also on other chromosomes ( table 2 ) .
these results therefore imply that there may be significant snps other than those near the il28b gene on chromosome 19 .
although that the virological responses of hcv patients treated with peg - ifn- and rbv have been reported to be strongly associated with genetic polymorphisms , there is no report of what responses can be predicted from the polymorphisms . if the responsiveness of hcv patients to a drug treatment could be predicted from information about related snps , side effects and treatment cost could be greatly reduced .
furthermore , because the results of the proposed method implied that snps other than those in the il28b region are strongly related to the prediction of the drug response , the relations between those snps and the drug response should be examined experimentally .
 highlights we modeled drug responses using decision tree learning based on snps in a genome - wide association study . 
  we can predict the drug responses of a new patient with hcv genotype 1 . 
  responsiveness to pegylated interferon  ( peg - ifn- ) plus rebavirin ( rbv ) treatment was predicted . 
  we can predict with 93% probability whether a new patient with hcv genotype 1 will be helped by drug treatment . 
Introduction
Materials and methods
Model for decision tree learning
Growth of the decision tree
Pruning of the decision tree
Prediction by decision tree learning
Results and discussion