although the human genome sequence was released a decade ago , the role of functional noncoding rnas ( ncrnas ) is much less understood compared with their coding counterparts .
several previous studies have demonstrated that the human genome is pervasively transcribed ( 14 ) , but thoroughly cataloging all the rna species ( especially ncrna ) is challenging .
undiscovered ncrnas might be rare , transient or beyond the detection limits of conventional approaches .
furthermore , ncrnas also tend to be idiosyncratic to species and tissues ( 5,6 ) .
nevertheless , advances in rna - seq have provided a new method of surveying the whole transcriptome to an unprecedented degree .
recent genome - wide studies revealed tens of thousands of novel transcripts , the majority of which were long noncoding rnas ( lncrnas , > 200 nt ) ( 49 ) .
although a few dozen lncrnas have been characterized to some extent and are reported to have critical roles in diverse cellular and disease development processes ( 6,1014 ) , the biogenesis and function of most lncrnas remain unclear .
accurate and quantitative assessment of coding potential is the first step toward comprehensive annotation of newly discovered transcripts .
until now , prediction of coding potential heavily relied on sequence alignment , either pairwise homology search for protein evidence such as that used in the coding - potential calculator ( cpc ) and portrait methods ( 15,16 ) or multiple alignments to calculate the phylogenetic conservation score such as that used in the phylogenetic codon substitution frequencies ( phylocsf ) and rnacode methods ( 17,18 ) .
alignment - based approaches are particularly useful for highly conserved protein - coding genes and , to a lesser extent , short genes encoding housekeeping or regulatory rnas ( e.g. snrnas , snorna , transfer rna ) .
however , these approaches can not immediately apply to all the novel transcripts because of several intrinsic limitations .
first , most newly discovered transcripts are lncrnas , which tend to be lineage specific and less conserved ( 5,6 ) .
for example , only 29 of 550 lncrnas identified from zebrafish had detectable sequence similarity with putative mammalian orthologs ( 6 ) , and only 993 of 8195 human lncrnas have orthologous transcripts in other species ( 5 ) .
second , considerable fractions of lncrnas are overlapped with either the sense or antisense strand of protein - coding genes .
these lncrnas can not be correctly classified by homology searching because they would have significant matches to protein - coding genes ( 3,8,19 ) .
third , the reliability of alignment - based approaches largely depends on the quality of alignments ( 20 ) .
this is problematic because most widely used multiple - sequence alignment tools use heuristics and do not guarantee optimal alignments .
for instance , cpc and phylocsf took 2 days to evaluate the coding potential of 14 353 lncrnas identified by cabili et al .
this problem is getting more attention as massive - scale rna sequencing is increasingly being performed .
consequently , a more accurate , robust and faster method that does not rely on sequence alignment is needed to distinguish ncrnas , especially lncrnas , from protein - coding genes . here , we present coding - potential assessment tool ( cpat ) , an alignment - free program , which uses logistic regression to distinguish between coding and noncoding transcripts on the basis of four sequence features .
cpat is highly accurate ( 0.967 ) and extremely efficient ( 10 000 times faster than cpc and phylocsf , and 50 times faster than portrait ) .
cpat needs only the sequence or coordinate file as input , and it is straightforward to use .
we expanded the availability of cpat to a larger scientific audience via a web interface , which allows users to submit sequences and receive the prediction results back almost instantaneously ( http://lilab.research.bcm.edu/cpat/index.php ) .
coding - potential prediction is essentially a binary decision problem , which makes logistic regression a suitable approach . as an alignment - free method , all selected features ( predictor variables )
the first feature was the maximum length of the open reading frame ( orf ) .
orf length is one of the most fundamental features used to distinguish ncrna from messenger rna because a long putative orf is unlikely to be observed by random chance in noncoding sequences . despite the simplicity , orf length has high concordance with more sophisticated discrimination methods and remains the primary criterion in almost all coding - potential prediction methods ( 21 ) .
the second feature was orf coverage defined as the ratio of orf to transcript lengths .
this feature also has good classification power , and it is highly complementary to , and independent of , the orf length ( supplementary figures s1 and s3 ) . some large bona fide ncrnas may contain putative long orfs by random chance ( 5 ) , and thus can not be classified correctly by orf length alone .
fortunately , those large ncrnas usually have much lower orf coverage than protein - coding rnas ( figure 1b ) . 

figure 1.score distribution between coding ( red ) and noncoding ( blue ) transcripts for the four linguistic features selected to build the logistic regression model ; training data set containing 10 000 coding and 10 000 noncoding transcripts were used .
score distribution between coding ( red ) and noncoding ( blue ) transcripts for the four linguistic features selected to build the logistic regression model ; training data set containing 10 000 coding and 10 000 noncoding transcripts were used .
the third feature we used was the fickett testcode score ( termed  fickett score hereafter ) , which is a simple linguistic feature that distinguishes protein - coding rna and ncrna according to the combinational effect of nucleotide composition and codon usage bias ( 22 ) .
briefly , the fickett score is obtained by computing four position values and four composition values ( nucleotide content ) from the dna sequence .
the position value reflects the degree to which each base is favored in one codon position versus another .
for example , position value of a ( apos ) is calculated as follows : 

  cpos , gpos and tpos are determined in the same way .
these eight values are then converted into probabilities ( p ) of coding using a lookup table provided in the original article .
each probability is multiplied by a weight ( w ) for the respective base , where the value of w reflects the percentage of time each parameter alone successfully predicts coding or noncoding function for the sequences of known function .
finally , the fickett score is calculated as follows : 

  the fickett score is independent of the orf , and when the test region is 200 nt in length ( which includes most lncrna ) , this feature alone can achieve 94% sensitivity and 97% specificity , with 
the fourth feature we used was hexamer usage bias ( termed  hexamer score hereafter ) .
this may be the most discriminating feature because of the dependence between adjacent amino acids in proteins ( 23 ) .
the hexamer score can be computed in numerous ways ; here , we used a log - likelihood ratio to measure differential hexamer usage between coding and noncoding sequences . for a given dna sequence , we calculated the probability of the sequence under the model of coding dna and under the model of noncoding dna , and then we took the logarithm of the ratio of these probabilities as the score of coding potential .
we used f ( hi ) ( i = 0 , 1 ,  , 4095 ) and f ( hi ) ( i = 0 , 1 ,  , 4095 ) to represent in - frame hexamer frequency , calculated from coding and noncoding training data sets ( described below ) , respectively .
for a given hexamer sequence s = h1 , h2 ,  , hm , 

  hexamer score determines the relative degree of hexamer usage bias in a particular sequence .
positive values indicate a coding sequence , whereas negative values indicate a noncoding sequence . we build a logistic regression model using these four linguistic features as predictor variables .
a  test was used to evaluate whether our logit model with predictors fits the training data significantly better than the null model , which had only an intercept .
we built a high - confidence training data set to measure the prediction performance of our logit model .
this data set contained 10 000 protein - coding transcripts selected from the refseq database ; all transcripts had high - quality protein sequences annotated by the consensus coding sequence project .
we evaluate the model with a 10-fold cross - validation and measured its sensitivity , specificity , accuracy , precision and area under the curve ( auc ) characteristics .
the receiver operating characteristic ( roc ) curve and precision  recall ( pr ) curve were generated using rocr package ( 24 ) .
we also built a nonparametric two - graph roc curve for selecting the optimal cpat score threshold that maximizes the sensitivity and specificity of cpat while minimizing misclassifications .
we built an independent test data set to compare the performance of cpat with that of cpc , phylocsf and portrait .
this test set composed of 4000 high - quality protein - coding genes ( refseq annotated ) and 4000 lncrnas from a human lncrna catalog ( 5 ) .
assuming that all 4000 lncrnas are truly noncoding sequences , we could compute the sensitivity , specificity , accuracy and precision of the algorithms to measure their performance .
those 528 genes were equally assigned to the true - negative and false - positive categories .
the abbreviations in the equations below are as follows : fn , false negative ; fp , false positive ; tn , true negative ; tp , true positive 



all four selected features were concordantly higher in coding transcripts and lower in noncoding transcripts ( figure 1 ) .
we plotted three major features ( orf size , fickett score and hexamer score ) in a three - dimensional space to evaluate their combinatorial effect ( figure 2 ) .
coding and noncoding transcripts in our training data set were grouped into two distinct clusters , indicating good concordance between features .
the  test p value was < .001 ( = 23 548.44 ; degrees of freedom = 4 ) , indicating that the logit model as a whole fits significantly better than the null model .
ten - fold cross - validation showed that cpat could achieve very high accuracy , with an auc of 0.9927 ( figure 3a ) .
we also provide the pr curve because the roc curve can be misleading when the test data are largely skewed ( figure 3b ) .
we use nonparametric two - graph roc curves to determine an optimal cpat score threshold that maximizes the discriminatory power ( figure 3c and d ) . according to figure 3d ,
a score threshold of 0.364 gave the highest sensitivity and specificity ( 0.966 for both ) for human data . 

figure 2.three-dimensional plot shows combinatorial effects of fickett score , hexamer score and orf size on 10 000 coding genes ( red dots ) and 10 000 noncoding genes ( blue dots ) . 

dashed curves represent the 10-fold cross - validation ; solid curves represent the averaged curve from 10 validation runs .
( d ) two - graph roc curve is used to determine the optimum cutoff value .
three - dimensional plot shows combinatorial effects of fickett score , hexamer score and orf size on 10 000 coding genes ( red dots ) and 10 000 noncoding genes ( blue dots ) .
dashed curves represent the 10-fold cross - validation ; solid curves represent the averaged curve from 10 validation runs .
( d ) two - graph roc curve is used to determine the optimum cutoff value .
we compared the performance of cpat with that of cpc , phylocsf and portrait ( protein - independent support vector machine model ) using an independent test data set composed of 4000 coding genes and 4000 noncoding genes .
a multiple alignment of 45 vertebrate genomes , including that of human , was downloaded from the ucsc ( university of california , santa cruz ) genome browser and was used as the input alignment for phylocsf . in general , cpat ( sensitivity : 0.96 , specificity : 0.97 ) had greater classification power compared with all other programs ( figure 4 ; supplementary tables s1 and s2 ) .
although cpc had the highest sensitivity ( 0.99 ) , it suffered from poor specificity ( 0.74 ) .
one possible explanation is that a significant proportion of ncrnas has a certain degree of sequence similarity to protein - coding genes .
phylocsf had the least sensitivity ( 0.90 ) and the lowest specificity ( 0.63 ) .
part of the reason for these outcomes is that nonconserved transcripts can not be processed by phylocsf .
if we consider those 528 nonconserved transcripts as noncoding , the specificity increased from 0.63 to 0.69 , and the sensitivity remained unchanged .
cpat achieved highest overall accuracy ( 0.97 ) when compared with cpc ( 0.87 ) , phylocsf ( 0.76 ) and portrait ( 0.92 ) .
cpat s excellent discriminatory power was further demonstrated by the greatest separation between the score distributions of coding and noncoding sequences ( figure 5 ) . unlike cpc , phylocsf and portrait , choosing a smaller cpat score threshold to increase the sensitivity will not sacrifice too much specificity . 

figure 4.performance comparison between cpat , cpc , phylocsf and portrait using roc curves . 

figure 5.cumulative curves of coding - potential assessment score for ( a ) cpat , ( b ) portrait , ( c ) cpc and ( d ) phylocsf .
cumulative curves of coding - potential assessment score for ( a ) cpat , ( b ) portrait , ( c ) cpc and ( d ) phylocsf .
one could argue that phylocsf underperformed in this study because we used whole transcripts for testing rather than consecutive protein - coding exons and intergenic regions as used in its original article ( 17 ) . to address this issue , we compiled another single - exon test data set consisting of 184 protein - coding and 278 noncoding transcripts . the test results with this data set indicated that cpat ( sensitivity : 0.962 , specificity : 0.842 ) still outperformed phylocsf ( sensitivity : 0.832 , specificity : 0.588 , supplementary figure s2 ) .
( 25 ) , phylocsf ( sensitivity 0.91 , specificity 0.99 ) has better performance than cpat ( sensitivity 0.50 , specificity 0.98 ) .
this is reasonable because lncrnas in our test data set are poorly conserved , whereas lncrnas in lin et al .
test data set are highly conserved because they are taken from multiple - sequence alignments of three closely related drosophila species .
hence , we argue that phylocsf works better if the transcripts are highly conserved , which are rare to find in lncrnas ( 5,6 ) .
this also highlights the achilles heel of the alignment - based methods for detecting lncrnas .
in contrast , the dramatic decrease in cpat s sensitivity is due to the lack of orf information in lin et al .
test data set , which is largely composed of individual exons , and not exon - length complete transcripts .
this , however , will not limit the application scope of cpat because most full - length transcripts can be constructed at the current sequencing depth ( 8) .
we measured the computational speed of cpat , cpc and phylocsf on a sample of 200 sequences randomly selected from the test data set .
cpat took 0.67 s to process the data , and it was four orders of magnitudes faster than both cpc [ 11 945 s ( 3.3 h ) ] and phylocsf [ 11 737 s ( 3.3 h ) ] . furthermore ,
computational time for the phylocsf did not include the time spent preparing multiple - alignment files for analysis .
portrait was significantly faster than cpc and phylocsf , and therefore all 8000 test genes were used to evaluate its speed : cpat took 23.83 s to process the test set , and it was 48 times faster than portrait [ 1146.30 s ( 19 min ) ] .
a number of linguistic features characterizing coding rna sequences have been developed over the past 30 years .
these include maximum orf size , dinucleotide usage , codon usage bias , hexamer usage bias , nucleotide composition bias between codon positions and imperfect periodicity in base occurrences ( 23,26 ) . among these features , we selected orf features ( size and coverage ) because of their discriminatory power and ease of calculation ( 21 ) . in - frame hexamer score
was selected because it has the highest prediction accuracy ( average of sensitivity and specificity ) as evaluated by fickett and tung in 1992 ( 23 ) .
fickett score was selected because it simultaneously captures the compositional bias and position asymmetry , which are orthogonal to the orf features .
supplementary figure s3 shows the performance of these individual features as well as the combined feature set .
the combined feature set has very high sensitivity and specificity ( > 0.966 ) , leaving very little room for further improvement .
annotation of genomes has always been a challenging task for biologists , and these efforts have been accelerated by deep transcriptome sequencing .
distinguishing between protein - coding and noncoding sequences is the first and arguably the most crucial step in genome annotation .
detecting the coding - potential of these transcripts via alignment - based software is intractable .
we developed cpat , a highly accurate alignment - free method , which uses a logistic regression model to discriminate between coding and noncoding transcripts using pure linguistic features . compared with other tools ,
cpat is more robust , markedly faster and more convenient to use . taken together , cpat is able to accurately assess the coding potential of tens of thousands of transcripts in real - time , and will be a valuable tool for the rapidly growing rna - seq community .
source code was implemented in c and python and is freely available at : http://code.google.com / p / cpat/. the web server was implemented in php , mysql and apache , with support for all major browsers : http://lilab.research.bcm.edu/cpat/index.php .
supplementary data are available at nar online : supplementary tables 1 and 2 and supplementary figures 13 .
department of defense prostate cancer program [ pc094421 to w.l . ] ; the cancer prevention and research institute of texas [ rp110471-c3 to w.l . ] ; the center for individualized medicine ( cim ) at mayo clinic ( to j.p.k . ) . funding for open access charge : cancer prevention and research institute of texas [ rp110471-c3 to w.l . ] .
 thousands of novel transcripts have been identified using deep transcriptome sequencing . 
 this discovery of large and  
 hidden transcriptome rejuvenates the demand for methods that can rapidly distinguish between coding and noncoding rna . here 
 , we present a novel alignment - free method , coding potential assessment tool ( cpat ) , which rapidly recognizes coding and noncoding transcripts from a large pool of candidates . to this end 
 , cpat uses a logistic regression model built with four sequence features : open reading frame size , open reading frame coverage , fickett testcode statistic and hexamer usage bias . 
 cpat software outperformed ( sensitivity : 0.96 , specificity : 0.97 ) other state - of - the - art alignment - based software such as coding - potential calculator ( sensitivity : 0.99 , specificity : 0.74 ) and phylo codon substitution frequencies ( sensitivity : 0.90 , specificity : 0.63 ) . 
 in addition to high accuracy , cpat is approximately four orders of magnitude faster than coding - potential calculator and phylo codon substitution frequencies , enabling its users to process thousands of transcripts within seconds . 
 the software accepts input sequences in either fasta- or bed - formatted data files . 
 we also developed a web interface for cpat that allows users to submit sequences and receive the prediction results almost instantly . 
INTRODUCTION
MATERIALS AND METHODS
RESULTS
DISCUSSION
AVAILABILITY AND IMPLEMENTATION
SUPPLEMENTARY DATA
FUNDING
Supplementary Material