access to automated dna sequencing technology has made possible the rapid generation and analysis of gene transcripts expressed in organisms via expressed sequence tags ( ests ) .
this information has helped to identify those genes expressed in particular stages of development and in specialized tissues or organs .
novel gene products and target leads for therapeutic intervention can also be gleaned rapidly from ests . a more detailed understanding of the molecular interactions between symbionts , whether pathogenic or mutualistic , is also possible with this approach . for a sequence isolated from interacting symbionts , determining its cellular role ( or roles )
we refer to this challenge as ' the problem ' : given a sequence x expressed in an interaction between species a and b , did x originate from a or b ?
various solutions are readily conceived , each with merits and faults . here , we show that a comparative lexical analysis of word counts ( specifically , hexamer frequencies ) , previously used to detect library contamination in sequencing projects , provides a powerful computational basis to infer a transcript 's species of origin . experimentally , one can attempt to solve the problem by hybridizing a clone ( as probe ) to genomic dna ( target ) from both species and determining to which target the probe hybridizes .
however , if a sequence is highly conserved in the two taxa , hybridization stringency conditions can influence the outcome considerably . for high - throughput est sequence analysis ,
source verification by hybridization is impractical in terms of time and reagents . as an alternative to in vitro hybridization , several computational solutions are possible .
were the genome sequence of both species completely determined , one could simply use sequence similarity searching . however , most plant hosts and their microbial symbionts have little or no genomic sequence data available , which makes this approach very unreliable .
strong similarity to a sequence from one organism does not preclude the possibility that a similar sequence is present in the other species .
exploiting this fact may seem a viable solution to the problem , as it has proven suitable for predicting the presence of introns among exons in genomic dna .
however , it really is not practical , because of the need to know the reading frame for translation of a messenger rna into an amino acid .
est data are of notoriously unreliable quality , sometimes having a large proportion of ambiguous bases , and sometimes having single base - pair insertions or deletions , which disrupt a reading frame .
word counting is less prone to these sources of error , and uses information intrinsic to biases in codon usage by counting codon pairs as hexamers in a sliding window , whereas codons are read in non - overlapping , tiled windows .
an intuitive approach to the problem that examines sequence composition is to compare the guanine and cytosine ( gc ) base content of a sequence with other sequences from the species being studied .
when two species ' genomes have different gc content , this method can be very useful .
in a recent investigation , for instance , sequences from the stramenopile plant pathogen phytophthora sojae and its soybean ( glycine max ) host showed a 20% difference in mean gc content . the origin of a number of sequences could readily be identified this way , but a large proportion could not , because of considerable overlap in the distributions ' tails .
counting frequencies of gc is simple word counting , where the word size k is 1/2 : only two semi - words , g / c and a / t are counted .
an alternative approach to determining the origin of a sequence is suggested by previous work on analysis of word counts , or k - tuple frequencies , which was intended as a means of evaluating a library for contamination when sequencing from a single model organism .
the word - counting method provides distinct advantages over other computational methods . unlike sequence - similarity searching
, it does not require that the full protein - coding content of both genomes be known for reasonable inferences to be made .
further , word counting is sensitive to biases in codon usage and gc content commonly observed when comparing taxa , but does not require knowledge of the reading frame for amino - acid translation .
that is , the underlying differences between the two organisms that result in base composition or codon usage biases can also be detected by counting words .
unlike gc analysis , lexical analysis establishes a clear threshold above or below which we can infer the species of origin , and a confidence level for an inference can readily be assigned .
dunning 's likelihood - ratio test of word dissimilarities   also has the appealing property of being non - parametric , having no assumption of normality for the underlying frequency distribution , which makes it statistically powerful . dunning   demonstrated that unreliable results can be obtained from parametric tests , such as  , particularly in such cases as lexical analysis . in the experiments detailed below , we first validate the word - counting method on sequences whose
origin and function are known , then compare it with ability to diagnose the origin of sequences with distributions of gc content .
we examine sequences from pathogenic interactions between species from the genus phytophthora and the plant hosts g. max and medicago truncatula , then apply the word - counting approach to sequences from two microbial mutualists in association with m. truncatula , the arbuscular mycorrhizal zygomycete glomus versiforme , and the nitrogen - fixing bacterium sinorhizobium meliloti .
validation sequence accession numbers , gene names , and comparison results appear in table 1 .
the word - counting method was generally quite reliable when tested against sequences of known origin , being wrong in 3 cases out of 50 ; a phosphate transporter from g. versiforme and two in planta - induced genes from phytophthora infestans were misidentified as plant sequences .
this indicates a failure rate of 6% - all false negatives under the null hypothesis that a transcript originates from the plant host .
performance of the method was not influenced by whether the isolated source of a sequence was an mrna or dna molecule , as indicated by the column labeled ' mrna ? ' .
distributions of gc content are approximately normal in two of three cases studied , those of axenic p. sojae cultures ( figure 1 ) . for sequences from infected plant cultures ,
roughly 25% of a total of 927 infected g. max sequences contain less than 50% gc ; most of these are likely to be plant transcripts .
this is a considerably greater number than for axenic p. sojae cultures , in which fewer than 5% of mycelia and zoospore isolates contain less than 50% gc .
several properties of cumulative distribution functions warrant comment , to help explain similar plots from word dissimilarity comparisons ( figures 1b,2a ) .
the median of a distribution occurs where the function reaches a cumulative probability of 0.5 .
medians from all three p. sojae libraries are similar , varying by less than 4% gc ( figure 1b ) .
other moments of the distributions are readily apparent ; the variance is inversely related to the slope at the median value of the function
. a useful property of cumulative distribution functions is that any point on the y axis gives the integrated area ( cumulative probability ) under the curve .
we use this property to establish experiment - wide false - positive and false - negative rates ( figure 2a ) . in this case ,
calibration curves from hexamer dissimilarity tests , shown in figure 2b as solid black lines for plant and dashed black lines for stramenopile training sequences are approximately normal .
the medians differ considerably , with only about 10% percent overlap in the two distributions ' tails about the neutral t - value of zero . superimposed
are comparison curves from p. sojae test sets ( figure 2b ) , which parallel the gc content curves in figure 1b but show slightly less variance .
axenic sequences are clearly more like stramenopiles ( b1 ) than plants ( a1 ) in hexamer composition , with all but a small percentage having positive t values .
plant - like sequences are as abundant in the mixed library as detected by gc content , about 23% . as expected , the two methods agree , having positively correlated values for gc and t ( r = 0.852 , p < 10 , v = 2,641 ) . looking in more detail at the paired dissimilarity values ( figure 3 ) ,
the magnitudes of dissimilarity are also apparent , with longer sequences having larger dissimilarity values .
blastx similarity searches against the protein sequences in nr , a non - redundant library of proteins   revealed that none of the 12 plant - like mycelial transcripts significantly resemble known proteins ( e > 10 ) . among the top ten most plant - like transcripts from the infected g. max library
, three had no significant matches , four matched putative arabidopsis thaliana proteins , and three matched known g. max proteins : cytochrome p450 ( accession af022460 , e < 10 ) , methylglyoxalase ( accession p46417 , e < 10 ) , and a ripening related protein ( accession af127110 , e < 10 ) .
thus , the majority of the most plant - like transcripts in the infected soybean library strongly resemble characterized plant sequences .
analysis results from all p. sojae and mixed - culture transcripts are available as additional data files , grouped by the library from which transcripts were sequenced .
figure 4 shows that calibration curves from comparing plant and microbial symbiont training sets have good separation and minimal overlap ( about 10% ) in two of three cases , but not for training set b2 , comprised of zygomycetes and chytridiomycetes , which overlaps considerably with plants ( figure 4b ) .
when comparing between plants and bacteria , the error rates are  = 0.052 and  = 0.084 , much lower than when comparing plants ( a2 , medicago ) with fungi ( b2 , zygomycetes and chytridiomycetes ) .
error rates for comparing stramenopiles and p. infestans ests with plants are as in figure 2 (  = 0.088 ,  = 0.032 ) . also shown in figure 4
all resemble calibration curves from plant sequences , having similar medians and slightly less variance than the plant calibration curves .
comparison curves show that the great majority of test sequences are more plant - like than otherwise , with 20% or less resembling microbial symbionts more closely than plants
. a greater proportion of microbial sequences is present in the m. truncatula - g .
versiforme interaction library ( 20% , figure 4b ) than in the p. medicaginis - infected m. truncatula library ( 5% , figure 4a ) .
however , long 's root - hair enriched library ( mtrhe )   had a greater proportion of putative microbial sequences present ( 7% and 25% ) than any of the libraries isolated from symbiont - associated cultures .
the axenic and nodulating root libraries had the smallest portion of putative microbial transcripts ( < 2% , figure 4c ) , with the axenic library closely resembling nodulating root libraries .
the method of preparing a library can affect the proportion of plant and non - plant sequences , as discussed below .
paired dissimilarity values in figure 5 show in greater detail which sequences are more or less like plant and symbiont .
considerable variation in the degree of dissimilarity to both training sets is clear , largely due to variation in the length of sequences within test sets .
d(b ) in figure 4 , most sequences lie above the identity function , and resemble the plant host more closely than the microbial symbiont .
mycorrhizal test sequences are more difficult to differentiate than sequences from the rhizobacterial or pathogenic associations , as seen by the diminished variation about the identity function in mycorrhizal comparisons ( figure 5b ) , contrasted with comparisons from pathogen - infected and nodulating root libraries ( figures 5a and c , respectively ) .
analysis results from all m. truncatula and mixed - culture transcripts are available as additional data files , grouped by the library from which transcripts were sequenced , and sorted from the least plant - like transcripts to the most plant - like .
clearly , the word - counting approach provides a reliable solution to the problem of source identification with known confidence , and has several significant advantages .
the reliability of the method is best justified in terms of the favorable validation test results , and is further corroborated by agreement with an analysis of gc content . in test cases
where the correct answer is known a priori , results were correct within error rates expected from overlap in training sets .
( recall that  = 0.088 for comparisons between plants and stramenopiles , and  = 0.052 for comparisons between plants and bacteria . ) unlike gc content , the problem is clearly resolved by word counting with a threshold value of t = 0 , and with statistical rigor , because false - positive and false - negative rates for a set of comparisons are readily computed from cumulative distributions of dissimilarity between two training sets .
optimal statistical power ( minimal false - negative rate ) is ensured when using a likelihood - ratio test statistic , as demonstrated by the pearson - neyman theorem .
rather , it is sufficient that the training set be related to , but not necessarily congeners of , the species from which sequences are being compared .
sequences from several species of the genus phytophthora were correctly distinguished from plant and bacterial sequences , and three genes from agrobacterium tumefaciens were correctly identified as representing a bacterial sequence .
however , several caveats warrant prudence . transcribed sequences that do not encode proteins , but rather catalytic single - stranded rnas such as transfer and ribosomal rnas , should be treated independently because they are more highly conserved across taxa than messenger rnas . also , filtering or trimming of low - complexity repeat regions , such as poly(a ) or poly(t ) tracts , is helpful because comparison results can be influenced by the abundance of a single hexamer .
early in our investigations , using one set of training sequences obtained from directionally cloned p.
it eventually became clear that , as the p. infestans sequences were all single - pass reads from the 5 ' end of a clone generated with the t3 primer , few sequences complementary to the 3 ' end of the mrna sequence were present in the training set .
large amounts of the poly(t ) hexamer would be expected when sequencing reverse complements of mrnas obtained from 3 ' sequences generated with the t7 primer .
as a result , any sequence that contained a poly(t ) tract tended to resemble the plant sequences .
further , because the error rates for an inference depend on the degree to which calibration curves overlap , the best results are obtained where overlap is minimal . despite these caveats , word counting presents a viable solution to the problem .
the p. sojae - infected g. max library provides a clear example of contrast in both hexamer composition and gc content , resulting in readily diagnosed origins .
for clear separation between the two species to appear , the two must differ in composition and a detectable proportion of transcripts from each species must be present in the library . to be detectable , the proportion of transcripts present from a particular species must be greater than the error rate obtained from calibration curves . though these criteria are true for the infected g. max library ( t < 0 for < 25% of 927 transcripts ) , they do not appear to be true for the m. truncatula libraries we analyzed ( t < 0 for 8099% of 8903,017 transcripts ) . in the p. medicaginis interaction library
the p. sojae - infected library was prepared two days after infection , using a susceptible plant host strain , so as to maximize the number of pathogen transcripts present in the host tissue .
medicaginis - infected library was prepared ten days after infection and individual plants varied in their degree of susceptibility ( c. vance , unpublished data ) .
plants were also inoculated in a different manner : ground mycelia were dissolved in sterile water and incubated , and the resulting inoculum was pipetted onto the soil surface , rather than the plant .
these differences in how tissues were cultured prior to library preparation could have produced the disparate abundance of plant transcripts , though both libraries were prepared from plant tissues infected with phytophthora . for mycorrhizal root libraries
, we might explain the relative lack of symbiont sequences as resulting simply from a relative lack of transcripts in the host tissue .
we might therefore expect that most of the transcripts therein originate from the plant host . confounding this result ,
the error rates in this comparison are the greatest among all the comparisons we performed , most likely because the evolutionary distance between fungi ( zygomycetes and chytridiomycetes ) and plants is the least among comparisons . also , zygomycete protein - coding sequences are rare in genbank , which resulted in a small training set for these fungi , and may have amplified any biases .
the high false - negative rate probably led to a failure to detect some symbiont transcripts . in nodulating root libraries
, we do not expect to observe an abundance of bacterial transcripts , because bacteria generally do not form polyadenylated mrnas . as the protocols used to extract and purify mrnas from tissue lysate for the libraries cited in this study all relied on the presence of polyadenylation sites
the abundance of putative microbial symbiont transcripts among sequences from a pure plant root library is difficult to interpret .
the predicted portion of microbial transcripts was greater in the axenic root - hair enriched library than in mixed cultures .
error rates were greatest for comparisons between training sets from plant and pooled zygomycete and chytridiomycete sequences .
the 13% false - positive rate does not completely explain why about 15% of root - hair enriched transcripts resemble fungal hexamer composition more closely than plants , and warrants further study .
care had been taken to avoid contaminating plant tissue cultures by culturing seedlings in covered plates .
because of concern that ethylene accumulation in covered plates could improperly stimulate nodulation - related gene expression , seedlings were treated with ag2so4 , an inhibitor of the plants ' response to ethylene .
inhibition of the ethylene response could have resulted in synthesis of transcripts that are uncharacteristic of plant roots .
analysis of another axenic root - hair enriched library , particularly one provided a carbon source to identify potential contaminants , and not treated with an inhibitor of ethylene response , would be an informative test .
the transcripts identified as most and least like plant or symbiont might also be studied in more detail as candidate participants in symbiosis .
symbiotic interactions , whether pathogenic or mutualistic , present novel challenges to both plant hosts and the biologists who study them . computational approaches , in concert with experimental verification , can help resolve these challenges .
to characterize hexamer frequencies in plant hosts and their microbial symbionts , we collected sets of training sequences from public databases and edited them for quality .
training sets were chosen to be representative of , but obtained independently from , taxa participating in symbiotic associations for which a diagnosis of origin would be made . because the species being compared are represented unevenly in public sequence databases , taxa were chosen so that roughly the same number of genes were analyzed in each training set , rather than simply to maximize the numbers of species or sequences present .
training sets represent protein - coding sequences from three taxonomic groupings : plants ( a1 , medicago and glycine spp . ) , either fungi ( b2 , zygomycetes and chytridiomycetes ) or stramenopiles ( b1 ) , including ests from p. infestans , and bacteria ( b3 , rhizobium , sinorhizobium and bradyrhizobium ) .
we performed pairwise comparisons with two different , taxon - specific training sets ( a and b ) to infer the origin of a transcript .
training sets were obtained by querying the genbank database using the entrez retrieval tool . a preliminary query by taxon name obtained all available nucleotide sequences from that taxon , then the limits option excluded ests , stss ( sequence - tagged sites ) , gsss ( genome survey sequences ) , working draft sequences , and patented sequences from the query set . organellar ( mitochondrial and chloroplast ) dna was also excluded via the limits option .
a query term to require that a sequence contain a protein - coding region ( cds ) was also added , which excluded ribosomal and transfer rna sequences .
the results consisted of all sequences that contain a nuclear protein - coding sequence available for that taxon at the time of the query .
( changing slightly the composition of training sets between those dates did not notably affect the experimental outcome . ) following a previously established protocol , we used a resampling procedure to evaluate the degree of overlap between distributions of hexamer composition obtained from comparing two training sets . in this protocol
, we resampled each training set 40 times by random partitioning into training ( for hexamer counts ) and test calculation pools . to control for any bias introduced by length variation ,
a program randomly clipped 300 nucleotide fragments for word counting . as a result , one random 300 nucleotide fragment from each training sequence was present in the training set during a single resampling replicate ; independent replicates contained different , randomly chosen training sequences and 300 nucleotide fragments .
values of the test statistic from 40 resampled replicates were pooled for calibration purposes . as with the original protocol , we pooled the resulting test statistic distributions , normalized them as cumulative distributions , and then evaluated them for overlap .
we call the resulting comparisons ' calibration curves ' , as they are not used directly to make inferences , but rather indirectly , to evaluate the degree of separation in hexamer counts from different taxa
. overlap of calibration curves should be minimal to yield the most statistically powerful results possible .
due to considerable overlap of calibration curves between taxonomically general , inclusive training sets ( that is , all eudicots , all fungi and miscellaneous eukaryotes , and all eubacteria , data not shown ) , we opted to work with specific training sets that included only the most species - specific sequences available , while maintaining approximately equal sample sizes across taxa .
the most challenging case was that of the arbuscular mycorrhizal fungi , for which very few protein - coding sequences are available . to increase the amount of data in this training set ( b2 ) without biasing sample sizes , we pooled sequences from all species in the zygomycetes with all available chytridiomycete coding sequences , and compared this training set with a set from a single plant genus , medicago ( a2 ) .
we chose this option , rather than including an arbitrary subset of sequences from the ascomycetes and basidiomycetes , because zygomycetes and chytridiomycetes have diverged from their common ancestor less recently than the ascomycetes and basidiomycetes , based on 18s ribosomal rna sequence data .
that is , the ascomycetes and basidiomycetes are more highly derived from the common fungal ancestor than zygomycetes and chytridiomycetes , which resemble more closely the ancestral state in modern lineages . starting with a full set of sequences , we filtered for high - quality sequences by trimming regions having extensive ambiguous bases ( n - rich ) and poly(a ) or poly(t ) regions .
thus , we trimmed poly(a ) and poly(t ) sites to minimize the cases in which a test sequence resembles one training set more closely than the other , simply by virtue of having an abundance of the hexamer aaaaaa or tttttt .
similarly , test results obtained from short or n - rich sequences can be difficult to interpret .
we allowed no more than one n per hexamer and trimmed poly(a ) or poly(t ) tracts longer than 13 nucleotides . to accommodate for possible sequence chimeras ,
those sequences found to contain an internal poly(a ) or poly(t ) segment longer than 13 nucleotides were partitioned into two fragments , and the longer of the two fragments was used in analysis , provided its length was at least 300 nucleotides . after trimming ,
we screened all remaining sequences of 300 nt or longer for similarity to escherichia coli using blastn .
all blast searches used default parameters and low - complexity filtering with the programs dust or seg .
the decision to exclude non - coding rna sequences from training sets was informed by the appearance of bimodal distributions of hexamer frequencies and a large degree of overlap between calibration curves ( data not shown ) , likely a result of divergent evolutionary rates between protein - coding and non - coding sequences .
chloroplast and mitochondrial sequences were eliminated to avoid complications due to variation in codon usage between nuclear and organellar genomes .
table 2 summarizes counts of sequences and nucleotides in training sets before and after trimming and screening .
to test the validity of word counting as a solution to the problem , we identified a set of 50 gene sequences from plants ( m. truncatula and g. max ) , oomycetes ( phytophthora ) , zygomycetes ( glomus versiforme ) , and bacteria ( sinorhizobium meliloti and agrobacterium tumefaciens ) , for which the function and origin have been characterized experimentally .
we chose genes known to play a role in plant - microbe interactions , as well as genes that are found across taxa .
we withheld these sequences , and partial transcripts of the same genes , from training sets prior to comparative lexical analysis , and calculated hexamer dissimilarities for each of the three training sets as described below . to diagnose the species of origin for sequences expressed in symbiotic cultures , we collected sequences generated by distinct est sequencing projects from the genbank database .
sequences from pathogenic interactions originated from cultures of a species from the genus phytophthora with its plant host , such as p. sojae and soybean ( g. max ) isolated from inoculated hypocotyls two days after infection   and p. medicaginis and m. truncatula isolated from infected roots 10 days after infection ( c. vance , unpublished data ) .
sequences expressed during mutualistic interactions were obtained from cultures with m. truncatula and mycorrhizal ( glomus versiforme ; m.j .
harrison , unpublished data ) or rhizobacterial ( s. meliloti ; k. vandenbosch , unpublished data ) endosymbionts several days after inoculation .
sequences expressed in pure , axenic cultures from p. sojae mycelia and zoospores   and from sterile , uninoculated m. truncatula roots   provided a basis for comparison in which no foreign transcripts were expected . to maximize the reliability of diagnostic comparisons , we screened test sequences for high quality as for training sequences , and for low similarity to e. coli , chloroplast and mitochondrial genes , and non - coding rna transcripts ( ribosomal and transfer rnas ) .
independent blastn comparisons identified sequences having very high similarity ( e < 10 ) to vector sequences or moderately high similarity ( e < 10 ) to non - nuclear or non - coding sequences obtained from genbank .
we wrote a perl program ( countgc.pl ) that calculates the gc base content of a sequence as the portion of guanine and cytosine residues among all unambiguous ( non - n ) nucleotides in a sequence . the hist method in r ,
version 1.1.1   aggregated continuous percentages into discrete histogram bins , using bin sizes of 2% difference in gc , with inclusive lower bin boundaries and exclusive upper bounds ; the lm method tested for linear correlation of the dissimilarity test statistic t with gc .
used a likelihood - ratio test to determine whether word frequencies from a particular sequence more closely resemble the frequency distribution of control data sets from the taxon being sequenced or a distantly related outgroup .
they computed a test statistic t(a , b , x ) for each sequence x as the difference of log - likelihood ratio dissimilarity measures , d(a , x ) = -2log(a , x ) , for two data sets , a control set a and an outgroup b , such that t(a , b , x ) = d(a , x ) - d(b , x ) .
a negative value for t indicates that the sequence more closely resembles words from a ; conversely , a positive value indicates a likely contaminant related to b. ( dissimilarity is conceptually related to distance . however , dissimilarity does not measure distance because it does not possess the mathematical properties of a distance metric . ) unlike the calculation of calibration curves , in which 300-nucleotide subsequences are randomly resampled , hexamer dissimilarity is measured over the whole length of a test sequence when inferring a transcript 's origin .
originally , the investigators used the null hypothesis that no difference exists for dissimilarity measures between the two data sets , or that t(a , b , x ) = 0 .
tested two alternative hypotheses : that t < 0 , being more like a , or t > 0 , like b. lexical analysis using pentamers or heptamers yields similar error rates and very highly correlated values for the test result ( not shown ) . because white et al .  
reported the best results were obtained using hexamers , and because a word size of six nucleotides corresponds to the size of a dicodon , we chose to analyze hexamer frequencies . to use longer words
requires more training data , because the number of possible words increases exponentially with increasing word size .
use of shorter words may be adequate for some applications and will be investigated in future work . though we used white 's word - counting methods , we did make slight modifications .
we simplified one program ( called hybridize ) to compute individual dissimilarity values , rather than paired differences ; a patch that details how to modify the c program is available ( see hyb2dis.txt in additional data files ) .
more importantly , we amended the null hypothesis and interpreted calibration curves to test for statistically significant dissimilarity differences . though the likelihood - ratio test statistic indicates the magnitude of similarity to a or b , we do not know what values for t are significant with known confidence .
when testing hypotheses , one can make two types of error : type i , or false positives , and type ii , false negatives .
the false - positive rate is denoted  and false - negative rate . we determine  and  from overlap in the calibration curves . inferring error rates from calibration curves
is justified because we know the correct answer and determine the error rate via resampling , as with bootstrap methods to infer error rates or confidence intervals .
we are interested in knowing from which of two organisms a sequence originated , and are reasonably confident that it came from either one or the other .
thus , we assume it came from one and test whether we have evidence to refute this assumption .
the null hypothesis here is that sequence x is from a. alternatively , it might be from b. evaluating the calibration curve overlap at t = 0 quantifies the associated error rates .
the cumulative distribution function ( cdf ) of taxon b specifies  where cdfb intersects 0 ; the cdf from a specifies  as 1-cdfa(0 )
. we can thus resolve the problem with known confidence p : p ( t > 0 ) = . all other computations were performed as described previously .
software used for lexical analysis was obtained via anonymous ftp from the tigr software ftp site .
to characterize hexamer frequencies in plant hosts and their microbial symbionts , we collected sets of training sequences from public databases and edited them for quality .
training sets were chosen to be representative of , but obtained independently from , taxa participating in symbiotic associations for which a diagnosis of origin would be made . because the species being compared are represented unevenly in public sequence databases , taxa were chosen so that roughly the same number of genes were analyzed in each training set , rather than simply to maximize the numbers of species or sequences present .
training sets represent protein - coding sequences from three taxonomic groupings : plants ( a1 , medicago and glycine spp . ) , either fungi ( b2 , zygomycetes and chytridiomycetes ) or stramenopiles ( b1 ) , including ests from p. infestans , and bacteria ( b3 , rhizobium , sinorhizobium and bradyrhizobium ) .
we performed pairwise comparisons with two different , taxon - specific training sets ( a and b ) to infer the origin of a transcript .
training sets were obtained by querying the genbank database using the entrez retrieval tool . a preliminary query by taxon name obtained all available nucleotide sequences from that taxon , then the limits option excluded ests , stss ( sequence - tagged sites ) , gsss ( genome survey sequences ) , working draft sequences , and patented sequences from the query set . organellar ( mitochondrial and chloroplast ) dna was also excluded via the limits option .
a query term to require that a sequence contain a protein - coding region ( cds ) was also added , which excluded ribosomal and transfer rna sequences .
the results consisted of all sequences that contain a nuclear protein - coding sequence available for that taxon at the time of the query .
( changing slightly the composition of training sets between those dates did not notably affect the experimental outcome . ) following a previously established protocol , we used a resampling procedure to evaluate the degree of overlap between distributions of hexamer composition obtained from comparing two training sets . in this protocol
, we resampled each training set 40 times by random partitioning into training ( for hexamer counts ) and test calculation pools . to control for any bias introduced by length variation ,
a program randomly clipped 300 nucleotide fragments for word counting . as a result , one random 300 nucleotide fragment from each training sequence was present in the training set during a single resampling replicate ; independent replicates contained different , randomly chosen training sequences and 300 nucleotide fragments .
values of the test statistic from 40 resampled replicates were pooled for calibration purposes . as with the original protocol , we pooled the resulting test statistic distributions , normalized them as cumulative distributions , and then evaluated them for overlap .
we call the resulting comparisons ' calibration curves ' , as they are not used directly to make inferences , but rather indirectly , to evaluate the degree of separation in hexamer counts from different taxa
. overlap of calibration curves should be minimal to yield the most statistically powerful results possible .
due to considerable overlap of calibration curves between taxonomically general , inclusive training sets ( that is , all eudicots , all fungi and miscellaneous eukaryotes , and all eubacteria , data not shown ) , we opted to work with specific training sets that included only the most species - specific sequences available , while maintaining approximately equal sample sizes across taxa .
the most challenging case was that of the arbuscular mycorrhizal fungi , for which very few protein - coding sequences are available . to increase the amount of data in this training set ( b2 ) without biasing sample sizes , we pooled sequences from all species in the zygomycetes with all available chytridiomycete coding sequences , and compared this training set with a set from a single plant genus , medicago ( a2 ) .
we chose this option , rather than including an arbitrary subset of sequences from the ascomycetes and basidiomycetes , because zygomycetes and chytridiomycetes have diverged from their common ancestor less recently than the ascomycetes and basidiomycetes , based on 18s ribosomal rna sequence data .
that is , the ascomycetes and basidiomycetes are more highly derived from the common fungal ancestor than zygomycetes and chytridiomycetes , which resemble more closely the ancestral state in modern lineages . starting with a full set of sequences , we filtered for high - quality sequences by trimming regions having extensive ambiguous bases ( n - rich ) and poly(a ) or poly(t ) regions .
thus , we trimmed poly(a ) and poly(t ) sites to minimize the cases in which a test sequence resembles one training set more closely than the other , simply by virtue of having an abundance of the hexamer aaaaaa or tttttt .
similarly , test results obtained from short or n - rich sequences can be difficult to interpret .
we allowed no more than one n per hexamer and trimmed poly(a ) or poly(t ) tracts longer than 13 nucleotides . to accommodate for possible sequence chimeras ,
those sequences found to contain an internal poly(a ) or poly(t ) segment longer than 13 nucleotides were partitioned into two fragments , and the longer of the two fragments was used in analysis , provided its length was at least 300 nucleotides . after trimming ,
we screened all remaining sequences of 300 nt or longer for similarity to escherichia coli using blastn .
all blast searches used default parameters and low - complexity filtering with the programs dust or seg .
the decision to exclude non - coding rna sequences from training sets was informed by the appearance of bimodal distributions of hexamer frequencies and a large degree of overlap between calibration curves ( data not shown ) , likely a result of divergent evolutionary rates between protein - coding and non - coding sequences .
chloroplast and mitochondrial sequences were eliminated to avoid complications due to variation in codon usage between nuclear and organellar genomes .
table 2 summarizes counts of sequences and nucleotides in training sets before and after trimming and screening .
to test the validity of word counting as a solution to the problem , we identified a set of 50 gene sequences from plants ( m. truncatula and g. max ) , oomycetes ( phytophthora ) , zygomycetes ( glomus versiforme ) , and bacteria ( sinorhizobium meliloti and agrobacterium tumefaciens ) , for which the function and origin have been characterized experimentally .
we chose genes known to play a role in plant - microbe interactions , as well as genes that are found across taxa .
we withheld these sequences , and partial transcripts of the same genes , from training sets prior to comparative lexical analysis , and calculated hexamer dissimilarities for each of the three training sets as described below .
to characterize hexamer frequencies in plant hosts and their microbial symbionts , we collected sets of training sequences from public databases and edited them for quality .
training sets were chosen to be representative of , but obtained independently from , taxa participating in symbiotic associations for which a diagnosis of origin would be made . because the species being compared are represented unevenly in public sequence databases , taxa were chosen so that roughly the same number of genes were analyzed in each training set , rather than simply to maximize the numbers of species or sequences present .
training sets represent protein - coding sequences from three taxonomic groupings : plants ( a1 , medicago and glycine spp . ) , either fungi ( b2 , zygomycetes and chytridiomycetes ) or stramenopiles ( b1 ) , including ests from p. infestans , and bacteria ( b3 , rhizobium , sinorhizobium and bradyrhizobium ) .
we performed pairwise comparisons with two different , taxon - specific training sets ( a and b ) to infer the origin of a transcript .
training sets were obtained by querying the genbank database using the entrez retrieval tool . a preliminary query by taxon name obtained all available nucleotide sequences from that taxon , then the limits option excluded ests , stss ( sequence - tagged sites ) , gsss ( genome survey sequences ) , working draft sequences , and patented sequences from the query set . organellar ( mitochondrial and chloroplast ) dna was also excluded via the limits option .
a query term to require that a sequence contain a protein - coding region ( cds ) was also added , which excluded ribosomal and transfer rna sequences .
the results consisted of all sequences that contain a nuclear protein - coding sequence available for that taxon at the time of the query .
( changing slightly the composition of training sets between those dates did not notably affect the experimental outcome . ) following a previously established protocol , we used a resampling procedure to evaluate the degree of overlap between distributions of hexamer composition obtained from comparing two training sets . in this protocol
, we resampled each training set 40 times by random partitioning into training ( for hexamer counts ) and test calculation pools . to control for any bias introduced by length variation ,
a program randomly clipped 300 nucleotide fragments for word counting . as a result , one random 300 nucleotide fragment from each training sequence was present in the training set during a single resampling replicate ; independent replicates contained different , randomly chosen training sequences and 300 nucleotide fragments .
values of the test statistic from 40 resampled replicates were pooled for calibration purposes . as with the original protocol , we pooled the resulting test statistic distributions , normalized them as cumulative distributions , and then evaluated them for overlap .
we call the resulting comparisons ' calibration curves ' , as they are not used directly to make inferences , but rather indirectly , to evaluate the degree of separation in hexamer counts from different taxa
. overlap of calibration curves should be minimal to yield the most statistically powerful results possible .
due to considerable overlap of calibration curves between taxonomically general , inclusive training sets ( that is , all eudicots , all fungi and miscellaneous eukaryotes , and all eubacteria , data not shown ) , we opted to work with specific training sets that included only the most species - specific sequences available , while maintaining approximately equal sample sizes across taxa .
the most challenging case was that of the arbuscular mycorrhizal fungi , for which very few protein - coding sequences are available . to increase the amount of data in this training set ( b2 ) without biasing sample sizes , we pooled sequences from all species in the zygomycetes with all available chytridiomycete coding sequences , and compared this training set with a set from a single plant genus , medicago ( a2 ) .
we chose this option , rather than including an arbitrary subset of sequences from the ascomycetes and basidiomycetes , because zygomycetes and chytridiomycetes have diverged from their common ancestor less recently than the ascomycetes and basidiomycetes , based on 18s ribosomal rna sequence data .
that is , the ascomycetes and basidiomycetes are more highly derived from the common fungal ancestor than zygomycetes and chytridiomycetes , which resemble more closely the ancestral state in modern lineages .
starting with a full set of sequences , we filtered for high - quality sequences by trimming regions having extensive ambiguous bases ( n - rich ) and poly(a ) or poly(t ) regions .
thus , we trimmed poly(a ) and poly(t ) sites to minimize the cases in which a test sequence resembles one training set more closely than the other , simply by virtue of having an abundance of the hexamer aaaaaa or tttttt .
similarly , test results obtained from short or n - rich sequences can be difficult to interpret .
we allowed no more than one n per hexamer and trimmed poly(a ) or poly(t ) tracts longer than 13 nucleotides . to accommodate for possible sequence chimeras ,
those sequences found to contain an internal poly(a ) or poly(t ) segment longer than 13 nucleotides were partitioned into two fragments , and the longer of the two fragments was used in analysis , provided its length was at least 300 nucleotides . after trimming , we screened all remaining sequences of 300 nt or longer for similarity to escherichia coli using blastn .
all blast searches used default parameters and low - complexity filtering with the programs dust or seg .
the decision to exclude non - coding rna sequences from training sets was informed by the appearance of bimodal distributions of hexamer frequencies and a large degree of overlap between calibration curves ( data not shown ) , likely a result of divergent evolutionary rates between protein - coding and non - coding sequences .
chloroplast and mitochondrial sequences were eliminated to avoid complications due to variation in codon usage between nuclear and organellar genomes .
table 2 summarizes counts of sequences and nucleotides in training sets before and after trimming and screening .
to test the validity of word counting as a solution to the problem , we identified a set of 50 gene sequences from plants ( m. truncatula and g. max ) , oomycetes ( phytophthora ) , zygomycetes ( glomus versiforme ) , and bacteria ( sinorhizobium meliloti and agrobacterium tumefaciens ) , for which the function and origin have been characterized experimentally .
we chose genes known to play a role in plant - microbe interactions , as well as genes that are found across taxa .
we withheld these sequences , and partial transcripts of the same genes , from training sets prior to comparative lexical analysis , and calculated hexamer dissimilarities for each of the three training sets as described below .
to diagnose the species of origin for sequences expressed in symbiotic cultures , we collected sequences generated by distinct est sequencing projects from the genbank database .
sequences from pathogenic interactions originated from cultures of a species from the genus phytophthora with its plant host , such as p. sojae and soybean ( g. max ) isolated from inoculated hypocotyls two days after infection   and p. medicaginis and m. truncatula isolated from infected roots 10 days after infection ( c. vance , unpublished data ) .
sequences expressed during mutualistic interactions were obtained from cultures with m. truncatula and mycorrhizal ( glomus versiforme ; m.j .
harrison , unpublished data ) or rhizobacterial ( s. meliloti ; k. vandenbosch , unpublished data ) endosymbionts several days after inoculation
. sequences expressed in pure , axenic cultures from p. sojae mycelia and zoospores   and from sterile , uninoculated m. truncatula roots   provided a basis for comparison in which no foreign transcripts were expected . to maximize the reliability of diagnostic comparisons , we screened test sequences for high quality as for training sequences , and for low similarity to e. coli , chloroplast and mitochondrial genes , and non - coding rna transcripts ( ribosomal and transfer rnas ) .
independent blastn comparisons identified sequences having very high similarity ( e < 10 ) to vector sequences or moderately high similarity ( e < 10 ) to non - nuclear or non - coding sequences obtained from genbank .
we wrote a perl program ( countgc.pl ) that calculates the gc base content of a sequence as the portion of guanine and cytosine residues among all unambiguous ( non - n ) nucleotides in a sequence . the hist method in r ,
version 1.1.1   aggregated continuous percentages into discrete histogram bins , using bin sizes of 2% difference in gc , with inclusive lower bin boundaries and exclusive upper bounds ; the lm method tested for linear correlation of the dissimilarity test statistic t with gc .
white et al .   used a likelihood - ratio test to determine whether word frequencies from a particular sequence more closely resemble the frequency distribution of control data sets from the taxon being sequenced or a distantly related outgroup .
they computed a test statistic t(a , b , x ) for each sequence x as the difference of log - likelihood ratio dissimilarity measures , d(a , x ) = -2log(a , x ) , for two data sets , a control set a and an outgroup b , such that t(a , b , x ) = d(a , x ) - d(b , x ) .
a negative value for t indicates that the sequence more closely resembles words from a ; conversely , a positive value indicates a likely contaminant related to b. ( dissimilarity is conceptually related to distance . however , dissimilarity does not measure distance because it does not possess the mathematical properties of a distance metric . ) unlike the calculation of calibration curves , in which 300-nucleotide subsequences are randomly resampled , hexamer dissimilarity is measured over the whole length of a test sequence when inferring a transcript 's origin .
originally , the investigators used the null hypothesis that no difference exists for dissimilarity measures between the two data sets , or that t(a , b , x ) = 0 .
white et al .   tested two alternative hypotheses : that t < 0 , being more like a , or t > 0 , like b. lexical analysis using pentamers or heptamers yields similar error rates and very highly correlated values for the test result ( not shown ) . because white et al .  
reported the best results were obtained using hexamers , and because a word size of six nucleotides corresponds to the size of a dicodon , we chose to analyze hexamer frequencies . to use longer words requires more training data , because the number of possible words increases exponentially with increasing word size .
use of shorter words may be adequate for some applications and will be investigated in future work . though we used white 's word - counting methods , we did make slight modifications .
we simplified one program ( called hybridize ) to compute individual dissimilarity values , rather than paired differences ; a patch that details how to modify the c program is available ( see hyb2dis.txt in additional data files ) .
more importantly , we amended the null hypothesis and interpreted calibration curves to test for statistically significant dissimilarity differences . though the likelihood - ratio test statistic indicates the magnitude of similarity to a or b , we do not know what values for t are significant with known confidence .
when testing hypotheses , one can make two types of error : type i , or false positives , and type ii , false negatives .
the false - positive rate is denoted  and false - negative rate . we determine  and  from overlap in the calibration curves . inferring error rates from calibration curves
is justified because we know the correct answer and determine the error rate via resampling , as with bootstrap methods to infer error rates or confidence intervals .
we are interested in knowing from which of two organisms a sequence originated , and are reasonably confident that it came from either one or the other .
thus , we assume it came from one and test whether we have evidence to refute this assumption .
the null hypothesis here is that sequence x is from a. alternatively , it might be from b. evaluating the calibration curve overlap at t = 0 quantifies the associated error rates .
the cumulative distribution function ( cdf ) of taxon b specifies  where cdfb intersects 0 ; the cdf from a specifies  as 1-cdfa(0 )
. we can thus resolve the problem with known confidence p : p ( t > 0 ) = . all other computations were performed as described previously .
software used for lexical analysis was obtained via anonymous ftp from the tigr software ftp site .
the following files are available for download : countgc.pl : perl script used to compute gc content of sequences analyzed .
hyb2dis.txt : patch file that converts white 's hybridize program to compute individual dissimilarity values .
training sets ( glycinemedicago.txt,rhizobia.txt , stramenopiles.txt , zygochytrid.txt ) : fasta - formatted text files that contain the sequences used for calibration and comparison .
test sets ( psojaeha.txt , psojaemy.txt , psojaezo.txt , mtrhe.txt , dsir.txt , mham.txt , kv0.txt , kv2.txt , kv3.txt ) : fasta - formatted text files containing transcripts analyzed , edited for quality .
test results ( psojaeha.dat , psojaemy.dat , psojaezo.dat , mtrhe-a1b1.dat , mtrhe-a2b2.dat , dsir.dat , mham.dat , kv0.dat , kv2.dat , kv3.dat ) : text files that contain transcript analysis results , sorted from least to most plant - like .
fasta - formatted text files containing transcripts analyzed , edited for quality . text files that contain transcript analysis results , sorted from least to most plant - like .
we thank callum bell , mark gijzen , maria harrison , tom kepler , deb samac , and bruno sobral for valued discussions and feedback . comments from b. m. tyler and an anonymous reviewer on an earlier version of this work greatly enhanced its presentation .
distribution of gc content in pure and mixed - culture libraries . ( a ) probability densities for histogram bin sizes of 0.02 ( 2% ) in base content .
( a ) calculation of statistical parameters from cdfs a and b. overlap in the upper tail of cdfa with cdfb and the lower tail of cdfb with cdfa are likely regions for error .
we find the false - positive rate  where 1 - cdfa intersects 0 [ cdfa(0)= 1 -  ] , and the false - negative rate  where cdfb crosses 0 . also shown
are the medians (  ) for each distribution , where cdf( ) = 0.5 .
, solid black line ) and stramenopile plus p. infestans est ( b1 , dashed black line ) training sequences .
superimposed distributions of test results show dissimilarity differences for infected g. max ( green ) and axenic p. sojae mycelial and zoospore sequences ( blue and cyan , respectively ) .
each point corresponds to an expressed tag from either ( a ) infected g. max or ( b ) axenic p. sojae mycelial or ( c ) zoospore sequences , compared with plant ( a1 ) and stramenopile plus p. infestans est training sequences ( b1 ) .
the identity function indicates equal dissimilarity to both training sets , t = d(a ) - d(b)= 0 .
calibration curves compare plant training sets ( a1 and a2 , solid black lines ) with one of three microbial symbiont training sets ( broken black lines ) : ( a ) stramenopile and p. infestans est sequences ( b1 ) ; ( b ) pooled zygomycete and chytridiomycete coding sequences ( b2 ) ; and ( c ) sequences from the genera rhizobium , sinorhizobium and bradyrhizobium ( b3 ) .
cumulative distributions of test results from m. truncatula axenic and microbial symbiont mixed cultures appear in each panel ( colored lines ) .
each point indicates the dissimilarity of a test sequence compared with a plant training set ( a1 or a2 ) and one of three microbial symbiont training sets : ( a ) stramenopile and p. infestans est sequences ( b1 ) ; ( b ) pooled zygomycete and chytridiomycete coding sequences ( b2 ) ; and ( c ) sequences from the genera rhizobium , sinorhizobium and bradyrhizobium ( b3 ) . sequences from m. truncatula axenic ( green ) and microbial symbiont mixed culture libraries are represented in each panel .
number of sequences ( n ) and nucleotides ( nt ) , as raw , trimmed ( removed n - rich regions , poly(a ) and poly(t ) sites ) , and screened sequences ( removed ribosomal , chloroplast , and mitochondrial dna and remaining sequences shorter than 300 nucleotides ) .
number of est sequences ( n ) and nucleotides ( nt ) as raw , trimmed ( limited lengths of n - rich regions , poly(a ) and poly(t ) sites ) , and screened ( removed ribosomal , chloroplast , and mitochondrial dna , and remaining sequences shorter than 300 nt ) sequences .
 backgroundmost organisms have developed ways to recognize and interact with other species . 
 symbiotic interactions range from pathogenic to mutualistic 
 . some molecular mechanisms of interspecific interaction are well understood , but many remain to be discovered . expressed sequence tags ( ests ) from cultures of interacting symbionts can help identify transcripts that regulate symbiosis , but present a unique challenge for functional analysis . given a sequence expressed in an interaction between two symbionts , the challenge is to determine from which organism the transcript originated . for high - throughput sequencing from interaction cultures , 
 a reliable computational approach is needed . 
 previous investigations into gc nucleotide content and comparative similarity searching provide provisional solutions , but a comparative lexical analysis , which uses a likelihood - ratio test of hexamer counts , is more powerful.resultsvalidation with genes whose origin and function are known yielded 94% accuracy . 
 microbial ( non - plant ) transcripts comprised 75% of a phytophthora 
 sojae - infected soybean ( glycine max cv harasoy ) library , contrasted with 15% or less in root tissue libraries of medicago truncatula from axenic , phytophthora medicaginis - infected , mycorrhizal , and rhizobacterial treatments . 
 mycorrhizal libraries contained about 23% microbial transcripts ; an axenic plant library contained a similar proportion of putative microbial transcripts.conclusionscomparative lexical analysis offers numerous advantages over alternative approaches . 
 many of the transcripts isolated from mixed cultures were of unknown function , suggesting specificity to symbiotic metabolism and therefore candidates likely to be interesting for further functional investigation . 
 future investigations will determine whether the abundance of non - plant transcripts in a pure plant library indicates procedural artifacts , horizontally transferred genes , or other phenomena . 
Background
Results
Discussion
Methods and materials
Training sequences
Calibration
Data quality
Validation
Test sequences
Base content
Comparative lexical analysis
Additional data files
Supplementary Material
Acknowledgements
Figures and Tables