BACKGROUND
in principle, an enormous amount of information about biological function and the genetic mechanisms of disease resides in high-throughput data and one of the major challenges of computational biology is to extract this knowledge using techniques from machine learning and statistical inference.
in particular, many classification techniques developed in the statistical learning community have been applied to cancer diagnosis, prognosis and sub-type identification based on gene expression microarrays.
nonetheless, the clinical applications resulting from statistical analyses remain somewhat limited.
indeed, a certain skepticism is well-founded since results, for instance "signatures" and reported error rates, obtained in one study often do not generalize to another.
in the case of molecular cancer diagnosis and prognosis from gene expression data, there are several plausible reasons for these difficulties.
one issue is certainly the high dimensionality of the data relative to the typical sample size, the well-known "small n, large p" dilemma.
a typical microarray data set contains expression values of thousands to tens of thousands of transcripts but for only tens or at most hundreds of samples.
this technical barrier can be somewhat lowered by aggregating data from different studies so as to reach samples sizes in the hundreds, but this may still be "small" relative to the complex interactions among the observed variables that one would like to uncover.
another important obstacle to both biological understanding and clinical applications is the "black box" nature of the decision rules produced by most machine learning classification methods.
these rules generally involve a great many genes combined in a highly nonlinear fashion.
this is not surprising: by and large, these techniques were developed in other communities, notably pattern recognition, computational vision and computational speech, where data are plentiful and transparency of the decision rules is generally not a criterion for success.
in contrast, simplicity and interpretability are highly desirable features for biomedical applications.
breast cancer prognosis is at the forefront of the application of classification rules based on gene expression, as three such assays have been recently approved for use in clinical management of patients.
for a complete review of these assays and their validation see  <cit> .
the three assays differ in several respects: the technology used to measure gene expression, the classification algorithms used, the number of genes considered , the way they were developed, and the degree of their validation on independent populations in real clinical settings.
importantly, none of the classification algorithms used is easily categorized into a well-known machine learning technique.
all are based on thresholds applied to compounded continuous scores obtained through a mix of classification techniques, empirical observations, and biological insight applied to the training sets.
this puts a barrier between statistical learning and current clinical applications, and emphasizes the need for classification rules that are interpretable and as independent as possible from the specific technology used for the measurement of biological markers, since technology is continuously evolving.
in view of these considerations, achieving statistically stable and biologically relevant results argues for a different strategy, particularly if we wish to go beyond a mere list of "biomarkers" to identifying potential "marker interactions" among several genes.
a promising alternative is to base prediction entirely upon the relative expression ordering of a small number of genes.
the simplest variation on this theme is to base classification on ratios of expression values, first introduced in a heuristic way in  <cit>  and independently developed as a general, data-driven procedure, the tsp algorithm, by  <cit> , and later applied to learn cancer biomarkers and induce elementary prediction rules for cancer diagnosis and prognosis in  <cit> .
it has also recently been applied to differentiate between gastrointestinal stromal tumors and leiomyosarcomas  <cit> , resulting in a nearly-perfect two-gene classifier, and to predict response to the farnesyltransferase inhibitor tipifarnib in acute myeloid leukemia  <cit> .
specifically, one need only compare the expression values among two genes, thus providing a specific hypothesis for follow-up studies.
the tsp algorithm is illustrated in figure  <dig> for the lung data from  <cit> , where the objective is to distinguish between malignant pleural mesothelioma  and adenocarcinoma  of the lung.
the purpose of this example is only to visualize the tsp decision process, not to re-analyze the lung data.
in the left panel, mpm and adca samples are well-separated by comparing the expression values of the genes kir2dl <dig> and rock <dig> whereas in the right panel the comparison is based on bin <dig> and anxa <dig>  the high accuracy obtained, roughly 98%, corroborates the findings in  <cit> , in which several genes are first identified based on fold changes, standard t-tests, expression cutoffs, etc., and then multiple ratios are formed and used both individually and in combination.
in contrast, the pairs in figure  <dig> are unrestricted, allowing for non-differentially-expressed genes to appear.
whereas ad hoc, and not rank-invariant, the approach in  <cit>  illustrates the power and transparency of simple decision rules.
a remaining obstacle to an even broader applicability of the tsp   methodology  is the heterogeneity of molecular mechanisms underlying the same disease   phenotype.
in cancer, for example, tumors that would look similar under a microscope can present different expression patterns.
when this is the case, it is a challenge to identify single pairs with good discrimination.
this is illustrated by a simple, artificial example in figure  <dig>  there are two latent subclasses among the cancer samples, captured by the two relative orderings between gene  <dig>  and gene  <dig> .
these could be two genes whose activity is sufficient to activate the same cancer-related pathway, or they could each flag the activation of alternative cancer-related pathways.
using these two genes alone we cannot distinguish between a normal and an ill patient based on their relative ordering since the cancer phenotype can have either ordering.
however, if we combine these two genes with a suitable "reference" gene, the cancer can then be identified, since the reference gene, while relatively stable overall, is the most highly expressed in most of the normal samples but rarely in cancer.
motivated by these considerations, as well as the broader goal of extending tsp to more genes in order to increase accuracy without sacrificing interpretability, we explore the differing roles the genes play in the decision mechanism and apply this methodology to two problems in breast cancer.
the first is of direct clinical applicability, while the second is chosen because it provides opportunities for cross-study validation.
the top-scoring triplet  classifier is based on the expression orderings among three genes.
in both tsp and tst, "score" refers to the apparent classification rate, defined here as the average of sensitivity and specificity.
given any triplet of genes, the classification rule is then determined by maximum likelihood: choose the class for which the observed ordering is most likely.
the probabilities  are estimated from the training data.
as with tsp, there are no parameters to tune and classification results are invariant to any form of data preprocessing and normalization which preserves the ranking among the expression values within a sample.
clearly, tst is potentially more discriminating than tsp since there are now six possible orderings and this refinement of two-gene orderings can sometimes capture interactions that are not accessible to the tsp classifier; in particular, tst significantly out-performs tsp in detecting brca <dig> mutations.
we refer to the family of methods encompassing both tsp and tst as rxa, for "relative expression analysis."
the simplicity of rxa for a small number of genes allows for an exploration of the differing roles played by the genes in phenotype distinction.
returning to figure  <dig>  notice that both genes for the pair on the right are differentially expressed, although bin <dig> more so than anxa <dig>  whereas clearly only kir2dl <dig> is differentially expressed for the pair on the left, in which the gene rock <dig> serves as a "pivot" or "reference".
moreover, the situation depicted in the artificial example figure  <dig> appears in our featured application to detecting brca <dig> mutations:  the top-scoring triplet of genes contains a pivot gene, tmem <dig>  which  always sits between two differentially expressed genes, ppp1cb and rnf <dig>   in mutated tumors.
ppp1cb encodes for a protein shown to directly interact with brca <dig>  and is expressed at high levels in mutants.
rnf <dig> is a co-factor that modulates hormone nuclear receptors activity, including the estrogen and androgen receptors, an activity similar to that of the brca <dig> protein itself, and is expressed at low levels in mutants.
the role of pivot genes is elaborated in the discussion.
in summary, we report on i) a computational advance, namely a general rxa framework for phenotype identification based on genomic features, including a rigorous and systematic comparison with earlier approaches in a variety of cancer studies; ii) a cross-study validation based on the notoriously hard problem of predicting er status in breast cancer; and iii) a clinically relevant application to predicting germline brca <dig> mutations in breast cancer, including extensive bioinformatic analysis to provide biological interpretation for the proposed predictor.
RESULTS
the performance of the tsp algorithm has been previously validated in  <cit> .
this section is organized as follows.
first, general validation results are presented which demonstrate the advantages of bringing in a third gene for a variety of well-known studies in molecular cancer diagnosis and subtype identification from microarray data.
next, we focus on interpreting the decision rules in terms of the different biological roles played by the three participating genes.
the main application – detecting brca <dig> mutations – is then presented.
our three-gene classifier achieves an overall accuracy of 94% in cross-validation on the combined van't veer and hedenfalk datasets, which well exceeds the performance of several well-known methods.
finally, we present a cross-study validation of our methodology in the context of another important classification problem in breast cancer – predicting er status.
general validation
in table  <dig> we compare the classification accuracy of two-gene and three-gene versions of rxa for nine cancer datasets summarized in table  <dig>  the three-gene version is tst, which restricts all three genes to the ten most differentially expressed; see methods.
in order to ensure a fair comparison, we restricted the two genes in tsp to be among the sixteen most differentially expressed.
since the number of ways to select three genes from ten, namely  <dig>  is the same as the number of ways to select two genes from among sixteen, the total number of candidate classifiers is identical.
the classification rates are estimated by leave-one-out cross validation.
in both cases, the genes are restricted to a subset of differentially expressed genes based on a wilcoxon rank test; the details appear in § <dig>  and § <dig> .
the subsets are selected to ensure that the number of possible two-gene and three-gene classifiers are the same.
score permutation tests for tst for six of the nine datasets are depicted in figure  <dig>  for each dataset, we randomly permuted the class labels  <dig> times and computed the score s, the average of sensitivity and specificity, for the top-scoring triplet.
artificial data created in this way preserves both the sample sizes and the overall dependency structure among the genes.
shown is the histogram of scores with the score of the real dataset marked by a red cross.
as can be seen, all six scores are highly significant with p-values of zero.
the probability tables for these same six datasets are given in table  <dig> and the names of the genes in the top-scoring triple are listed in table  <dig>  for example, from table  <dig> we see that, for the colon study, the preferred ordering among normal samples is xj <xi <xk, and xk is never the least expressed among these samples; as seen in table  <dig>  gi, gj, gk, represent vip, dars, fcgr3a.
similarly, in the lung data, among the mpm samples, gene gj is always the least expressed, but never so among the cancer samples.
each portion of the corresponds to one study with two phenotypes.
for each study and each phenotype, the table shows the relative frequencies of the six possible orderings among the expression values of the top-scoring triple for the samples in the study.
the gene triple  for each study is given in table 4
the three genes in the top-scoring triplet for each of the six studies.
the histograms of scores for the top-scoring triple classifier for the other three datasets are given in figure  <dig>  as can be seen, the top scores for prostate <dig> and prostate <dig> are still significant, although less so than for the six studies in figure  <dig>  whereas the top score for the cns dataset is at best borderline significant.
this may not be surprising in view of the very small number of samples for the minority class in both prostate <dig> and cns.
over-fitting is very difficult to avoid with only nine samples for one of the classes; see table  <dig>
biological roles
for the tsp algorithm, there are two prototypical situations: either both gi and gj are differentially expressed in opposite directions or only gi is differentially expressed and gj serves as a "pivot" or "reference" for gi, in effect a random threshold; see methods.
call these two cases  and .
a biological mechanism leading to the  case may occur when the two genes are involved in competing processes, e.g., one gene may be an oncogene and the other a tumor suppressor gene.
the  case was illustrated in figure  <dig> for separating malignant pleural mesothelioma  and adenocarcinomas : rock <dig> serves as a pivot for kir2dl <dig>  which is up-regulated in mpm samples.
the expression of rock <dig> is relatively stable across the two phenotypes.
the role of "pivot genes" is elaborated in the discussion section.
several typical cases emerge for three genes.
one is , meaning that all three genes in the top-scoring triplet are differentially expressed.
this is illustrated for the lung study in the left panel of figure  <dig>  where the gene triplet is the one selected by the tst algorithm.
another case is , signifying that two of the three genes are differentially expressed and the third is not, serving instead as a reference for the other two.
this is illustrated in the right panel of figure 5; the gene triplet comes from tst, in which one of the three genes is unrestricted.
this is also what emerges for the top-scoring triplet in the brca <dig> study; see again the treatment of pivot genes in the discussion section
identifying brca1-related breast cancer
we now consider the identification of breast tumors that arose as the result of an inherited deleterious mutation of the brca <dig> gene.
brca <dig> is a tumor suppressor gene whose altered function is associated with breast, ovarian and other cancers  <cit> .
deleterious germline mutations of brca <dig> have been estimated to occur in  <dig> in  <dig> ashkenazi jews and  <dig> in  <dig> non-ashkenazi  <cit>  and are responsible for a significant fraction of inherited breast cancer cases  <cit> .
genetic testing for germline mutations is available commercially.
testing is expensive and, despite significant recent improvements, still incomplete in its sensitivity  <cit> .
for women newly diagnosed with breast cancer, and a family history of the disease, knowledge of whether they harbor germline mutations is of help in guiding decisions about prevention of contralateral breast cancer and ovarian cancer.
prevention options include radical surgery.
therefore, the availability of inexpensive expression markers for brca <dig> mutations based on tumor samples would significantly improve the clinical management of these women, and contribute to more efficient prevention within their families.
we apply the tst algorithm  to predict brca <dig> mutant status, using two breast cancer gene expression microarray data sets available from the public domain.
the raw data can be downloaded from the supporting websites of the two published manuscripts  <cit> .
the two studies, designated van't veer and hedenfalk, are generated from two different platforms.
after data preprocessing and cross-platform matching , we obtain a combined dataset with  <dig> features and  <dig> samples.
the two classes  are brca1-mutant cancers and non-brca <dig> cancers, with sample sizes  <dig> and  <dig>  respectively.
for the tst algorithm, the score for the top-scoring triplet is .
<dig>  the estimated gene expression ordering probabilities for the genes in this triplet are shown in table  <dig>  since there are about  ×  <dig> ≈  <dig>  triplets having at least two differentially expressed genes, a high score might happen by chance.
however, a permutation test demonstrates that the p-value of score of the top-scoring triplet is virtually zero; see figure  <dig>
estimated probabilities for the six possible orderings among the three genes in the top-scoring triplets for each of the two classes.
here, x <dig>  x <dig>  and x <dig> refer to the expression values of ppp1cb, tmem <dig> and rnf <dig>  respectively.
mutant samples are characterized by a single preferred ordering whereas non-mutant samples display all orderings.
performance
we compare the performance of the tst algorithm with tsp and four well-known machine learning methods: naive bayes , k-nearest neighbor , support vector machine , and random forest .
we use the weka machine learning package  <cit>  which contains all but tsp and tst, as well as several r packages.
for tsp and tst we have developed an r package for relative expression analysis  which incorporates all the versions of tsp and tst used in this paper and which is available for download at .
for nb, k-nn, svm and rf, in order to optimize performance, we report the best results we obtained by taking either the weka default parameters or systematically exploring the parameter spaces, estimating generalization errors with cross-validation.
in the case of svms, this included trying a wide range of combinations for the scale and penalty parameters with the rbf kernel.
table  <dig> summarizes the results of loocv.
as seen, tst has the best overall classification accuracy  and the best sensitivity .
equally noteworthy, tst involves only three genes whereas the four traditional machine learning methods use many more.
estimates are based on leave-one-out cross-validation and accuracy is defined as the average of sensitivity, the percentage of correctly classified brca <dig> samples, and specificity, the percentage of correctly classified nonbrca <dig> samples.
the top-scoring gene triplet is .
table  <dig> gives the empirical probability distribution over the six possible orderings of expression values for each of the two phenotypes.
interestingly, the expression values of this triplet are in the same order
for all brca1-mutant samples; for nonbrca1-mutant samples, the probability distribution is dispersed, almost uniform.
in our study there are  <dig> nonbrca1-mutant samples which exhibit the relation rnf <dig> <tmem <dig> <ppp1cb, of which  <dig> are "basal-like" tumors, a subtype of breast cancer associated with lack of expression of the estrogen receptor and poor prognosis.
interestingly a strong association between the "basal-like" subtype and brca <dig> mutation has been suggested in a number of molecular and pathological studies  <cit> .
the top panel in figure  <dig> shows the expression pattern of the top-scoring triplet.
we can see that ppp1cb is up-regulated in brca <dig> samples, rnf <dig> is down-regulated in brca <dig> samples, while tmem <dig> is rather stable across the two phenotypes.
both ppp1cb and rnf <dig> are highly differentially expressed, actually among the top three, with p-values of  <dig> e -  <dig> and  <dig> e -  <dig>  respectively.
the benefit of the reference gene tmem <dig> is displayed in the bottom panel of figure  <dig>  the decision boundary of the two-gene tsp classifier based on ppp1cb and rnf <dig> is the line y = -x: the upper right area corresponds to ppp1cb > rnf <dig> and the lower left area corresponds to rnf <dig> > ppp1cb.
incorporating tmem <dig> into the decision narrows the upper right "mutant" region to the indicated rectangle where rnf <dig> <tmem <dig> <ppp1cb.
the samples in the two triangular areas would be misclassified based on the expression ordering of the gene pair ppp1cb and rnf <dig> alone whereas they are correctly classified by the tst algorithm.
cross-study validation for er status
estrogen receptor  has been studied in clinical breast cancer for more than  <dig> years.
approximately two-thirds of all breast cancers are er+ at the time of diagnosis  <cit> .
the expression of er has important implications for breast cancer diagnosis and treatment.
in particular, er status correlates well with response to hormonal therapy: er+ patients are much more likely to benefit from such therapy  <cit> .
research shows that er+ and er- tumors display remarkably different gene-expression patterns  <cit> .
here we use the tst method to classify tumors according to their er status.
three breast cancer microarray data sets are included in this study and they are denoted as miller, sotiriou and expobreast.
the raw data of miller and sotiriou can be downloaded from gene expression omnibus or supporting web sites  <cit> , and expobreast can be downloaded from  <cit> .
miller and sotiriou are generated from the affymetrix hgu133a microarray platform and expobreast are generated from hgu133plus <dig>  mas <dig> was used to pre-process the raw data to get probe sets level data.
in order to match the two microarray platforms, we only keep those probe sets that are present on both.
there is an 88-patient overlap between miller and sotiriou, so we exclude the replicate patients from the original sotiriou.
the sample sizes and the phenotype information are shown in table  <dig>
two types of cross-study validation were performed, each involving learning three classifiers.
in the first, there is one classifier for each of the three ways of integrating two of the three microarray data sets to obtain a training set and then using the third one for testing.
in the second case, each classifier is trained on only one dataset and tested on the data obtained by merging the other two.
we restrict our search to genes on five breast cancer related pathways.
there are  <dig> such genes present on the microarray, which correspond to  <dig> probe sets.
information about the five pathways and the  <dig> probe sets can be obtained from the additional files  <dig> and  <dig>
top: classification results when training on the data set obtained by integrating two of the three microarray data sets and testing on the third one.
bottom: classification results when training on one of the three microarray data sets and testing on the data set obtained by integrating the other two.
the numbers in the parentheses are the sensitivity and specificity levels respectively.
discussion
function and interactors of tst genes
in addition to the role of brca <dig> mutations in familial breast cancer, the reduced expression, or incorrect sub-cellular localization of brca <dig> protein, are postulated to be important also in the pathogenesis of sporadic breast cancer.
evaluation of brca <dig> protein expression in  <dig> breast cancer cases has shown that about 50% of the tumors showed loss of nuclear expression or cytoplasmic localization of the protein  <cit> .
the evidence of biological roles of brca <dig> reveals multiple functions for this protein, that may contribute to its tumor suppressor activity, including regulation of cell cycle progression, dna repair, dna damage-responsive cell cycle check-points, apoptosis, and the regulation of a set of specific transcriptional pathways like the androgen receptor's and esr <dig> .
the top scoring triplet identified in our brca <dig> analysis involves ppp1cb, tmem <dig>  and rnf <dig>  the ppp1cb gene is located on chromosomal cytoband 2p <dig>  and encodes one of the three catalytic sub-units of the phosphatase- <dig>  serine/threonine-specific protein phosphatases.
this multimeric complex is involved in protein dephosphorylation within a variety of cellular processes, including cell division, muscle contractility, glycogen metabolism, protein synthesis, and hiv- <dig> viral transcription.
the rnf <dig> gene, also known as ara <dig>  is located on chromosomal cytoband 5q <dig> -q <dig>  and encodes for a protein involved in the modulation, by direct protein-protein interaction, of a number of hormone nuclear receptors, including the androgen receptor , the estrogen receptor , and the growth hormone receptor .
brca <dig> has been shown to directly interact with the andogen receptor, increasing androgen-dependant transcription  <cit> .
this supports our observation that the ar cofactor, rnf <dig> has very low expression in those samples in which brca <dig> function is impaired.
finally, the tmem <dig> gene, located on chromosomal band 1p <dig> , encodes for a protein developmentally regulated in the brain, with predominant expression in differentiating neurons  <cit> .
the biological role of this protein is not yet known.
since a recent study by winter and colleagues showed that all three isoforms of pp <dig>  including ppp1cb, interact with brca <dig>  <cit>  we used protein-protein interaction  data to understand whether the triplet genes  directly interact with each other and with brca <dig>  in addition to the interactions described by winter and colleagues, ppi interaction gene lists included information from three sources: the human protein reference databases   <cit> , biogrid  <cit>  and the biomolecular interaction network database   <cit> .
all protein-protein interactions reported in any of these databases to involve the triplet genes were used, regardless of the techniques employed to identify the interaction, or the type of evidence supporting its inclusion in the databases.
we represented ppi data as adjacency matrices  and displayed the corresponding networks using undirected graphs, where each node represents a protein while edges represent interactions.
no ppi interactions were reported for the pivot gene tmem <dig>  while the other two genes  were found to interact with several other proteins.
although none of such inter-actors is in common between the two proteins, the ppi network revealed a number of shortest paths connecting these two proteins and involving a minimum of two proteins .
one such path accounts for brca <dig> and ar, while the other involves esr <dig>  sm arcb <dig> , nr3c <dig> , and nucleolin .
overall, this analysis suggests that rn f  <dig> and ppp1cb are part of a regulatory network modulating gene expression and involving brca <dig> and a number of hormone nuclear receptors.
pivot genes
as has been seen, one very interesting scenario that often arises in the application of tsp and especially in the application of tst, is that one of the genes appears to play a passive role, serving as a pivot point or benchmark expression level for the others.
this situation is illustrated well in figure  <dig>  where the key biological signal of cancer is that at least one of the pathway-activator genes is expressed above the level of the pivot gene.
it is difficult to assign roles to the genes in a triplet observed in experimental data with any certainty, but expression patterns consistent with the pivot gene theory have been observed very frequently in a wide variety of experiments and we think it important to consider the implications of this when developing and evaluating methodology.
in finding triplets in practice of the methods section, we present practical methods for reducing the triplet search space by recognizing such a division of labor among the genes in a triplet and pre-filtering for genes that, say, could serve as a pivot.
in this section we discuss additional biological and technical consequences of the pivot gene theory.
there are technical issues associated with expression microarrays that make it difficult to find a good pivot gene in practice.
the intensity level of a microarray probe depends on a variety of technical variables in addition to the biological variable of interest, transcript abundance, and so the measured intensity for gene a may exceed that of gene b even when b is present in greater quantity.
in single color microarrays, these probe effects can overwhelm sample to sample differences in gene expression, driving correlations in excess of 95% when expression data obtained from very different samples, but measured on the same array platform are compared.
this works two ways: the availability of a large number of probes with relatively constant intensities at various levels should make it quite easy to find efficient pivots when working on a single platform, while on the other hand, the selected pivot gene may not sit at the same level relative to its partners in the triplet when measured by another technology.
two color arrays offer additional technical challenges and introduce study design issues as well.
classical house-keeping genes, expressed at near constant levels in all cells, should yield expression ratios of  <dig> for any two samples and so may not work well as benchmark expression levels for other genes.
the use of two different dyes for the two samples on an array introduces a technical effect that continues to slightly bias the estimated ratios of individual genes even though the broadest effects are well controlled by standard pre-processing methods  <cit> .
thus, as on single color arrays, pivot genes identified on a two-color platform may be effective only within that technology.
an additional concern arising in two-color studies is the fact that both samples on an array contribute to the expression ratio.
the reference samples included in one study may determine the level of a potential pivot gene or in extreme cases, even drive apparent differential expression that is in fact not present in the population of interest and which therefore will not be observed in another study with a different design.
the successes of the rxa approach clearly demonstrate that these technical challenges can be overcome, and we believe that steps can be taken in implementation to minimize the threat to performance.
careful preprocessing to minimize the influence of technical effects is a crucial step.
principled pre-filtration of array features, as discussed in finding triplets in practice of the methods section, could help by eliminating a large number of apparently irrelevant and possibly misleading probes from consideration.
we also recommend that the rxa classifiers be made as robust as possible by maximizing the diversity of samples and platforms included in the training set.
biological findings
in the present study we apply the tst algorithm to predict brca <dig> mutant status using data from the public domain.
within the training set, our approach enables a correct classification of all brca <dig> mutants considered, while only  <dig> sporadic breast cancers are misclassified.
a number of factors may account for the brca1-like behavior of some of the wildtype tumors.
for example, brca <dig> function may be altered by somatic mutation, methylation or other genetic alterations, or it may be impaired by incorrect cellular localization.
the "basal-like" subtype of breast cancer is associated with lack of expression of the estrogen receptor and poor prognosis.
a strong connection between the "basal-like" subtype and brca <dig> loss of function has been suggested in a number of molecular and pathological studies  <cit> .
among the  <dig> sporadic breast cancer that were misclassified by tst,  <dig> are "basal-like".
since there are  <dig> "basal-like" samples in total, the probability of seeing  <dig> of them in  <dig> randomly chosen samples is indeed small .
therefore, the "basal-like" types are over-represented in the  <dig> nonbrca1-mutant samples which are classified as brca1-mutant cancers by tst, arguing for the biological relevance of the top-scoring triplet.
the analysis of the protein-protein interactions among the top-scoring triplet genes and brca <dig> further suggests that the classifier has a biological foundation.
no interactors were found for tmem <dig>  possibly reflecting its role in the classifier as the pivot gene, while the other two genes showed interactions with many other proteins   involved in breast cancer biology including the brca <dig> protein itself.
ppp1cb is one of the three catalytic sub-units of the protein phosphatase pp <dig>  a  <dig> study shows that all three isoforms of pp <dig> interact with brca <dig>  <cit> .
in the same study, rt-pcr expression analysis indicates that sporadic breast cancers have lower expression levels of ppp1cb than do normal tissues.
the gene expression microarray data that we use show a higher expression level of ppp1cb in brca1-mutant cancers than in sporadic breast cancers.
moreover, the literature also suggests that ppp1cb is a discriminator gene between brca1-mutant and brca2-mutant tumors for both breast and ovarian cancers  <cit> .
although no direct links exist between rnf <dig> and brca <dig>  our ppi analysis shows that indirect interactions occur, and they involve important proteins in breast cancer biology, like the estrogen and androgen receptors.
the expression of the estrogen receptor is a fundamental prognostic factor in breast cancer: hormonal therapy is used in adjuvant settings based on whether cancer cells express it or not.
androgen receptor signaling is also emerging as a relevant pathway for breast cancer biology.
unlike prostate cancer, where ar is sustaining growth of cancer cells, androgen signaling in breast cancer represents a restraint to cancer cell growth, and it has been shown that ar expression correlates with a better prognosis  <cit> .
interestingly, reduced or altered brca <dig> protein expression has been shown to be associated with lack of progesterone and esr <dig>  and expression of the ar  <cit> .
from this perspective, it is important that ar activity is modulated by numerous factors, including rnf <dig> and brca <dig>  <cit> .
while elucidation of the exact mechanisms by which loss of brca <dig> function affects expression of ppp1cb and rnf <dig> awaits additional laboratory work, the evidence we presented strongly suggests that the tst classifier described here has properties that go beyond classification performance and that are capturing genuine biological mechanisms underlying breast cancer pathogenesis.
CONCLUSIONS
we have developed and validated a general rxa approach to building simple and interpretable classifiers using trios of features.
other approaches have been advanced for selecting informative gene triplets and three-gene interactions from expression microarray data.
recently, methods based on fuzzy logic  <cit> , liquid association  <cit>  and a three-way interaction model  <cit>  have been proposed.
in  <cit> , activator-repressor-target triplets are identified using logical relationships among the genes.
liquid association is aimed at capturing the dynamic association between a pair of genes; the correlation between the expression values of a gene pair depends on the expression level of a third gene.
the three-way interaction model is similar, except the third gene plays the role of a qualitative switch rather than a continuous measure as in liquid association.
however, none of these approaches involve inferring phenotype-specific models or classifiers, and none are rank-based.
while statistical and machine learning techniques have contributed  significantly to the interpretation of the large and complex data sets  generated by high throughput genomic techniques, the direct application of these techniques in the clinical management of patients is slowed by challenges in interpretability and cross-study reproducibility.
algorithms based on the relative level of a small number of genomic features provide a formidable simplification, yielding progress in both interpretability and reproducibility, often at little or no cost in terms of accuracy.
this article demonstrates a new incarnation of this philosophy, based on three-gene classifiers, provides a general framework for understanding the roles of the genes involved, and illustrates its potential in the difficult and clinically relevant problem of identifying brca <dig> mutation carriers.

 in principle, an enormous amount of information about biological function and the genetic mechanisms of disease resides in high-throughput data and one of the major challenges of computational biology is to extract this knowledge using techniques from machine learning and statistical inference. in particular, many classification techniques developed in the statistical learning community have been applied to cancer diagnosis, prognosis and sub-type identification based on gene expression microarrays. nonetheless, the clinical applications resulting from statistical analyses remain somewhat limited. indeed, a certain skepticism is well-founded since results, for instance "signatures" and reported error rates, obtained in one study often do not generalize to another. in the case of molecular cancer diagnosis and prognosis from gene expression data, there are several plausible reasons for these difficulties. one issue is certainly the high dimensionality of the data relative to the typical sample size, the well-known "small n, large p" dilemma. a typical microarray data set contains expression values of thousands to tens of thousands of transcripts but for only tens or at most hundreds of samples. this technical barrier can be somewhat lowered by aggregating data from different studies so as to reach samples sizes in the hundreds, but this may still be "small" relative to the complex interactions among the observed variables that one would like to uncover. another important obstacle to both biological understanding and clinical applications is the "black box" nature of the decision rules produced by most machine learning classification methods. these rules generally involve a great many genes combined in a highly nonlinear fashion. this is not surprising: by and large, these techniques were developed in other communities, notably pattern recognition, computational vision and computational speech, where data are plentiful and transparency of the decision rules is generally not a criterion for success. in contrast, simplicity and interpretability are highly desirable features for biomedical applications. breast cancer prognosis is at the forefront of the application of classification rules based on gene expression, as three such assays have been recently approved for use in clinical management of patients. for a complete review of these assays and their validation see. the three assays differ in several respects: the technology used to measure gene expression, the classification algorithms used, the number of genes considered, the way they were developed, and the degree of their validation on independent populations in real clinical settings. importantly, none of the classification algorithms used is easily categorized into a well-known machine learning technique. all are based on thresholds applied to compounded continuous scores obtained through a mix of classification techniques, empirical observations, and biological insight applied to the training sets. this puts a barrier between statistical learning and current clinical applications, and emphasizes the need for classification rules that are interpretable and as independent as possible from the specific technology used for the measurement of biological markers, since technology is continuously evolving. in view of these considerations, achieving statistically stable and biologically relevant results argues for a different strategy, particularly if we wish to go beyond a mere list of "biomarkers" to identifying potential "marker interactions" among several genes. a promising alternative is to base prediction entirely upon the relative expression ordering of a small number of genes. the simplest variation on this theme is to base classification on ratios of expression values, first introduced in a heuristic way in and independently developed as a general, data-driven procedure, the tsp algorithm, by, and later applied to learn cancer biomarkers and induce elementary prediction rules for cancer diagnosis and prognosis in. it has also recently been applied to differentiate between gastrointestinal stromal tumors and leiomyosarcomas, resulting in a nearly-perfect two-gene classifier, and to predict response to the farnesyltransferase inhibitor tipifarnib in acute myeloid leukemia. specifically, one need only compare the expression values among two genes, thus providing a specific hypothesis for follow-up studies. the tsp algorithm is illustrated in figure for the lung data from, where the objective is to distinguish between malignant pleural mesothelioma and adenocarcinoma of the lung. the purpose of this example is only to visualize the tsp decision process, not to re-analyze the lung data. in the left panel, mpm and adca samples are well-separated by comparing the expression values of the genes kir2dl and rock whereas in the right panel the comparison is based on bin and anxa the high accuracy obtained, roughly 98%, corroborates the findings in, in which several genes are first identified based on fold changes, standard t-tests, expression cutoffs, etc., and then multiple ratios are formed and used both individually and in combination. in contrast, the pairs in figure are unrestricted, allowing for non-differentially-expressed genes to appear. whereas ad hoc, and not rank-invariant, the approach in illustrates the power and transparency of simple decision rules. a remaining obstacle to an even broader applicability of the tsp methodology is the heterogeneity of molecular mechanisms underlying the same disease phenotype. in cancer, for example, tumors that would look similar under a microscope can present different expression patterns. when this is the case, it is a challenge to identify single pairs with good discrimination. this is illustrated by a simple, artificial example in figure there are two latent subclasses among the cancer samples, captured by the two relative orderings between gene and gene. these could be two genes whose activity is sufficient to activate the same cancer-related pathway, or they could each flag the activation of alternative cancer-related pathways. using these two genes alone we cannot distinguish between a normal and an ill patient based on their relative ordering since the cancer phenotype can have either ordering. however, if we combine these two genes with a suitable "reference" gene, the cancer can then be identified, since the reference gene, while relatively stable overall, is the most highly expressed in most of the normal samples but rarely in cancer. motivated by these considerations, as well as the broader goal of extending tsp to more genes in order to increase accuracy without sacrificing interpretability, we explore the differing roles the genes play in the decision mechanism and apply this methodology to two problems in breast cancer. the first is of direct clinical applicability, while the second is chosen because it provides opportunities for cross-study validation. the top-scoring triplet classifier is based on the expression orderings among three genes. in both tsp and tst, "score" refers to the apparent classification rate, defined here as the average of sensitivity and specificity. given any triplet of genes, the classification rule is then determined by maximum likelihood: choose the class for which the observed ordering is most likely. the probabilities are estimated from the training data. as with tsp, there are no parameters to tune and classification results are invariant to any form of data preprocessing and normalization which preserves the ranking among the expression values within a sample. clearly, tst is potentially more discriminating than tsp since there are now six possible orderings and this refinement of two-gene orderings can sometimes capture interactions that are not accessible to the tsp classifier; in particular, tst significantly out-performs tsp in detecting brca mutations. we refer to the family of methods encompassing both tsp and tst as rxa, for "relative expression analysis." the simplicity of rxa for a small number of genes allows for an exploration of the differing roles played by the genes in phenotype distinction. returning to figure notice that both genes for the pair on the right are differentially expressed, although bin more so than anxa whereas clearly only kir2dl is differentially expressed for the pair on the left, in which the gene rock serves as a "pivot" or "reference". moreover, the situation depicted in the artificial example figure appears in our featured application to detecting brca mutations: the top-scoring triplet of genes contains a pivot gene, tmem which always sits between two differentially expressed genes, ppp1cb and rnf in mutated tumors. ppp1cb encodes for a protein shown to directly interact with brca and is expressed at high levels in mutants. rnf is a co-factor that modulates hormone nuclear receptors activity, including the estrogen and androgen receptors, an activity similar to that of the brca protein itself, and is expressed at low levels in mutants. the role of pivot genes is elaborated in the discussion. in summary, we report on i) a computational advance, namely a general rxa framework for phenotype identification based on genomic features, including a rigorous and systematic comparison with earlier approaches in a variety of cancer studies; ii) a cross-study validation based on the notoriously hard problem of predicting er status in breast cancer; and iii) a clinically relevant application to predicting germline brca mutations in breast cancer, including extensive bioinformatic analysis to provide biological interpretation for the proposed predictor.  the performance of the tsp algorithm has been previously validated in. this section is organized as follows. first, general validation results are presented which demonstrate the advantages of bringing in a third gene for a variety of well-known studies in molecular cancer diagnosis and subtype identification from microarray data. next, we focus on interpreting the decision rules in terms of the different biological roles played by the three participating genes. the main application – detecting brca mutations – is then presented. our three-gene classifier achieves an overall accuracy of 94% in cross-validation on the combined van't veer and hedenfalk datasets, which well exceeds the performance of several well-known methods. finally, we present a cross-study validation of our methodology in the context of another important classification problem in breast cancer – predicting er status. general validation in table we compare the classification accuracy of two-gene and three-gene versions of rxa for nine cancer datasets summarized in table the three-gene version is tst, which restricts all three genes to the ten most differentially expressed; see methods. in order to ensure a fair comparison, we restricted the two genes in tsp to be among the sixteen most differentially expressed. since the number of ways to select three genes from ten, namely is the same as the number of ways to select two genes from among sixteen, the total number of candidate classifiers is identical. the classification rates are estimated by leave-one-out cross validation. in both cases, the genes are restricted to a subset of differentially expressed genes based on a wilcoxon rank test; the details appear in § and §. the subsets are selected to ensure that the number of possible two-gene and three-gene classifiers are the same. score permutation tests for tst for six of the nine datasets are depicted in figure for each dataset, we randomly permuted the class labels times and computed the score s, the average of sensitivity and specificity, for the top-scoring triplet. artificial data created in this way preserves both the sample sizes and the overall dependency structure among the genes. shown is the histogram of scores with the score of the real dataset marked by a red cross. as can be seen, all six scores are highly significant with p-values of zero. the probability tables for these same six datasets are given in table and the names of the genes in the top-scoring triple are listed in table for example, from table we see that, for the colon study, the preferred ordering among normal samples is xj <xi <xk, and xk is never the least expressed among these samples; as seen in table gi, gj, gk, represent vip, dars, fcgr3a. similarly, in the lung data, among the mpm samples, gene gj is always the least expressed, but never so among the cancer samples. each portion of the corresponds to one study with two phenotypes. for each study and each phenotype, the table shows the relative frequencies of the six possible orderings among the expression values of the top-scoring triple for the samples in the study. the gene triple for each study is given in table 4 the three genes in the top-scoring triplet for each of the six studies. the histograms of scores for the top-scoring triple classifier for the other three datasets are given in figure as can be seen, the top scores for prostate and prostate are still significant, although less so than for the six studies in figure whereas the top score for the cns dataset is at best borderline significant. this may not be surprising in view of the very small number of samples for the minority class in both prostate and cns. over-fitting is very difficult to avoid with only nine samples for one of the classes; see table biological roles for the tsp algorithm, there are two prototypical situations: either both gi and gj are differentially expressed in opposite directions or only gi is differentially expressed and gj serves as a "pivot" or "reference" for gi, in effect a random threshold; see methods. call these two cases and. a biological mechanism leading to the case may occur when the two genes are involved in competing processes, e.g., one gene may be an oncogene and the other a tumor suppressor gene. the case was illustrated in figure for separating malignant pleural mesothelioma and adenocarcinomas: rock serves as a pivot for kir2dl which is up-regulated in mpm samples. the expression of rock is relatively stable across the two phenotypes. the role of "pivot genes" is elaborated in the discussion section. several typical cases emerge for three genes. one is, meaning that all three genes in the top-scoring triplet are differentially expressed. this is illustrated for the lung study in the left panel of figure where the gene triplet is the one selected by the tst algorithm. another case is, signifying that two of the three genes are differentially expressed and the third is not, serving instead as a reference for the other two. this is illustrated in the right panel of figure 5; the gene triplet comes from tst, in which one of the three genes is unrestricted. this is also what emerges for the top-scoring triplet in the brca study; see again the treatment of pivot genes in the discussion section identifying brca1-related breast cancer we now consider the identification of breast tumors that arose as the result of an inherited deleterious mutation of the brca gene. brca is a tumor suppressor gene whose altered function is associated with breast, ovarian and other cancers. deleterious germline mutations of brca have been estimated to occur in in ashkenazi jews and in non-ashkenazi and are responsible for a significant fraction of inherited breast cancer cases. genetic testing for germline mutations is available commercially. testing is expensive and, despite significant recent improvements, still incomplete in its sensitivity. for women newly diagnosed with breast cancer, and a family history of the disease, knowledge of whether they harbor germline mutations is of help in guiding decisions about prevention of contralateral breast cancer and ovarian cancer. prevention options include radical surgery. therefore, the availability of inexpensive expression markers for brca mutations based on tumor samples would significantly improve the clinical management of these women, and contribute to more efficient prevention within their families. we apply the tst algorithm to predict brca mutant status, using two breast cancer gene expression microarray data sets available from the public domain. the raw data can be downloaded from the supporting websites of the two published manuscripts. the two studies, designated van't veer and hedenfalk, are generated from two different platforms. after data preprocessing and cross-platform matching, we obtain a combined dataset with features and samples. the two classes are brca1-mutant cancers and non-brca cancers, with sample sizes and respectively. for the tst algorithm, the score for the top-scoring triplet is. the estimated gene expression ordering probabilities for the genes in this triplet are shown in table since there are about × ≈ triplets having at least two differentially expressed genes, a high score might happen by chance. however, a permutation test demonstrates that the p-value of score of the top-scoring triplet is virtually zero; see figure estimated probabilities for the six possible orderings among the three genes in the top-scoring triplets for each of the two classes. here, x x and x refer to the expression values of ppp1cb, tmem and rnf respectively. mutant samples are characterized by a single preferred ordering whereas non-mutant samples display all orderings. performance we compare the performance of the tst algorithm with tsp and four well-known machine learning methods: naive bayes, k-nearest neighbor, support vector machine, and random forest. we use the weka machine learning package which contains all but tsp and tst, as well as several r packages. for tsp and tst we have developed an r package for relative expression analysis which incorporates all the versions of tsp and tst used in this paper and which is available for download at. for nb, k-nn, svm and rf, in order to optimize performance, we report the best results we obtained by taking either the weka default parameters or systematically exploring the parameter spaces, estimating generalization errors with cross-validation. in the case of svms, this included trying a wide range of combinations for the scale and penalty parameters with the rbf kernel. table summarizes the results of loocv. as seen, tst has the best overall classification accuracy and the best sensitivity. equally noteworthy, tst involves only three genes whereas the four traditional machine learning methods use many more. estimates are based on leave-one-out cross-validation and accuracy is defined as the average of sensitivity, the percentage of correctly classified brca samples, and specificity, the percentage of correctly classified nonbrca samples. the top-scoring gene triplet is. table gives the empirical probability distribution over the six possible orderings of expression values for each of the two phenotypes. interestingly, the expression values of this triplet are in the same order for all brca1-mutant samples; for nonbrca1-mutant samples, the probability distribution is dispersed, almost uniform. in our study there are nonbrca1-mutant samples which exhibit the relation rnf <tmem <ppp1cb, of which are "basal-like" tumors, a subtype of breast cancer associated with lack of expression of the estrogen receptor and poor prognosis. interestingly a strong association between the "basal-like" subtype and brca mutation has been suggested in a number of molecular and pathological studies. the top panel in figure shows the expression pattern of the top-scoring triplet. we can see that ppp1cb is up-regulated in brca samples, rnf is down-regulated in brca samples, while tmem is rather stable across the two phenotypes. both ppp1cb and rnf are highly differentially expressed, actually among the top three, with p-values of e - and e - respectively. the benefit of the reference gene tmem is displayed in the bottom panel of figure the decision boundary of the two-gene tsp classifier based on ppp1cb and rnf is the line y = -x: the upper right area corresponds to ppp1cb > rnf and the lower left area corresponds to rnf > ppp1cb. incorporating tmem into the decision narrows the upper right "mutant" region to the indicated rectangle where rnf <tmem <ppp1cb. the samples in the two triangular areas would be misclassified based on the expression ordering of the gene pair ppp1cb and rnf alone whereas they are correctly classified by the tst algorithm. cross-study validation for er status estrogen receptor has been studied in clinical breast cancer for more than years. approximately two-thirds of all breast cancers are er+ at the time of diagnosis. the expression of er has important implications for breast cancer diagnosis and treatment. in particular, er status correlates well with response to hormonal therapy: er+ patients are much more likely to benefit from such therapy. research shows that er+ and er- tumors display remarkably different gene-expression patterns. here we use the tst method to classify tumors according to their er status. three breast cancer microarray data sets are included in this study and they are denoted as miller, sotiriou and expobreast. the raw data of miller and sotiriou can be downloaded from gene expression omnibus or supporting web sites, and expobreast can be downloaded from. miller and sotiriou are generated from the affymetrix hgu133a microarray platform and expobreast are generated from hgu133plus mas was used to pre-process the raw data to get probe sets level data. in order to match the two microarray platforms, we only keep those probe sets that are present on both. there is an 88-patient overlap between miller and sotiriou, so we exclude the replicate patients from the original sotiriou. the sample sizes and the phenotype information are shown in table two types of cross-study validation were performed, each involving learning three classifiers. in the first, there is one classifier for each of the three ways of integrating two of the three microarray data sets to obtain a training set and then using the third one for testing. in the second case, each classifier is trained on only one dataset and tested on the data obtained by merging the other two. we restrict our search to genes on five breast cancer related pathways. there are such genes present on the microarray, which correspond to probe sets. information about the five pathways and the probe sets can be obtained from the additional files and top: classification results when training on the data set obtained by integrating two of the three microarray data sets and testing on the third one. bottom: classification results when training on one of the three microarray data sets and testing on the data set obtained by integrating the other two. the numbers in the parentheses are the sensitivity and specificity levels respectively. discussion function and interactors of tst genes in addition to the role of brca mutations in familial breast cancer, the reduced expression, or incorrect sub-cellular localization of brca protein, are postulated to be important also in the pathogenesis of sporadic breast cancer. evaluation of brca protein expression in breast cancer cases has shown that about 50% of the tumors showed loss of nuclear expression or cytoplasmic localization of the protein. the evidence of biological roles of brca reveals multiple functions for this protein, that may contribute to its tumor suppressor activity, including regulation of cell cycle progression, dna repair, dna damage-responsive cell cycle check-points, apoptosis, and the regulation of a set of specific transcriptional pathways like the androgen receptor's and esr. the top scoring triplet identified in our brca analysis involves ppp1cb, tmem and rnf the ppp1cb gene is located on chromosomal cytoband 2p and encodes one of the three catalytic sub-units of the phosphatase- serine/threonine-specific protein phosphatases. this multimeric complex is involved in protein dephosphorylation within a variety of cellular processes, including cell division, muscle contractility, glycogen metabolism, protein synthesis, and hiv- viral transcription. the rnf gene, also known as ara is located on chromosomal cytoband 5q -q and encodes for a protein involved in the modulation, by direct protein-protein interaction, of a number of hormone nuclear receptors, including the androgen receptor, the estrogen receptor, and the growth hormone receptor. brca has been shown to directly interact with the andogen receptor, increasing androgen-dependant transcription. this supports our observation that the ar cofactor, rnf has very low expression in those samples in which brca function is impaired. finally, the tmem gene, located on chromosomal band 1p, encodes for a protein developmentally regulated in the brain, with predominant expression in differentiating neurons. the biological role of this protein is not yet known. since a recent study by winter and colleagues showed that all three isoforms of pp including ppp1cb, interact with brca we used protein-protein interaction data to understand whether the triplet genes directly interact with each other and with brca in addition to the interactions described by winter and colleagues, ppi interaction gene lists included information from three sources: the human protein reference databases, biogrid and the biomolecular interaction network database. all protein-protein interactions reported in any of these databases to involve the triplet genes were used, regardless of the techniques employed to identify the interaction, or the type of evidence supporting its inclusion in the databases. we represented ppi data as adjacency matrices and displayed the corresponding networks using undirected graphs, where each node represents a protein while edges represent interactions. no ppi interactions were reported for the pivot gene tmem while the other two genes were found to interact with several other proteins. although none of such inter-actors is in common between the two proteins, the ppi network revealed a number of shortest paths connecting these two proteins and involving a minimum of two proteins. one such path accounts for brca and ar, while the other involves esr sm arcb, nr3c, and nucleolin. overall, this analysis suggests that rn f and ppp1cb are part of a regulatory network modulating gene expression and involving brca and a number of hormone nuclear receptors. pivot genes as has been seen, one very interesting scenario that often arises in the application of tsp and especially in the application of tst, is that one of the genes appears to play a passive role, serving as a pivot point or benchmark expression level for the others. this situation is illustrated well in figure where the key biological signal of cancer is that at least one of the pathway-activator genes is expressed above the level of the pivot gene. it is difficult to assign roles to the genes in a triplet observed in experimental data with any certainty, but expression patterns consistent with the pivot gene theory have been observed very frequently in a wide variety of experiments and we think it important to consider the implications of this when developing and evaluating methodology. in finding triplets in practice of the methods section, we present practical methods for reducing the triplet search space by recognizing such a division of labor among the genes in a triplet and pre-filtering for genes that, say, could serve as a pivot. in this section we discuss additional biological and technical consequences of the pivot gene theory. there are technical issues associated with expression microarrays that make it difficult to find a good pivot gene in practice. the intensity level of a microarray probe depends on a variety of technical variables in addition to the biological variable of interest, transcript abundance, and so the measured intensity for gene a may exceed that of gene b even when b is present in greater quantity. in single color microarrays, these probe effects can overwhelm sample to sample differences in gene expression, driving correlations in excess of 95% when expression data obtained from very different samples, but measured on the same array platform are compared. this works two ways: the availability of a large number of probes with relatively constant intensities at various levels should make it quite easy to find efficient pivots when working on a single platform, while on the other hand, the selected pivot gene may not sit at the same level relative to its partners in the triplet when measured by another technology. two color arrays offer additional technical challenges and introduce study design issues as well. classical house-keeping genes, expressed at near constant levels in all cells, should yield expression ratios of for any two samples and so may not work well as benchmark expression levels for other genes. the use of two different dyes for the two samples on an array introduces a technical effect that continues to slightly bias the estimated ratios of individual genes even though the broadest effects are well controlled by standard pre-processing methods. thus, as on single color arrays, pivot genes identified on a two-color platform may be effective only within that technology. an additional concern arising in two-color studies is the fact that both samples on an array contribute to the expression ratio. the reference samples included in one study may determine the level of a potential pivot gene or in extreme cases, even drive apparent differential expression that is in fact not present in the population of interest and which therefore will not be observed in another study with a different design. the successes of the rxa approach clearly demonstrate that these technical challenges can be overcome, and we believe that steps can be taken in implementation to minimize the threat to performance. careful preprocessing to minimize the influence of technical effects is a crucial step. principled pre-filtration of array features, as discussed in finding triplets in practice of the methods section, could help by eliminating a large number of apparently irrelevant and possibly misleading probes from consideration. we also recommend that the rxa classifiers be made as robust as possible by maximizing the diversity of samples and platforms included in the training set. biological findings in the present study we apply the tst algorithm to predict brca mutant status using data from the public domain. within the training set, our approach enables a correct classification of all brca mutants considered, while only sporadic breast cancers are misclassified. a number of factors may account for the brca1-like behavior of some of the wildtype tumors. for example, brca function may be altered by somatic mutation, methylation or other genetic alterations, or it may be impaired by incorrect cellular localization. the "basal-like" subtype of breast cancer is associated with lack of expression of the estrogen receptor and poor prognosis. a strong connection between the "basal-like" subtype and brca loss of function has been suggested in a number of molecular and pathological studies. among the sporadic breast cancer that were misclassified by tst, are "basal-like". since there are "basal-like" samples in total, the probability of seeing of them in randomly chosen samples is indeed small. therefore, the "basal-like" types are over-represented in the nonbrca1-mutant samples which are classified as brca1-mutant cancers by tst, arguing for the biological relevance of the top-scoring triplet. the analysis of the protein-protein interactions among the top-scoring triplet genes and brca further suggests that the classifier has a biological foundation. no interactors were found for tmem possibly reflecting its role in the classifier as the pivot gene, while the other two genes showed interactions with many other proteins involved in breast cancer biology including the brca protein itself. ppp1cb is one of the three catalytic sub-units of the protein phosphatase pp a study shows that all three isoforms of pp interact with brca. in the same study, rt-pcr expression analysis indicates that sporadic breast cancers have lower expression levels of ppp1cb than do normal tissues. the gene expression microarray data that we use show a higher expression level of ppp1cb in brca1-mutant cancers than in sporadic breast cancers. moreover, the literature also suggests that ppp1cb is a discriminator gene between brca1-mutant and brca2-mutant tumors for both breast and ovarian cancers. although no direct links exist between rnf and brca our ppi analysis shows that indirect interactions occur, and they involve important proteins in breast cancer biology, like the estrogen and androgen receptors. the expression of the estrogen receptor is a fundamental prognostic factor in breast cancer: hormonal therapy is used in adjuvant settings based on whether cancer cells express it or not. androgen receptor signaling is also emerging as a relevant pathway for breast cancer biology. unlike prostate cancer, where ar is sustaining growth of cancer cells, androgen signaling in breast cancer represents a restraint to cancer cell growth, and it has been shown that ar expression correlates with a better prognosis. interestingly, reduced or altered brca protein expression has been shown to be associated with lack of progesterone and esr and expression of the ar. from this perspective, it is important that ar activity is modulated by numerous factors, including rnf and brca. while elucidation of the exact mechanisms by which loss of brca function affects expression of ppp1cb and rnf awaits additional laboratory work, the evidence we presented strongly suggests that the tst classifier described here has properties that go beyond classification performance and that are capturing genuine biological mechanisms underlying breast cancer pathogenesis.  we have developed and validated a general rxa approach to building simple and interpretable classifiers using trios of features. other approaches have been advanced for selecting informative gene triplets and three-gene interactions from expression microarray data. recently, methods based on fuzzy logic, liquid association and a three-way interaction model have been proposed. in, activator-repressor-target triplets are identified using logical relationships among the genes. liquid association is aimed at capturing the dynamic association between a pair of genes; the correlation between the expression values of a gene pair depends on the expression level of a third gene. the three-way interaction model is similar, except the third gene plays the role of a qualitative switch rather than a continuous measure as in liquid association. however, none of these approaches involve inferring phenotype-specific models or classifiers, and none are rank-based. while statistical and machine learning techniques have contributed significantly to the interpretation of the large and complex data sets generated by high throughput genomic techniques, the direct application of these techniques in the clinical management of patients is slowed by challenges in interpretability and cross-study reproducibility. algorithms based on the relative level of a small number of genomic features provide a formidable simplification, yielding progress in both interpretability and reproducibility, often at little or no cost in terms of accuracy. this article demonstrates a new incarnation of this philosophy, based on three-gene classifiers, provides a general framework for understanding the roles of the genes involved, and illustrates its potential in the difficult and clinically relevant problem of identifying brca mutation carriers. 
achieving biologically relevant results argues for a different strategy. rxa has the potential to identify genomic "marker interactions" with plausible biological interpretation and direct clinical applicability. a promising alternative is to base prediction entirely upon the relative expression ordering of a small number of genes. we present a three-gene version of "relative expression analysis", a rigorous and systematic comparison with earlier approaches in a variety of cancer studies, a clinically relevant application to predicting germline brca mutations in breast cancer and a cross-study validation for predicting er status. it provides a general framework for understanding the roles of the genes involved in decision rules, as illustrated for the difficult and clinically relevant problem of identifying brca mutation carriers. however, an important obstacle to both biological understanding and clinical applications is the "black box" nature of the decision rules provided by most machine learning approaches, which usually involve many genes combined in a highly complex fashion. a major challenge in computational biology is to extract knowledge about the genetic nature of disease from high-throughput data. in the brca study, rxa yields high accuracy with a simple decision rule: in tumors carrying mutations, the expression of a "reference gene" falls between the expression of two differentially expressed genes, ppp1cb and rnf an analysis of the protein-protein interactions among the triplet of genes and brca suggests that the classifier has a biological foundation.
 a major challenge in computational biology is to extract knowledge about the genetic nature of disease from high-throughput data. however, an important obstacle to both biological understanding and clinical applications is the "black box" nature of the decision rules provided by most machine learning approaches, which usually involve many genes combined in a highly complex fashion. achieving biologically relevant results argues for a different strategy. a promising alternative is to base prediction entirely upon the relative expression ordering of a small number of genes.  we present a three-gene version of "relative expression analysis", a rigorous and systematic comparison with earlier approaches in a variety of cancer studies, a clinically relevant application to predicting germline brca mutations in breast cancer and a cross-study validation for predicting er status. in the brca study, rxa yields high accuracy with a simple decision rule: in tumors carrying mutations, the expression of a "reference gene" falls between the expression of two differentially expressed genes, ppp1cb and rnf an analysis of the protein-protein interactions among the triplet of genes and brca suggests that the classifier has a biological foundation.  rxa has the potential to identify genomic "marker interactions" with plausible biological interpretation and direct clinical applicability. it provides a general framework for understanding the roles of the genes involved in decision rules, as illustrated for the difficult and clinically relevant problem of identifying brca mutation carriers. 