a major goal for epidemiologists is the identification of genetic and environmental factors that predict common complex diseases ( eg , cancer ) .
traditional mendelian ( single - gene ) approaches , such as those typically adopted in genome - wide association studies , have yielded limited success when applied to most common diseases , at best identifying common variants that contribute only modestly to a given phenotype.1 
 2 perceived problems , common to these analyses , such as the lack of reproducibility,3 
 4 the observation of  missing heritability,2 
 5 
 6 and the sheer number of candidate factors identified as potentially related to disease , are all suggestive of a complex pattern of association .
complexity references the number of factors involved , the influence of interaction ( eg , additive or epistatic ) , and the inconsistency of heterogeneity . from an evolutionary perspective
, these types of complex disease associations would be expected as the logical byproduct of canalization and the accumulation of cryptic genetic variation.7 the term epistasis was coined to describe a genetic  masking effect viewed as a multi - locus extension of the dominance phenomenon , where a variant at one locus prevents the variant at another locus from manifesting its effect.8 this type of interaction might plausibly occur between sets of genetic or environmental factors . to date , the detection and modeling of epistasis and general interaction effects , has received a great deal of attention . random forests,9 multifactor dimensionality reduction ( mdr),10 detection of informative combined effects ( dice),11
combinatorial partitioning method,12 logistic regression,13 patterning and recursive partitioning,14 and bayesian pathway modeling15 represent just a handful of the available strategies . by comparison ,
the meaning of the term heterogeneity depends on the context . in the context of admixture ,
heterogeneity simply refers to genetic differences in population structure.16 in genetic modeling , a heterogeneous model describes the independent effect of a number of factors.17 similarly , in association studies , heterogeneity refers to an independence effect seen in three different phenomena : allelic heterogeneity , locus heterogeneity , and phenocopy.18 allelic heterogeneity occurs when two or more alleles of a single locus are independently associated with the same trait , while locus heterogeneity occurs when two or more dna sequence variations at distinct loci are independently associated with the same trait .
heterogeneity , typically classified as either genetic ( locus and allelic ) or environmental ( ie , phenocopy ) , occurs when an individual , or set , of factors is independently predictive of the same phenotype .
additionally , trait heterogeneity occurs when a trait or disease has been defined with insufficient specificity such that it is actually two or more distinct underlying traits.18 in the context of mining genetic and environmental patterns within an association study , there is no practical distinction between genetic heterogeneity , trait heterogeneity , and phenocopy , since these phenomena manifest the same type of independent associations . from a computer science prospective ,
hidden class problem . while the disease status ( case or control ) of each patient is already known , the individuals making up either class would be more accurately subgrouped into two or more  hidden classes , each characterized by an independent predictive model of disease . as mentioned , there are far fewer successful strategies for dealing with the heterogeneity problem .
an exception to this is seen in an evaluation of mdr that demonstrated that simulated heterogeneity dramatically hinders mdr 's power to detect all underlying modeled factors.19 statistical approaches such as the admixture test,20 m test,21 and  test22 are specific to family - based data and can only identify the existence of heterogeneity rather than characterize it . the most common approach to heterogeneity is to try to remove its confounding effect by data stratification .
this has been done using strategies such as ordered subset analysis,23 latent class analysis,24 
 25 tree - based recursive partitioning,26 and clustering.27 
 28 these methods preprocess the dataset based on genetic risk factors , demographic data , phenotypic data , or endophenotypes in order to form more homogeneous subsets of subjects .
this is in line with the standard epidemiological paradigm that seeks to find a single best disease model within a given homogeneous sample .
the obvious drawback of these methods is that their success completely relies on the availability , quality , and relevance of these covariates . additionally , stratification represents a relative reduction in sample size , leading to an inevitable loss in power to detect associations within these homogeneous subsets .
only a few strategies have been considered that concurrently examine the problems of epistasis and heterogeneity without resorting to some form of stratification .
these include mdr,19 
 29 random forests,30 association rule discovery,31 and clique - finding for heterogeneity and multidimensionality in biomedical and epidemiological research ( chamber).32 while some algorithms have been successful in accommodating the problem of heterogeneity , explicit characterization has remained a major challenge .
chamber , an algorithm that uses graph building was the first to consider the joint characterization of interaction and heterogeneity .
specifically , heterogeneity was characterized through the identification of groups of individuals , within which , different predictive attributes were correlated with disease risk .
in the context of data mining and machine learning , the word attribute refers to a variable such as a single nucleotide polymorphism ( snp ) or a demographic variable such as gender that is used to make a prediction .
while chamber represents a unique step in the direction of data - driven approaches to heterogeneity and epistasis , its exhaustive search strategy limits its application to much smaller datasets .
also , the chamber algorithm has yet to be externally applied , and is not accessible for download . given the apparent complexity of common disease , and the likelihood that multi - locus interactions and heterogeneity are present and likely to be ubiquitous components of disease risk,33 
 34 it is critical to develop powerful new strategies that concurrently deal with these phenomena .
strategies that make assumptions about the nature , number , or source of underlying factors will inevitably be susceptible to complicating phenomena . learning classifier systems ( lcss)35 are a rule - based class of algorithms that combine machine learning with evolutionary computing and other heuristics to produce an adaptive system .
they represent solutions as sets of rules , affording them the ability to learn iteratively , form niches , and adapt .
this class of algorithm breaks from the traditional single model paradigm by evolving a solution comprising multiple rules , consequently avoiding the need for data stratification .
these characteristics make the application of lcss to the problem of heterogeneity , in particular , intrinsically appealing .
previously , we explored the application of different lcs algorithms to the detection and modeling of simulated epistatic and heterogeneous genetic disease associations and demonstrated their ability to successfully detect predictive factors in the presence of heterogeneity , and an extreme , precisely defined form of epistasis referred to as pure epistasis.36 
 37 a purely epistatic interaction occurs between n loci that do not display any main effects.38 
 39 these proof - of - principle analyses identified michigan - style lcss ( m - lcss ) as the most promising implementation for our particularly complex , noisy problem domain .
however , knowledge discovery in m - lcss remained problematic . in another study40 we developed an analysis pipeline with visualization - guided knowledge discovery to overcome this obstacle .
in addition to significance testing , the pipeline presented subjective visualization strategies for inferring patterns of attribute interaction and heterogeneity from the rule - set .
still lacking , was a strategy for explicitly identifying heterogeneity and linking instances in the dataset to respective heterogeneous subgroups .
with af - ucs ( attribute feedback - supervised classifier system)41 we introduced attribute tracking and feedback as mechanisms to deal with this problem , and improve learning and generalization in the m - lcs algorithm . while the aforementioned efforts to apply lcss to the characterization of both epistatic and heterogeneous patterns of association were evaluated over a diverse spectrum of simulated datasets , we have yet to apply them to a real - world investigation of common complex disease .
in this study we applied our extended m - lcs approach to the investigation of bladder cancer susceptibility . like other common complex diseases ,
cancer is recognized as a multifactorial disease that results from complex interactions between many genetic and environmental factors . in an effort to validate the utility of our m - lcs approach we investigated the relationship between dna repair gene snps , smoking , and bladder cancer susceptibility in 355 cases and 559 controls enrolled in a population - based study of bladder cancer .
this dataset was previously analyzed by andrew et al42 using a multifaceted statistical approach that included the application of logistic regression , mdr , and information theory .
these previous findings identified xpd codon 751 and 312 snps together with smoking as the best predictors of bladder cancer . in this study , we applied af - ucs,41 to the same dataset in an attempt to replicate these previous findings and characterize any patterns of interaction or heterogeneity that might be associated with bladder cancer risk .
we have demonstrated how the clustering of attribute tracking scores within instances of the dataset may be used to identify sample subsets , after training .
additionally , we have attempted to validate these subgroups with statistical comparisons examining clinical outcome variables .
specifically , we examined age of diagnosis , survivorship , age of recurrence , and tumor stage / grade between reliable patient clusters .
in this section we describe ( 1 ) the bladder cancer data examined in this study , ( 2 ) the af - ucs algorithm and associated run parameters , and ( 3 ) the analytical pipeline and statistical analysis used in this study . the bladder cancer dataset considered in this study was previously collected and examined by andrew et al.42 after removal of subjects with missing snp values , the dataset included 355 cases and 559 controls each with seven snps , age , gender , and cigarette smoking history .
dna repair gene snps were examined that had been previously related to bladder cancer ( xrcc1 , xrcc3 , xpd , xpc ) and other pathway members that physically interact with these genes ( ape1 ) .
a full description of this dataset is given by andrews et al.42 along with the variables considered in that publication,42 additional clinical outcome variables were recorded for the cases in this study group that are used in this study .
these included ( 1 ) tumor stage and grade , ( 2 ) age at diagnosis ( years ) , ( 3 ) survival time in years ( ie , survivorship ) , and ( 4 ) time to first recurrence in years .
censoring occurs when we do not know the time of death or recurrence for all subjects .
tumor stage and grade was included as a categorical variable with the following categories : ( 1 ) non - invasive low grade , ( 2 ) non - invasive missing grade , ( 3 ) non - invasive high grade , ( 4 ) in situ tumor , ( 5 ) stage ii , ( 6 ) stage iii , and ( 7 ) stage iv . non - invasive , low - grade tumors are the least aggressive and have the best prognosis .
stage ii and higher - stage tumors are tumors that are  invading through the bladder wall , which can then metastasize to other organs . in this study ,
analysis of the described dataset was completed without access to unique patient identifiers in accordance with institutional review board human subject protection .
any identifiers added to track patients during learning , clustering , and comparison of clinical variables , were arbitrarily assigned for the purposes of this study .
overall , no significant associations were identified between any single dna repair gene snp and bladder cancer risk .
a marginally significantly increased risk was seen in the xpd codon 751 homozygote variant among subjects who never smoked .
the xrcc1 191 variant allele was associated with reduced bladder cancer risk among heavy smokers .
mdr analysis identified pack - years smoking as the strongest single factor for predicting bladder cancer risk ( average testing accuracy=0.63 ) .
the best two - factor model included xpd 751 and xpd 312 ( average testing accuracy=0.65 ) .
the best three - factor model ( also the best overall model ) added pack - years smoking to xpd 751 and xpd 312 ( average testing accuracy=0.66 ) .
the application of information theory suggested that the relationship between the two xpd snps and bladder cancer is mostly non - additive ( ie , epistatic ) , while the effect of smoking is mostly additive .
further analysis indicated that the combination of these snps into a haplotype indicated that a variant xpd haplotype was more susceptible to bladder cancer , an effect that was magnified with the inclusion of smoking .
xpd stands for xeroderma pigmentosum group d , the gene encoding an enzyme in the nucleotide excision repair pathway .
this enzyme is known to remove certain dna crosslinks , ultraviolet photolesions , and bulky chemical adducts.43 interactions between xpd 312 and xpd 751 have also been seen in relation to lung cancer risk , and several studies found that the risk of lung cancer associated with the variant allele was higher among non - smokers than among smokers.44 
 45 the most unique feature of m - lcs is that it evolves a population of rules which collectively constitute the learned prediction model .
learning proceeds iteratively , with the rule population training on one instance from the dataset at a time .
rule discovery is largely achieved with a genetic algorithm operating at the level of individual rules within the population .
for a complete lcs introduction and review , see urbanowicz and moore.35 ucs46 is an m - lcs based largely on the popular xcs ( extended classifier system ) algorithm47 but replaces reinforcement learning with supervised learning .
ucs was designed specifically to deal with single - step problems such as classification and data mining , where delayed reward is irrelevant , and showed particular promise when applied to epistasis and heterogeneity as we showed in a previous study.36 previously , we developed the af - ucs algorithm,41 an expansion of ucs which incorporated attribute tracking and feedback into the basic supervised learning algorithm .
each rule includes a condition and class ( ie , if certain instance attributes have a specific state , then the rule predicts the specified class ) .
rules are built using a quaternary representation , where each attribute of the condition will either specify an snp genotype encoding ( ie , 0 , 1 , 2 ) or that attribute will be generalized ( ie ,  #  , wild / don't care ) . the right - hand yellow box in figure 1 gives an example ( c ) including three hypothetical rules represented in this manner .
notice that their conditions all match the example training instance , and they all specify the correct class of the instance .
outline of the af - ucs ( attribute feedback - supervised classifier system ) algorithm .
( 1 ) learning occurs iteratively , focusing on a single training instance from the dataset at a time . ( 2 ) training instance passed to the population of rules ( p ) .
( 3 ) match set ( m ) is formed , including any rule in ( p ) that that has a condition matching the attribute states of the instance .
( 4 ) correct set ( c ) is formed , including any rule in ( m ) which specifies the correct class of the instance . ( 5 ) if no rules are found for ( c ) , randomly generate such a rule using the covering mechanism .
( 6 ) update rule parameters in ( m ) and ( c ) ( eg , rule fitness ) .
( 7 ) use rules in ( c ) to update attribute tracking scores for current instance .
( 8) the genetic algorithm ( ga ) selects parent rules from ( c ) based on fitness and generates offspring rules which are added to ( p )
. if attribute feedback is being used , the attribute tracking scores for the current instance are applied as weights to guide the ga .
( 9 ) deletion mechanism removes rules from ( p ) based on fitness whenever the size of ( p ) is greater than the user - specified maximum population size . while the majority of af - ucs is equivalent to ucs , the dark blue box in figure 1 highlights the mechanism unique to our algorithm .
attribute tracking is a collective form of memory designed to be applied to single - step supervised learning problems .
essentially this mechanism learns which attributes are most important to the accurate classification of each individual instance , storing and accumulating this knowledge independently of the rule population .
attribute feedback is a heuristic that draws upon the knowledge learned in attribute tracking to promote efficient generalization and improve learning in the presence of noisy , complex , and heterogeneous data .
attribute feedback probabilistically directs generalization pressures in the ga based on relative attribute tracking scores .
previously , af - ucs was evaluated using only simulated datasets . in order to accommodate the nature of real - world datasets
, one minor modification was made to the algorithm . to address the calculation of training and testing accuracy when the algorithm is applied to unbalanced datasets we replaced the traditional accuracy calculation with balanced accuracy
as described by velez et al.48 we had previously implemented attribute tracking and feedback into af - ucs , a python encoding of the ucs algorithm.36 
 41 we adopted mostly default m - lcs run parameters .
parameters unique to this study include 200  000 learning iterations , a rule population size of 1000 , tournament selection , uniform crossover , subsumption , attribute mutation probability=0.04 , crossover probability=0.8 , and a  of 1 .
 has been described as a  constant set by the user that determines the strength ( of ) pressure toward accurate classifiers49 and is typically set to 10 by default .
a low  was used to place less emphasis on high accuracy in this type of noisy problem domain , where 100% accuracy is only indicative of over - fitting . also , as in our previous study,36 we employed a quaternary rule representation , where for each snp attribute , a rule can specify genotype or covariates as ( 0 , 1 , or 2 ) , or instead generalize with  #  , a character that implies that the rule does not care about the state of that particular attribute .
generally speaking , the use of larger population sizes and a greater number of learning iterations can improve the resulting performance of the evolved m - lcs rule population .
it is likely that optimization of these and other run parameters would further improve the performance of the af - ucs algorithm .
we adopted the analysis pipeline40 for the identification of significant predictive attributes identified by the af - ucs algorithm .
our analysis includes the following steps : ( 1 ) run the af - ucs algorithm on the dataset using 10-fold cross - validation ( cv ) , ( 2 ) run a permutation test with 1000 permutations , ( 3 ) confirm significance of testing accuracy , ( 4 ) identify significant attributes and significantly co - occurring pairs of attributes , ( 5 ) train the af - ucs algorithm on the whole dataset ( no cv ) , ( 6 ) generate visualization for pattern characterization , ( 7 ) repeat steps 13 as a second pass on the dataset that only includes attributes identified as significant from the first pass , ( 8) identify significant , stable clusters of subjects using attribute tracking scores , and ( 9 ) compare clinical variables between identified subject clusters .
although we do not claim that this analysis pipeline is necessarily optimal , we have attempted to assemble a logical series of analytical steps that rely primarily on statistically significant empirical observations . indeed it is likely that there are other reasonable ways to approach knowledge discovery and hypothesis generation in this context .
our first - pass analysis of the bladder cancer data ( summarized by steps 16 ) began by running af - ucs on the dataset using 10-fold cv strategy in order to determine average testing accuracy and account for over - fitting .
the dataset was randomly partitioned into 10 equal parts and af - ucs was run 10 separate times during which 9/10 of the data was used to train the algorithm , and the other 1/10 was set aside for testing .
we generated 1000 permuted versions of the original dataset by randomly permuting the affection status ( class ) of all samples , while preserving the number of cases and controls .
for each permuted dataset we ran ucs using 10-fold cv . in total , permutation testing required 10  000 runs of af - ucs .
next , we confirmed that the average testing accuracy was significantly higher than expected by random chance .
if average testing accuracy had not been significantly high , this would have suggested that af - ucs was unable to learn any useful generalizations from the data , excluding a need for further analysis .
we used a typical one - tailed permutation test with a significance threshold of p<0.05 .
once a significant testing accuracy was confirmed , we used the permutation test to identify attributes in the dataset that showed significant importance in making accurate classifications .
as detailed elsewhere,40 we used the following statistics for making such an inference from the rule population : ( 1 ) specificity sum ( sps ) and ( 2 ) accuracy - weighted specificity sum ( awsps ) . additionally , we used the permutation test to evaluate attribute interactions and to help to discriminate between interaction and heterogeneity .
this was achieved by evaluating a co - occurrence statistic ( cos ) that examined all pairwise attribute co - occurrence within rules of the population.40 we calculated cos for every non - redundant pairwise combination of attributes in the dataset . in this 10-attribute dataset we calculated 45 coss .
these coss were also used to generate the co - occurrence network given in the results . to generate the co - occurrence network we used gephi ( http://gephi.org/)open-source graph visualization software . with the 45 coss calculated above
using gephi , we generated a fully connected , undirected network , where nodes represent individual attributes , the diameter of a node is the sps for that attribute , edges represent co - occurrence , and the thickness of an edge is the respective cos .
gephi offers a built - in function to filter edges from the network based on edge weight .
this was for rule population visualization purposes ( ie , the generation of a rule population heat - map ) . in another study40
we detailed the re - encoding of the rule - population in preparation for visualization .
we employed agglomerative hierarchical clustering using hamming distance as the distance metric http://gephi.org/. clustering was performed on both axes ( ie , across rules and attributes ) .
both clustering and 2d heat - map visualization were performed in r using the hclust and gplots packages , respectively .
we extended this analysis to a second pass over the data that focused exclusively on those attributes identified as significant in the first pass .
we repeated steps 13 including cv , permutation testing , and statistical evaluation of average testing accuracy . also , we ran af - ucs without cv on a subset of the dataset that included only these significant attributes in order to obtain a matrix of attribute tracking scores for further investigation .
attribute tracking keeps a record of which attributes are most important for accurate classification for each subject in the dataset .
therefore , by clustering subjects in the dataset by these attribute tracking scores we aimed to identify homogeneous groups of subjects defined by similar patterns of attributes determined to be important for accurate classification . as we discussed elsewhere,41 before clustering we normalized
normalization was achieved by dividing each tracking score by the sum of all tracking scores for that instance .
our strategy for the selection of significant stable subject clusters involved hierarchical clustering with an assessment of uncertainty .
we applied pvclust , an r package that calculated p values for hierarchical clustering via multiscale bootstrap resampling.50 significant clusters were identified using approximately unbiased ( au ) p values , where au values > 95% were deemed significant .
once calculation of p values was complete we assigned alphabetical group ids to unique , significant clusters .
finally , we compared the clinical variables between cases found in respective significant subject clusters .
the clinical variable data was only applicable to the bladder cancer cases in our study group .
all the following statistical evaluations were also performed in r. next , we discuss our evaluation of the continuous clinical variables ( ie , age at diagnosis , survivorship , and time to recurrence ) . the non - parametric kruskal 
wallis one - way analysis of variance was used to determine whether these clinical variables differ by cluster .
pairwise comparisons between subject clusters were performed using the non - parametric mann  whitney test .
in addition , we performed  time - to - failure analyses ( ie , survival analysis ) for age at diagnosis , survivorship , and time to recurrence including failure curves ( ie , kaplan  meier curves ) for each . since both survivorship and time to recurrence data include censored values , we adopted a cox proportional hazard regression model ( coxph ) , most widely used in medical studies .
since age at diagnosis could logically affect survivorship or time to recurrence we included it as a covariate in the covariance analysis model .
we began with a cox proportional hazard model including the interaction between cluster i d and age at diagnosis .
next we used the step function to choose the best factors to keep in the model by akaike 's information criterion ( aic ) .
aic takes into account the balance between goodness of fit , and the number of parameters included in a model .
follow - up analysis of variance between the best model identified by aic , and a similar model excluding group specification , indicates whether there is a significant difference in our clinical outcome variable based on group designation .
tumor stage and grade was a categorical variable , we adopted a  test of homogeneity in order to look for differences between the cases of different clusters . noting that certain cells of the table had very few counts
the bladder cancer dataset considered in this study was previously collected and examined by andrew et al.42 after removal of subjects with missing snp values , the dataset included 355 cases and 559 controls each with seven snps , age , gender , and cigarette smoking history .
dna repair gene snps were examined that had been previously related to bladder cancer ( xrcc1 , xrcc3 , xpd , xpc ) and other pathway members that physically interact with these genes ( ape1 ) .
a full description of this dataset is given by andrews et al.42 along with the variables considered in that publication,42 additional clinical outcome variables were recorded for the cases in this study group that are used in this study .
these included ( 1 ) tumor stage and grade , ( 2 ) age at diagnosis ( years ) , ( 3 ) survival time in years ( ie , survivorship ) , and ( 4 ) time to first recurrence in years .
censoring occurs when we do not know the time of death or recurrence for all subjects . censoring indicators
tumor stage and grade was included as a categorical variable with the following categories : ( 1 ) non - invasive low grade , ( 2 ) non - invasive missing grade , ( 3 ) non - invasive high grade , ( 4 ) in situ tumor , ( 5 ) stage ii , ( 6 ) stage iii , and ( 7 ) stage iv . non - invasive , low - grade tumors are the least aggressive and have the best prognosis .
stage ii and higher - stage tumors are tumors that are  invading through the bladder wall , which can then metastasize to other organs . in this study ,
analysis of the described dataset was completed without access to unique patient identifiers in accordance with institutional review board human subject protection .
any identifiers added to track patients during learning , clustering , and comparison of clinical variables , were arbitrarily assigned for the purposes of this study .
overall , no significant associations were identified between any single dna repair gene snp and bladder cancer risk .
a marginally significantly increased risk was seen in the xpd codon 751 homozygote variant among subjects who never smoked .
the xrcc1 191 variant allele was associated with reduced bladder cancer risk among heavy smokers .
mdr analysis identified pack - years smoking as the strongest single factor for predicting bladder cancer risk ( average testing accuracy=0.63 ) . the best two - factor model included xpd 751 and xpd 312 ( average testing accuracy=0.65 ) .
the best three - factor model ( also the best overall model ) added pack - years smoking to xpd 751 and xpd 312 ( average testing accuracy=0.66 ) .
the application of information theory suggested that the relationship between the two xpd snps and bladder cancer is mostly non - additive ( ie , epistatic ) , while the effect of smoking is mostly additive .
further analysis indicated that the combination of these snps into a haplotype indicated that a variant xpd haplotype was more susceptible to bladder cancer , an effect that was magnified with the inclusion of smoking .
xpd stands for xeroderma pigmentosum group d , the gene encoding an enzyme in the nucleotide excision repair pathway .
this enzyme is known to remove certain dna crosslinks , ultraviolet photolesions , and bulky chemical adducts.43 interactions between xpd 312 and xpd 751 have also been seen in relation to lung cancer risk , and several studies found that the risk of lung cancer associated with the variant allele was higher among non - smokers than among smokers.44 
 45
the most unique feature of m - lcs is that it evolves a population of rules which collectively constitute the learned prediction model . learning proceeds iteratively , with the rule population training on one instance from the dataset at a time .
rule discovery is largely achieved with a genetic algorithm operating at the level of individual rules within the population . for a complete lcs introduction and review ,
see urbanowicz and moore.35 ucs46 is an m - lcs based largely on the popular xcs ( extended classifier system ) algorithm47 but replaces reinforcement learning with supervised learning .
ucs was designed specifically to deal with single - step problems such as classification and data mining , where delayed reward is irrelevant , and showed particular promise when applied to epistasis and heterogeneity as we showed in a previous study.36 previously , we developed the af - ucs algorithm,41 an expansion of ucs which incorporated attribute tracking and feedback into the basic supervised learning algorithm .
each rule includes a condition and class ( ie , if certain instance attributes have a specific state , then the rule predicts the specified class ) .
rules are built using a quaternary representation , where each attribute of the condition will either specify an snp genotype encoding ( ie , 0 , 1 , 2 ) or that attribute will be generalized ( ie ,  #  , wild / don't care ) . the right - hand yellow box in figure 1 gives an example ( c ) including three hypothetical rules represented in this manner .
notice that their conditions all match the example training instance , and they all specify the correct class of the instance .
outline of the af - ucs ( attribute feedback - supervised classifier system ) algorithm .
( 1 ) learning occurs iteratively , focusing on a single training instance from the dataset at a time . ( 2 ) training instance passed to the population of rules ( p ) .
( 3 ) match set ( m ) is formed , including any rule in ( p ) that that has a condition matching the attribute states of the instance .
( 4 ) correct set ( c ) is formed , including any rule in ( m ) which specifies the correct class of the instance .
( 5 ) if no rules are found for ( c ) , randomly generate such a rule using the covering mechanism .
( 6 ) update rule parameters in ( m ) and ( c ) ( eg , rule fitness ) . ( 7 ) use rules in ( c ) to update attribute tracking scores for current instance .
( 8) the genetic algorithm ( ga ) selects parent rules from ( c ) based on fitness and generates offspring rules which are added to ( p ) .
if attribute feedback is being used , the attribute tracking scores for the current instance are applied as weights to guide the ga .
( 9 ) deletion mechanism removes rules from ( p ) based on fitness whenever the size of ( p ) is greater than the user - specified maximum population size .
while the majority of af - ucs is equivalent to ucs , the dark blue box in figure 1 highlights the mechanism unique to our algorithm .
attribute tracking is a collective form of memory designed to be applied to single - step supervised learning problems .
essentially this mechanism learns which attributes are most important to the accurate classification of each individual instance , storing and accumulating this knowledge independently of the rule population .
attribute feedback is a heuristic that draws upon the knowledge learned in attribute tracking to promote efficient generalization and improve learning in the presence of noisy , complex , and heterogeneous data .
attribute feedback probabilistically directs generalization pressures in the ga based on relative attribute tracking scores .
previously , af - ucs was evaluated using only simulated datasets . in order to accommodate the nature of real - world datasets
, one minor modification was made to the algorithm . to address the calculation of training and testing accuracy when the algorithm is applied to unbalanced datasets we replaced the traditional accuracy calculation with balanced accuracy
as described by velez et al.48 we had previously implemented attribute tracking and feedback into af - ucs , a python encoding of the ucs algorithm.36 
 41 we adopted mostly default m - lcs run parameters .
parameters unique to this study include 200  000 learning iterations , a rule population size of 1000 , tournament selection , uniform crossover , subsumption , attribute mutation probability=0.04 , crossover probability=0.8 , and a  of 1 .
 has been described as a  constant set by the user that determines the strength ( of ) pressure toward accurate classifiers49 and is typically set to 10 by default .
a low  was used to place less emphasis on high accuracy in this type of noisy problem domain , where 100% accuracy is only indicative of over - fitting . also , as in our previous study,36 we employed a quaternary rule representation , where for each snp attribute , a rule can specify genotype or covariates as ( 0 , 1 , or 2 ) , or instead generalize with  #  , a character that implies that the rule does not care about the state of that particular attribute .
generally speaking , the use of larger population sizes and a greater number of learning iterations can improve the resulting performance of the evolved m - lcs rule population .
it is likely that optimization of these and other run parameters would further improve the performance of the af - ucs algorithm .
we adopted the analysis pipeline40 for the identification of significant predictive attributes identified by the af - ucs algorithm .
our analysis includes the following steps : ( 1 ) run the af - ucs algorithm on the dataset using 10-fold cross - validation ( cv ) , ( 2 ) run a permutation test with 1000 permutations , ( 3 ) confirm significance of testing accuracy , ( 4 ) identify significant attributes and significantly co - occurring pairs of attributes , ( 5 ) train the af - ucs algorithm on the whole dataset ( no cv ) , ( 6 ) generate visualization for pattern characterization , ( 7 ) repeat steps 13 as a second pass on the dataset that only includes attributes identified as significant from the first pass , ( 8) identify significant , stable clusters of subjects using attribute tracking scores , and ( 9 ) compare clinical variables between identified subject clusters .
although we do not claim that this analysis pipeline is necessarily optimal , we have attempted to assemble a logical series of analytical steps that rely primarily on statistically significant empirical observations .
indeed it is likely that there are other reasonable ways to approach knowledge discovery and hypothesis generation in this context .
our first - pass analysis of the bladder cancer data ( summarized by steps 16 ) began by running af - ucs on the dataset using 10-fold cv strategy in order to determine average testing accuracy and account for over - fitting .
the dataset was randomly partitioned into 10 equal parts and af - ucs was run 10 separate times during which 9/10 of the data was used to train the algorithm , and the other 1/10 was set aside for testing .
we generated 1000 permuted versions of the original dataset by randomly permuting the affection status ( class ) of all samples , while preserving the number of cases and controls .
next , we confirmed that the average testing accuracy was significantly higher than expected by random chance .
if average testing accuracy had not been significantly high , this would have suggested that af - ucs was unable to learn any useful generalizations from the data , excluding a need for further analysis .
we used a typical one - tailed permutation test with a significance threshold of p<0.05 .
once a significant testing accuracy was confirmed , we used the permutation test to identify attributes in the dataset that showed significant importance in making accurate classifications .
as detailed elsewhere,40 we used the following statistics for making such an inference from the rule population : ( 1 ) specificity sum ( sps ) and ( 2 ) accuracy - weighted specificity sum ( awsps ) .
additionally , we used the permutation test to evaluate attribute interactions and to help to discriminate between interaction and heterogeneity .
this was achieved by evaluating a co - occurrence statistic ( cos ) that examined all pairwise attribute co - occurrence within rules of the population.40 we calculated cos for every non - redundant pairwise combination of attributes in the dataset . in this 10-attribute dataset we calculated 45 coss .
these coss were also used to generate the co - occurrence network given in the results . to generate the co - occurrence network we used gephi ( http://gephi.org/)open-source graph visualization software . with the 45 coss calculated above
using gephi , we generated a fully connected , undirected network , where nodes represent individual attributes , the diameter of a node is the sps for that attribute , edges represent co - occurrence , and the thickness of an edge is the respective cos .
gephi offers a built - in function to filter edges from the network based on edge weight .
this was for rule population visualization purposes ( ie , the generation of a rule population heat - map ) . in another study40
we detailed the re - encoding of the rule - population in preparation for visualization .
we employed agglomerative hierarchical clustering using hamming distance as the distance metric http://gephi.org/. clustering was performed on both axes ( ie , across rules and attributes ) .
both clustering and 2d heat - map visualization were performed in r using the hclust and gplots packages , respectively .
we extended this analysis to a second pass over the data that focused exclusively on those attributes identified as significant in the first pass .
we repeated steps 13 including cv , permutation testing , and statistical evaluation of average testing accuracy . also , we ran af - ucs without cv on a subset of the dataset that included only these significant attributes in order to obtain a matrix of attribute tracking scores for further investigation .
attribute tracking keeps a record of which attributes are most important for accurate classification for each subject in the dataset .
therefore , by clustering subjects in the dataset by these attribute tracking scores we aimed to identify homogeneous groups of subjects defined by similar patterns of attributes determined to be important for accurate classification . as we discussed elsewhere,41 before clustering we normalized
normalization was achieved by dividing each tracking score by the sum of all tracking scores for that instance . this allowed us to compare relative attribute patterns between instances in the dataset .
our strategy for the selection of significant stable subject clusters involved hierarchical clustering with an assessment of uncertainty .
we applied pvclust , an r package that calculated p values for hierarchical clustering via multiscale bootstrap resampling.50 significant clusters were identified using approximately unbiased ( au ) p values , where au values > 95% were deemed significant .
once calculation of p values was complete we assigned alphabetical group ids to unique , significant clusters .
finally , we compared the clinical variables between cases found in respective significant subject clusters .
the clinical variable data was only applicable to the bladder cancer cases in our study group .
all the following statistical evaluations were also performed in r. next , we discuss our evaluation of the continuous clinical variables ( ie , age at diagnosis , survivorship , and time to recurrence ) .
wallis one - way analysis of variance was used to determine whether these clinical variables differ by cluster .
in addition , we performed  time - to - failure analyses ( ie , survival analysis ) for age at diagnosis , survivorship , and time to recurrence including failure curves ( ie , kaplan  meier curves ) for each . since both survivorship and time to recurrence data include censored values , we adopted a cox proportional hazard regression model ( coxph ) , most widely used in medical studies .
since age at diagnosis could logically affect survivorship or time to recurrence we included it as a covariate in the covariance analysis model .
we began with a cox proportional hazard model including the interaction between cluster i d and age at diagnosis .
next we used the step function to choose the best factors to keep in the model by akaike 's information criterion ( aic ) .
aic takes into account the balance between goodness of fit , and the number of parameters included in a model .
follow - up analysis of variance between the best model identified by aic , and a similar model excluding group specification , indicates whether there is a significant difference in our clinical outcome variable based on group designation .
tumor stage and grade was a categorical variable , we adopted a  test of homogeneity in order to look for differences between the cases of different clusters . noting that certain cells of the table had very few counts
after a first - pass analysis of the bladder cancer dataset with af - ucs we observed an average training accuracy of 0.6995 and a significant average testing accuracy of 0.6042 averaged over 10-fold cv ( p=0.001 ) .
table  1 summarizes the sps and awsps statistics for each factor in the dataset .
note that significantly larger sps and awsps statistics were seen for xpd 751 , xpd 312 , and pack - years than would be expected by chance .
this finding corresponds with the results obtained using mdr in the study by andrew et al.42 although not statistically significant , the next largest sps or awsps was seen for xrcc1 194 .
recall that the study by andrew et al,42 a smoking - conditional decreased risk was found for this snp .
sps , awsps , and significant cos results awsps , accuracy - weighted specificity sum ; cos , co - occurrence statistic ; sps , specificity sum .
seven of the possible 45 attribute combinations were found to occur more frequently than would be expected by chance . in particular , notice that the largest cos value was found for the attribute combination ( xpd 751 & xpd 312 ) .
this is in line with the best two - attribute model identified by mdr in andrew et al.42 we also noted that the ( xpd 751 & pack - year ) cos value was the second most strongly observed pair .
this seems to correspond with the observation in andrew et al42 that the xpd 751 homozygote variant indicated a marginally significant increase in risk among subjects who never smoked .
in fact , all pairwise combinations including xpd 751 , xpd 312 , and pack - year were found to be significantly over - represented here , including ( xpd 312 & pack - year ) . however , the cos value for ( xpd 751 & xpd 312 ) was about 1.5 times larger than that for ( xpd 312 & pack - year ) .
the relative dissimilarity of the coss for these pairwise combinations does not support a clear three - way interaction to explain the dataset as a whole.40 if it did , we would expect more similar cos scores for all three combinations .
figure  2a presents a visualization of the rule population evolved by af - ucs when trained on the entire bladder cancer dataset .
first , xpd 751 and xpd 312 clustered together as columns indicating a tendency for both snps to be specified in rules concurrently .
second , specification of pack - years did not cluster together with xpd 751 and xpd 312 , suggesting an independent , and potentially heterogeneous relationship .
figure  2b , c give the co - occurrence network constructed using the cos values from this analysis .
again we observed evidence of interaction between xpd 751 and xpd 312 , and somewhat less evidence for other attribute pairs .
( a ) heat - map visualization of the evolved af - ucs ( attribute feedback - supervised classifier system ) rule population .
each row in the heat - map is 1 of 1000 rules comprising the population .
yellow indicates specification of a respective attribute within a rule , while blue indicates generalization ( ie , 
( b ) illustrates the co - occurrence network , appearing as a fully connected network before any filtering is applied .
the diameter of a node is the sps for that attribute , edges represent co - occurrence , and the thickness of an edge is the respective cos .
( c ) the network after filtering out all coss that did not meet the significance cut - off point .
clustering of normalized attribute tracking scores with pvclust , for the set of 10 attributes in the data yielded a total of 82 significant stable clusters .
the largest cluster included only 106 subjects , with subject counts in subsequent clusters dropping off quickly .
the large number of clusters is the result of including attribute patterns that are not necessarily useful in characterizing the significant underlying associations with disease risk . in the interest of exploring an analysis pathway that focuses only on significant attributes
, we performed a second - pass analysis of the data that included only attributes xpd 751 , xpd 312 , and pack - years .
we expected that this would yield larger clusters of subjects for comparison . after this secondary analysis of the bladder cancer dataset , including only attributes ( xpd 751 , xpd 312 , and pack - years ) , we observed an average training accuracy of 0.6989 and a significant average testing accuracy of 0.6968 averaged over 10-fold cv ( p=0.001 ) . recall that the mdr model that included these attributes reported a testing accuracy of 0.66 , and an accuracy of 0.5 would be expected by random chance .
we trained af - ucs on the entire three - attribute dataset and used pvclust to identify significant , stable clusters of samples as previously described .
a visualization of these clustered and normalized attribute tracking scores is given in figure 3a .
by far , the largest two clusters were b and d. cluster b indicated a strong pattern of high attribute tracking scores in xpd 751 and xpd 312 , while cluster d indicated a strong pattern of high attribute tracking scores for pack - years .
( a ) heat - map of normalized af - ucs ( attribute feedback - supervised classifier system ) attribute tracking scores for entire bladder cancer dataset ( three significant attributes ) .
each row in the heat - map is one of 914 instances comprising the dataset .
owing to their small size , clusters f and g are not labeled , but can be seen between clusters a and b. cluster g is adjacent to b , while cluster f is adjacent to a. in order to better highlight the attribute patterns underlying these clusters , the normalized attribute tracking scores are further scaled by instance using the scale feature in pvclust .
( b  d ) kaplan  meier plots comparing different clinical variables for clusters b and d. plus signs in the curve indicate censoring . once clusters were identified we looked for differences in clinical outcome variables for the cases in these groups .
cluster g included no cases , and therefore was not included in our subsequent analysis of clinical variables .
f yielded a marginally significant difference for age at diagnosis ( p=0.076 ) , a significant difference for survival time ( p<0.05 ) , and a marginally significant difference for time to first recurrence ( p=0.094 ) . for the remainder of this analysis we focused on clusters
b and d , as they were by far the largest of the subject clusters . mann 
whitney tests comparing clusters b and d yielded a significant difference for age at diagnosis , survival time , and recurrence ( p<0.05 ) .
meier plots illustrating  time to failure differences between clusters b and d. we supplemented these curves by performing failure analysis for each , as previously described .
examination of age of diagnosis yielded no significant difference between curves b and d as illustrated in figure 3b .
stepwise regression analysis indicated no significant interaction effect between diagnosis and cluster i d . however , aic suggested that the best model included both factors as main effects .
the final survival model indicated that both age at diagnosis ( hr=0.07 , 95% ci 1.05 to 1.10 ) and cluster i d ( hr=0.63 , 95% ci 0.44 to 0.91 ) were significant ( p<0.05 ) .
follow - up analysis of variance comparing the model with and without cluster i d indicated that there was indeed a significant survivorship difference between clusters b and d ( p<0.05 ) even after correcting for age at diagnosis as a covariant .
a similar analysis of recurrence indicated no significant interaction effect between recurrence and cluster i d .
however , subsequent analysis of the final model indicated that while age of diagnosis ( hr=1.03 , 95% ci 1.01 to 1.05 ) was significant ( p<0.05 ) , cluster i d ( hr=0.71 , 95% ci 0.50 to 1.00 ) was only marginally significant ( p=0.054 ) .
follow - up analysis of variance comparing the model with and without cluster i d confirmed that the difference in recurrence between clusters b and d was only marginally significant after taking age of diagnosis into account ( p=0.052 ) .
lastly , we found that the data were too sparse to successfully complete either a  test or a fisher 's exact test between all clusters and all stage / grade categories .
examination of stage / grade counts showed that the vast majority of cases included in the study were characterized as non - invasive low grade ( the least severe of the categories ) .
comparisons of stage / grade between clusters b and d alone yielded no significant findings .
this study explored the application of an m - lcs analysis pathway to the investigation of bladder cancer susceptibility and clinical outcome .
our approach employed an adaptive stochastic search algorithm that makes no assumptions about the underlying patterns of association .
we extended a previously described analysis pipeline for knowledge discovery and an attribute tracking strategy for the characterization of heterogeneity .
this investigation successfully replicated previous findings that implicate xpd 751 , xpd 312 , and pack - years of smoking as significant predictors of bladder cancer susceptibility.42 additionally , we extended the characterization of these predictive factors , identifying evidence of interaction between xpd 751 and xpd 312 , and evidence of heterogeneity between smoking and these genetic factors .
we identified two large subgroups of subjects , with unique underlying patterns of attributes important for accurate classification .
statistical analyses comparing clinical phenotypes between these groups yielded a significant and dramatic difference in patient survival time , together with a marginally significant difference in time to first bladder tumor recurrence ( each after correcting for age of diagnosis ) .
closer inspection showed that patients within cluster b ( within which the two xpd snps were the most important factors for accurate classification ) tended to be diagnosed earlier , displayed a significantly increased survivorship , and a marginally significant increase in time to recurrence .
alternatively , patients in cluster d ( within which pack - years smoking was the most important factor for accurate classification ) tended to be diagnosed later with a significantly shorter survivorship and a marginally significant decrease in time to recurrence .
although it is certainly no revelation that smoking can negatively influence patient health , we have uncovered evidence of a potentially heterogeneous smoking effect ( ie , phenocopy ) not previously characterized .
these findings support our claim that this proposed m - lcs analytic pathway can accommodate underlying heterogeneity and can also be used to characterize it .
this methodology was designed to guide the dissection of disease heterogeneity , supporting the identification of patient subgroups which may be indicative of disease subtypes .
additionally , the ability to characterize a patient - specific pattern of association is advantageous for the development of personalized medicine .
specifically , this strategy could be applied to enable targeting personalized screening and treatment regimens to appropriate subsets of patients . while the results presented in this study illustrate the promise of our proposed methodology
however , this algorithm has the advantage of making no assumptions about the underlying patterns of association .
it can uniquely identify predictive attributes in the context of higher - order interactions while simultaneously identifying subject subsets with respect to heterogeneous patterns , something no other established methodology can boast .
alternative strategies for determining patient subsets from attribute tracking scores will be considered in future work .
additionally , the hypotheses generated by this work must be followed up with laboratory validation .
perceived heterogeneous patterns might alternatively be indicative of higher - order interaction , or the absence of other critically predictive factors .
alternative algorithms that specialize in modeling epistatic interactions ( such as mdr ) may subsequently be run independently on subject subsets to better characterize the predictive attributes involved in these ideally more homogeneous groups .
this proposed strategy should benefit the generation of a more targeted hypothesis and help to identify patient subgroups based directly on patterns of association as opposed to potentially inappropriate or incomplete covariate - based data stratification .
 background and objectivedetecting complex patterns of association between genetic or environmental risk factors and disease risk has become an important target for epidemiological research . in particular , strategies that provide 
 multifactor interactions or heterogeneous patterns of association can offer new insights into association studies for which traditional analytic tools have had limited success.materials and methodsto concurrently examine these phenomena , previous work has successfully considered the application of learning classifier systems ( lcss ) , a flexible class of evolutionary algorithms that distributes learned associations over a population of rules . subsequent work dealt with the inherent problems of knowledge discovery and interpretation within these algorithms , allowing for the characterization of heterogeneous patterns of association . whereas these previous advancements were evaluated using complex simulation studies , 
 this study applied these collective works to a  real - world genetic epidemiology study of bladder cancer susceptibility.results and discussionwe replicated the identification of previously characterized factors that modify bladder cancer risk  namely , single nucleotide polymorphisms from a dna repair gene , and smoking . 
 furthermore , we identified potentially heterogeneous groups of subjects characterized by distinct patterns of association . 
 cox proportional hazard models comparing clinical outcome variables between the cases of the two largest groups yielded a significant , meaningful difference in survival time in years ( survivorship ) . a marginally significant difference in recurrence time was also noted . 
 these results support the hypothesis that an lcs approach can offer greater insight into complex patterns of association.conclusionsthis methodology appears to be well suited to the dissection of disease heterogeneity , a key component in the advancement of personalized medicine . 
Background and significance
Materials and methods
Dataset
Summary of previous findings
AF-UCS
Statistical analysis
Results and discussion
Conclusion