BACKGROUND
periodic phenomena are widely studied in biology and there are numerous biological applications where periodicities must be detected from experimental biological data.
because the measured data are often non-ideal, efficient algorithms are needed to extract as much information as possible.
spectral estimation has been a classical research topic in digital signal processing and has recently found important applications in dna microarray time series data analysis.
many spectral estimation methods have been proposed in the past decades, including the modified periodogram, the autoregressive  model, the music algorithm and the multitaper method  <cit> .
although all these algorithms have their own advantages, they were all developed based on a basic assumption: the input signal is evenly sampled.
however, in many real-world applications, the data can be unevenly sampled.
for example, in dna microarray gene expression experiments, a time series may be obtained with different sampling intervals  <cit> .
furthermore, an evenly sampled time series may contain missing values due to corruption or absence of some expression measurements  <cit> .
a time series with missing values can be considered as an unevenly sampled time series in general.
recently, several methods for detecting periodic gene expression have been proposed  <cit> .
lu et al.
<cit>  have proposed a periodic-normal mixture  model to fit transcription profiles of periodically expressed genes in cell cycle microarray experiments.
ahdesmäki et al.
<cit>  proposed a general-purpose robust testing procedure for finding periodic sequences in multiple time series data, which is based on a robust spectral estimator that is incorporated into a hypothesis testing framework using the so-called g-statistic together with correction for multiple testing.
chen  <cit>  proposed a statistical inference approach, the c&g procedure, to effectively detect statistically significant periodically expressed genes based on two statistical hypothesis testing procedures.
wichert et al.
<cit>  proposed to use the average periodogram as an exploratory tool to detect the presence of possible periodic genes and give an exact statistical test to determine whether or not a sinusoid is presence.
luan and li  <cit>  proposed to use the shape-invariant model combined with a cubic b-spline estimation to model periodic gene expression profiles.
ruf  <cit>  is one of the first to treat evenly sampled gene expression time series with missing values as unevenly sampled data for spectral analysis using the lomb-scargle periodogram.
bohn et al.
<cit>  have used the lomb-scargle periodogram in their attempt to detect rhythmic components in the circadian cycle of the crassulacean acid metabolism plants.
glynn et al.
<cit>  also used the lomb-scargle periodogram to detect periodic patterns in unevenly spaced gene expression time series.
the lomb-scargle periodogram produces better results on unevenly sampled data than the classical fourier transform method since it weights the data on a "per point" basis instead of on a "per time interval" basis  <cit> .
lomb  <cit>  proved that this periodogram is the same as the classical periodogram in the case of equally spaced data.
however, since the lomb-scargle method assumes that there is a single stationary sinusoid wave with infinite support, it introduces spurious periodic components in the periodogram for data with a finite length.
also, due to the effect of noise in the data, it may produce inaccurate estimation results.
in this paper, we propose a new spectral estimation technique for unevenly sampled data.
our method models the signal in a shift-invariant signal space, for which many theories and algorithms are available  <cit> .
in our method, a direct spectral estimation formula is derived based on the b-spline basis that has finite support.
experiments on simulated noisy periodic signals show that our algorithm is more accurate in detecting periodicity compared to the lomb-scargle algorithm.
RESULTS
our method is based on signal reconstruction in a shift-invariant signal space, where a direct spectral estimation procedure is developed using the b-spline basis.
the details of the reconstruction algorithm and the power spectrum density  estimation are given in the method section.
simulated data
we first test our spectral estimation algorithm on simulated signals to compare the estimation accuracy with the lomb-scargle method.
a cosine curve has been used to represent the ideal expression of a gene that goes from an "on" state, to an "off" state, and then back to "on"  <cit> .
for a gene g and expression level observed at time ti, we denote the time series by yg,
where ygβcos⁡+εg
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgzbqwdawgaawcbagaem4zacgabeaakiabcicaoiabdsha0naabaaaleaacqwgpbqaaeqaaogaeiykakcccigae8nsdimagi4yammaei4ba8maei4camnaeiikagyaasaaaeaacqqg0baddawgaawcbagaeeyaakgabeaakiab=b8awbqaaiabigdaxiabikdayaaacqggpaqkcqghrawkcqwf1oqzdawgaawcbagaee4zacgabeaakiabcicaoiabdsha0naabaaaleaacqwgpbqaaeqaaogaeiykakcaaa@4b11@
for i =  <dig> ...,n and g =  <dig> ...,g. our test data consists of simulated time series data for the expression of g =  <dig> genes, where  <dig> of them are random genes  and  <dig> are noisy periodic genes.
to obtain this dataset, the time series  is first evenly sampled at  <dig> points.
that is, ti = i, .
then, time points are randomly deleted from each time series to simulate the uneven sampling situation.
in the second simulation test, we use the  <dig> simulated noisy periodic gene profiles and compare our method with the lomb-scargle approach in terms of errors in the dominant frequency.
in figure  <dig>  we show the mean-square error in dominant frequency under various percentages of presence entries.
from figure  <dig>  we observe that our method is better than the lomb-scargle method.
finally, we use the entire  <dig> simulated genes and the false discovery rate  gene selection strategy using g-statistic to test the accuracy and sensitivity of our method.
lomb-scargle's test is used for lomb-scargle method.
we added artificial gaussian noise with mean μ =  <dig> and various sd values .
in table  <dig>  we compare the effectiveness of the two methods in detecting periodic gene expressions with different missing ratios and various noise levels under the same false discovery rate q. from table  <dig>  we find that our method is better than the lomb-scargle method in detecting periodic expressions with various missing ratios.
our method is also more robust than the lomb-scargle method under different noise levels.
the simulated data consists of  <dig> time series .
the total number of periodic genes is  <dig>  p is the number of periodic genes that are statistically significant for a fdr level of q =  <dig> .
the number of false positives fp can be computed as fp = q*tp/, where tp is the number of true positives.
keeping q at a fixed level ensures that we do not sacrifice specificity for sensitivity.
experimental data
plasmodium falciparum
we have tested our algorithm on the gene expression data of plasmodium falciparum, which is one of the species that cause human malaria  <cit> .
the gene expression time series from the asexual intraerythrocytic developmental cycle  of plasmodium falciparum are strongly periodic.
identifying periodically expressed genes is useful for understanding the genome of plasmodium falciparum and designing effective vaccines for prevention of human malaria.
in the gene expression database from bozdech et al.
<cit> , data values at the 23rd and the 29th hours are completely missing.
an example of a gene expression profiles from the database is shown in figure  <dig>  and its periodograms obtained by using the lomb-scargle algorithm and our algorithm are shown in figure  <dig>  the frequencies corresponding to the peaks in the periodograms obtained by using the lomb-scargle method and our method are 1/ <dig>  hz and 1/ <dig>  hz, respectively.
another example is shown in figure  <dig>  the frequencies corresponding to the peaks in the periodograms obtained by using the lomb-scargle method and our method are 1/ <dig>  hz and 1/ <dig>  hz, respectively ).
we can see from these diagrams that our algorithm can effectively reduce the spurious oscillation components in the spectra.
the plasmodium falciparum dataset was analyzed by bozdech et al.
<cit>  using the fast fourier transform , and later by glynn et al.
<cit>  using the lomb-scargle algorithm.
bozdech et al.
<cit>  identified  <dig> periodic genes in the quality control dataset of plasmodium falciparum, while glynn et al.
<cit>  found  <dig> periodic genes in the complete dataset of  <dig> .
our analysis has shown that the number of periodic profiles in the complete dataset should be around  <dig> to  <dig>  our estimate is based on analyzing the trend of the sorted g-statistic  in method) as shown in figure  <dig>  the intersection of the two distinct slopes points indicates a sudden change in the g-statistic trend.
nevertheless, no distinct cut-off between periodic/aperiodic profiles can be identified here.
figure  <dig> shows the histogram plot of the g-statistic.
note that a profile with larger g-statistic value implies it is much more likely to be periodic.
we see that many of the profiles are likely to be periodic.
no distinct valley can be observed in the histogram, indicating that a cut-off for periodicity/aperiodicity is difficult to be obtained here.
we also examine the periods of the profiles, and figure  <dig> shows the histogram plot.
it can be seen that there is a prominent period of  <dig> hours with a count of around  <dig> profiles.
this result agreed largely with that of bozdech et al.
<cit>   and that of glynn et al.
<cit>  .
nevertheless, our result also shows a much less prominent peak at a period of  <dig> hours with a low count of around  <dig> profiles.
in figure  <dig>  we show the top  <dig> ranking profiles, they can be seen to be highly periodic.
in figure 6– , we show the profiles that ranked around  <dig>   <dig>  and  <dig>  respectively.
even at around a ranking of  <dig>  some profiles  can still be judged to be somewhat periodic.
we provide a ranked list of the  <dig> profiles in additional file  <dig>
yeast
spectral analysis is useful for the identification of cell-cycle-regulated genes.
spellman et al.
<cit>  monitored genome-wide mrna levels for  <dig> yeast orfs simultaneously using several different methods of synchronization including an α -factor-mediated g <dig> arrest which covers approximately two cell-cycle periods with measurements at  <dig> min intervals for  <dig> min with a total of  <dig> time points, a temperature-sensitive cdc <dig> mutation to induce a reversible m-phase arrest, and a temperature-sensitive cdc <dig> mutation to arrest cells in g <dig> phase reversibly, and finally, an elutriation synchronization to produce the elutriation dataset of  <dig> time points .
for the cdc <dig> experiment, gene expression data were measured every  <dig> min for  <dig> min, lacking observations for the  <dig>   <dig>   <dig>   <dig> and  <dig> min time points, and gives a total of  <dig> time points.
for the cdc <dig> experiment, samples were taken every  <dig> min from  <dig> to  <dig> min for a total of  <dig> time points.
these four microarray datasets have spawned a large body of work on the gene expressions of the yeast cell cycle.
spellman  <cit>  originally identified a total of  <dig> cell-cycle genes in all four datasets, while wichert et al.
<cit>  claimed  <dig> cyclic genes in alpha,  <dig> cyclic genes in cdc <dig>   <dig> in cdc <dig>  and  <dig> in elutriation by using g-statistic as the test statistic.
chen  <cit>  detected  <dig> cyclic genes in alpha,  <dig> cyclic genes in cdc <dig>   <dig> in cdc <dig>  and  <dig> in elutriation by using the same g-statistic as the test statistic under the same fdr threshold level.
however, we found that the fisher p-value ) computed using the g-statistic has weak statistical power with such a short signal length.
instead, we analyze the four yeast datasets for periodicity and rank the gene expression profiles according to their g-statistic.
figure 7– show the histogram distributions of g-statistic values for the four datasets.
we see that there is a continuum of distribution and a clear cutoff for periodicity/aperiodicity cannot be identified .
the sorted g-statistic plots in figure 8– also supported such an observation.
hence, a ranking of the gene expression profiles would be much more informative than just giving an ad-hoc estimate of the number of periodic genes .
as pointed out by lichtenberg et al.
<cit> , there is a remarkably poor agreement between the numbers of periodically expressed genes detected by various computational methods.
to enable a more objective comparison between the performances of different algorithms, they proposed three benchmark sets b <dig>  b <dig>  and b <dig> .
set b <dig> contains a total of  <dig> genes previously identified as periodically expressed in small-scale experiments.
set b <dig> contains  <dig> genes whose promoters were bound by at least one of the  <dig> known cell cycle transcription factors  in two chromatin ip studies, and therefore many of the genes in this benchmark set should be expected to be cell cycle regulated.
set b <dig> contains  <dig> genes annotated in mips  <cit>  as "cell cycle and dna processing".
however, since a large number of genes involved in the cell cycle are not subjected to transcriptional regulation  and genes found in b <dig> were explicitly removed, only a small fraction of the genes in b <dig> are expected to be periodically expressed.
they define a good method as one that is able to reproduce precious findings , extract genes whose promoters are associated with known cell cycle transcription factors , or enriched for genes that play a role in the cell cycle .
a detail investigation of the expression profiles in the benchmark sets shows that the generally low coverage is really due to the absence of periodicity in many of the profiles.
in figure 11– , we plotted the ranking of the genes in the benchmark sets against the overall ranking in the four datasets.
we see that a large portion of the profiles in the benchmark sets is ranked very low in the four datasets.
a close examination of these profiles confirms that they are nearly random with no observable periodicity.
there could be two possible causes for this:  a large number of genes involved in the cell cycle are not directly transcription-regulated and therefore not periodic;  the genes are really periodic but experimental artifacts and noise has corrupted their profiles.
hence, for these profiles, it is expected that no algorithms would be able to identify them as periodic based on just a periodicity score.
in  <cit> , the strength of regulation  is an important criterion for the detection of periodically expressed genes.
regulation strength was not used as a criterion by our method  in detecting profile periodicity since the g-statistic value given by equation  gives a normalized periodic score.
based on the periodicity criterion alone, our method has comparable performance with  <cit>  for the alpha and cdc <dig> experiments.
for the cdc <dig> experiment, our result is notably inferior .
however, if we look at the cdc <dig> profiles as shown in figure  <dig>  we see that even the high ranking profiles are very noisy, and hence the comparison for cdc <dig> have lower reliability with regard to periodicity behavior.
when regulation strength is taken into consideration as well, the results of  <cit>  clearly out-performance our results for the b <dig> dataset .
this is not surprising since it was pointed out in  <cit>  that the benchmark datasets b <dig> and b <dig> are biased towards periodic genes which are strongly regulated.
in fact, it was observed in  <cit>  that regulation strength alone outperforms pure periodicity score for the alpha factor experiment on both b <dig> and b <dig> datasets.
however, for the b <dig> dataset, taking regulation strength into account actually gives inferior results for all three experiments.
as noted by  <cit> , the b <dig> dataset is likely to be biased toward small amplitude genes.
this suggests that regulation strength is only helpful in situations where genes involved in the cell cycle are also significantly regulated.
it would not be useful  in situations where genes are highly regulated but are not involved directly in cell cycle process.
the three benchmark datasets are also analyzed in  <cit> .
both the method of  <cit>  and our method considered only periodicity as the sole criterion.
we cited their results in figure  <dig>  comparing their results with our results as shown in figure  <dig>  we see that for the alpha factor experiment, our results is better for b <dig>  comparable with theirs for b <dig>  and inferior for b <dig>  for the cdc <dig> experiment, our results are better for all three benchmark datasets.
for this experiment, it is interesting to note that although our results are notably inferior to that of  <cit> , they are significantly better than that of  <cit> .
for the cdc <dig> experiment, our results are better for b <dig>  while comparable for b <dig> and b <dig>  the above comparative study indicates the difficulty in making general performance comparison between different algorithms even with benchmark datasets due to the differences in dataset characteristic.
CONCLUSIONS
in this paper, we have proposed a new spectral estimation algorithm based on a signal reconstruction technique in an unevenly sampled space.
the advantage of our algorithm over the lomb-scargle spectral estimation method is that the new algorithm can effectively reduce the effects of noise and spurious oscillation components and therefore improve the estimation accuracy.
experiments on simulated signals and real gene expression data show that our method is effective in identifying periodically expressed genes.
finally, we remark that this paper focuses on the improvement of periodicity estimation accuracy using spectral analysis algorithms.
another important issue is the statistical significance of the periodicity of a time series.
interested readers are referred to chen  <cit> , wichert et al.
<cit>  and glynn et al.
<cit> , who have used hypothesis testing to address this problem.

 periodic phenomena are widely studied in biology and there are numerous biological applications where periodicities must be detected from experimental biological data. because the measured data are often non-ideal, efficient algorithms are needed to extract as much information as possible. spectral estimation has been a classical research topic in digital signal processing and has recently found important applications in dna microarray time series data analysis. many spectral estimation methods have been proposed in the past decades, including the modified periodogram, the autoregressive model, the music algorithm and the multitaper method. although all these algorithms have their own advantages, they were all developed based on a basic assumption: the input signal is evenly sampled. however, in many real-world applications, the data can be unevenly sampled. for example, in dna microarray gene expression experiments, a time series may be obtained with different sampling intervals. furthermore, an evenly sampled time series may contain missing values due to corruption or absence of some expression measurements. a time series with missing values can be considered as an unevenly sampled time series in general. recently, several methods for detecting periodic gene expression have been proposed. lu et al. have proposed a periodic-normal mixture model to fit transcription profiles of periodically expressed genes in cell cycle microarray experiments. ahdesmäki et al. proposed a general-purpose robust testing procedure for finding periodic sequences in multiple time series data, which is based on a robust spectral estimator that is incorporated into a hypothesis testing framework using the so-called g-statistic together with correction for multiple testing. chen proposed a statistical inference approach, the c&g procedure, to effectively detect statistically significant periodically expressed genes based on two statistical hypothesis testing procedures. wichert et al. proposed to use the average periodogram as an exploratory tool to detect the presence of possible periodic genes and give an exact statistical test to determine whether or not a sinusoid is presence. luan and li proposed to use the shape-invariant model combined with a cubic b-spline estimation to model periodic gene expression profiles. ruf is one of the first to treat evenly sampled gene expression time series with missing values as unevenly sampled data for spectral analysis using the lomb-scargle periodogram. bohn et al. have used the lomb-scargle periodogram in their attempt to detect rhythmic components in the circadian cycle of the crassulacean acid metabolism plants. glynn et al. also used the lomb-scargle periodogram to detect periodic patterns in unevenly spaced gene expression time series. the lomb-scargle periodogram produces better results on unevenly sampled data than the classical fourier transform method since it weights the data on a "per point" basis instead of on a "per time interval" basis. lomb proved that this periodogram is the same as the classical periodogram in the case of equally spaced data. however, since the lomb-scargle method assumes that there is a single stationary sinusoid wave with infinite support, it introduces spurious periodic components in the periodogram for data with a finite length. also, due to the effect of noise in the data, it may produce inaccurate estimation results. in this paper, we propose a new spectral estimation technique for unevenly sampled data. our method models the signal in a shift-invariant signal space, for which many theories and algorithms are available. in our method, a direct spectral estimation formula is derived based on the b-spline basis that has finite support. experiments on simulated noisy periodic signals show that our algorithm is more accurate in detecting periodicity compared to the lomb-scargle algorithm.  our method is based on signal reconstruction in a shift-invariant signal space, where a direct spectral estimation procedure is developed using the b-spline basis. the details of the reconstruction algorithm and the power spectrum density estimation are given in the method section. simulated data we first test our spectral estimation algorithm on simulated signals to compare the estimation accuracy with the lomb-scargle method. a cosine curve has been used to represent the ideal expression of a gene that goes from an "on" state, to an "off" state, and then back to "on". for a gene g and expression level observed at time ti, we denote the time series by yg, where ygβcos⁡+εg mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgzbqwdawgaawcbagaem4zacgabeaakiabcicaoiabdsha0naabaaaleaacqwgpbqaaeqaaogaeiykakcccigae8nsdimagi4yammaei4ba8maei4camnaeiikagyaasaaaeaacqqg0baddawgaawcbagaeeyaakgabeaakiab=b8awbqaaiabigdaxiabikdayaaacqggpaqkcqghrawkcqwf1oqzdawgaawcbagaee4zacgabeaakiabcicaoiabdsha0naabaaaleaacqwgpbqaaeqaaogaeiykakcaaa@4b11@ for i =...,n and g =...,g. our test data consists of simulated time series data for the expression of g = genes, where of them are random genes and are noisy periodic genes. to obtain this dataset, the time series is first evenly sampled at points. that is, ti = i,. then, time points are randomly deleted from each time series to simulate the uneven sampling situation. in the second simulation test, we use the simulated noisy periodic gene profiles and compare our method with the lomb-scargle approach in terms of errors in the dominant frequency. in figure we show the mean-square error in dominant frequency under various percentages of presence entries. from figure we observe that our method is better than the lomb-scargle method. finally, we use the entire simulated genes and the false discovery rate gene selection strategy using g-statistic to test the accuracy and sensitivity of our method. lomb-scargle's test is used for lomb-scargle method. we added artificial gaussian noise with mean μ = and various sd values. in table we compare the effectiveness of the two methods in detecting periodic gene expressions with different missing ratios and various noise levels under the same false discovery rate q. from table we find that our method is better than the lomb-scargle method in detecting periodic expressions with various missing ratios. our method is also more robust than the lomb-scargle method under different noise levels. the simulated data consists of time series. the total number of periodic genes is p is the number of periodic genes that are statistically significant for a fdr level of q =. the number of false positives fp can be computed as fp = q*tp/, where tp is the number of true positives. keeping q at a fixed level ensures that we do not sacrifice specificity for sensitivity. experimental data plasmodium falciparum we have tested our algorithm on the gene expression data of plasmodium falciparum, which is one of the species that cause human malaria. the gene expression time series from the asexual intraerythrocytic developmental cycle of plasmodium falciparum are strongly periodic. identifying periodically expressed genes is useful for understanding the genome of plasmodium falciparum and designing effective vaccines for prevention of human malaria. in the gene expression database from bozdech et al., data values at the 23rd and the 29th hours are completely missing. an example of a gene expression profiles from the database is shown in figure and its periodograms obtained by using the lomb-scargle algorithm and our algorithm are shown in figure the frequencies corresponding to the peaks in the periodograms obtained by using the lomb-scargle method and our method are 1/ hz and 1/ hz, respectively. another example is shown in figure the frequencies corresponding to the peaks in the periodograms obtained by using the lomb-scargle method and our method are 1/ hz and 1/ hz, respectively ). we can see from these diagrams that our algorithm can effectively reduce the spurious oscillation components in the spectra. the plasmodium falciparum dataset was analyzed by bozdech et al. using the fast fourier transform, and later by glynn et al. using the lomb-scargle algorithm. bozdech et al. identified periodic genes in the quality control dataset of plasmodium falciparum, while glynn et al. found periodic genes in the complete dataset of. our analysis has shown that the number of periodic profiles in the complete dataset should be around to our estimate is based on analyzing the trend of the sorted g-statistic in method) as shown in figure the intersection of the two distinct slopes points indicates a sudden change in the g-statistic trend. nevertheless, no distinct cut-off between periodic/aperiodic profiles can be identified here. figure shows the histogram plot of the g-statistic. note that a profile with larger g-statistic value implies it is much more likely to be periodic. we see that many of the profiles are likely to be periodic. no distinct valley can be observed in the histogram, indicating that a cut-off for periodicity/aperiodicity is difficult to be obtained here. we also examine the periods of the profiles, and figure shows the histogram plot. it can be seen that there is a prominent period of hours with a count of around profiles. this result agreed largely with that of bozdech et al. and that of glynn et al.. nevertheless, our result also shows a much less prominent peak at a period of hours with a low count of around profiles. in figure we show the top ranking profiles, they can be seen to be highly periodic. in figure 6–, we show the profiles that ranked around and respectively. even at around a ranking of some profiles can still be judged to be somewhat periodic. we provide a ranked list of the profiles in additional file yeast spectral analysis is useful for the identification of cell-cycle-regulated genes. spellman et al. monitored genome-wide mrna levels for yeast orfs simultaneously using several different methods of synchronization including an α -factor-mediated g arrest which covers approximately two cell-cycle periods with measurements at min intervals for min with a total of time points, a temperature-sensitive cdc mutation to induce a reversible m-phase arrest, and a temperature-sensitive cdc mutation to arrest cells in g phase reversibly, and finally, an elutriation synchronization to produce the elutriation dataset of time points. for the cdc experiment, gene expression data were measured every min for min, lacking observations for the and min time points, and gives a total of time points. for the cdc experiment, samples were taken every min from to min for a total of time points. these four microarray datasets have spawned a large body of work on the gene expressions of the yeast cell cycle. spellman originally identified a total of cell-cycle genes in all four datasets, while wichert et al. claimed cyclic genes in alpha, cyclic genes in cdc in cdc and in elutriation by using g-statistic as the test statistic. chen detected cyclic genes in alpha, cyclic genes in cdc in cdc and in elutriation by using the same g-statistic as the test statistic under the same fdr threshold level. however, we found that the fisher p-value ) computed using the g-statistic has weak statistical power with such a short signal length. instead, we analyze the four yeast datasets for periodicity and rank the gene expression profiles according to their g-statistic. figure 7– show the histogram distributions of g-statistic values for the four datasets. we see that there is a continuum of distribution and a clear cutoff for periodicity/aperiodicity cannot be identified. the sorted g-statistic plots in figure 8– also supported such an observation. hence, a ranking of the gene expression profiles would be much more informative than just giving an ad-hoc estimate of the number of periodic genes. as pointed out by lichtenberg et al., there is a remarkably poor agreement between the numbers of periodically expressed genes detected by various computational methods. to enable a more objective comparison between the performances of different algorithms, they proposed three benchmark sets b b and b. set b contains a total of genes previously identified as periodically expressed in small-scale experiments. set b contains genes whose promoters were bound by at least one of the known cell cycle transcription factors in two chromatin ip studies, and therefore many of the genes in this benchmark set should be expected to be cell cycle regulated. set b contains genes annotated in mips as "cell cycle and dna processing". however, since a large number of genes involved in the cell cycle are not subjected to transcriptional regulation and genes found in b were explicitly removed, only a small fraction of the genes in b are expected to be periodically expressed. they define a good method as one that is able to reproduce precious findings, extract genes whose promoters are associated with known cell cycle transcription factors, or enriched for genes that play a role in the cell cycle. a detail investigation of the expression profiles in the benchmark sets shows that the generally low coverage is really due to the absence of periodicity in many of the profiles. in figure 11–, we plotted the ranking of the genes in the benchmark sets against the overall ranking in the four datasets. we see that a large portion of the profiles in the benchmark sets is ranked very low in the four datasets. a close examination of these profiles confirms that they are nearly random with no observable periodicity. there could be two possible causes for this: a large number of genes involved in the cell cycle are not directly transcription-regulated and therefore not periodic; the genes are really periodic but experimental artifacts and noise has corrupted their profiles. hence, for these profiles, it is expected that no algorithms would be able to identify them as periodic based on just a periodicity score. in, the strength of regulation is an important criterion for the detection of periodically expressed genes. regulation strength was not used as a criterion by our method in detecting profile periodicity since the g-statistic value given by equation gives a normalized periodic score. based on the periodicity criterion alone, our method has comparable performance with for the alpha and cdc experiments. for the cdc experiment, our result is notably inferior. however, if we look at the cdc profiles as shown in figure we see that even the high ranking profiles are very noisy, and hence the comparison for cdc have lower reliability with regard to periodicity behavior. when regulation strength is taken into consideration as well, the results of clearly out-performance our results for the b dataset. this is not surprising since it was pointed out in that the benchmark datasets b and b are biased towards periodic genes which are strongly regulated. in fact, it was observed in that regulation strength alone outperforms pure periodicity score for the alpha factor experiment on both b and b datasets. however, for the b dataset, taking regulation strength into account actually gives inferior results for all three experiments. as noted by, the b dataset is likely to be biased toward small amplitude genes. this suggests that regulation strength is only helpful in situations where genes involved in the cell cycle are also significantly regulated. it would not be useful in situations where genes are highly regulated but are not involved directly in cell cycle process. the three benchmark datasets are also analyzed in. both the method of and our method considered only periodicity as the sole criterion. we cited their results in figure comparing their results with our results as shown in figure we see that for the alpha factor experiment, our results is better for b comparable with theirs for b and inferior for b for the cdc experiment, our results are better for all three benchmark datasets. for this experiment, it is interesting to note that although our results are notably inferior to that of, they are significantly better than that of. for the cdc experiment, our results are better for b while comparable for b and b the above comparative study indicates the difficulty in making general performance comparison between different algorithms even with benchmark datasets due to the differences in dataset characteristic.  in this paper, we have proposed a new spectral estimation algorithm based on a signal reconstruction technique in an unevenly sampled space. the advantage of our algorithm over the lomb-scargle spectral estimation method is that the new algorithm can effectively reduce the effects of noise and spurious oscillation components and therefore improve the estimation accuracy. experiments on simulated signals and real gene expression data show that our method is effective in identifying periodically expressed genes. finally, we remark that this paper focuses on the improvement of periodicity estimation accuracy using spectral analysis algorithms. another important issue is the statistical significance of the periodicity of a time series. interested readers are referred to chen, wichert et al. and glynn et al., who have used hypothesis testing to address this problem. 
however, since the lomb-scargle method assumes that there is a single stationary sinusoid wave with infinite support, it introduces spurious periodic components in the periodogram for data with a finite length. such challenge occurs due to the fact that the observed time series usually exhibit non-idealities, such as noise, short length, and unevenly sampled time points. we have proposed an effective method for identifying periodic genes in unevenly sampled space of microarray time series gene expression data. recently, the lomb-scargle algorithm has been applied to unevenly sampled gene expression data for spectral estimation. in this paper, we propose a new spectral estimation algorithm for unevenly sampled gene expression data. we have applied our algorithm to the plasmodium falciparum and yeast gene expression data and the results show that the algorithm is able to detect biologically meaningful periodically expressed genes. the new method is based on signal reconstruction in a shift-invariant signal space, where a direct spectral estimation procedure is developed using the b-spline basis. a new challenge for analyzing the microarray time series data is to identify genes that are periodically expressed. most methods used in the literature operate on evenly sampled time series and are not suitable for unevenly sampled time series. the method can also be used as an effective tool for gene expression time series interpolation or resampling. experiments on simulated noisy gene expression profiles show that our algorithm is superior to the lomb-scargle algorithm and the classical fourier periodogram based method in detecting periodically expressed genes.
 periodogram analysis of time-series is widespread in biology. a new challenge for analyzing the microarray time series data is to identify genes that are periodically expressed. such challenge occurs due to the fact that the observed time series usually exhibit non-idealities, such as noise, short length, and unevenly sampled time points. most methods used in the literature operate on evenly sampled time series and are not suitable for unevenly sampled time series.  for evenly sampled data, methods based on the classical fourier periodogram are often used to detect periodically expressed gene. recently, the lomb-scargle algorithm has been applied to unevenly sampled gene expression data for spectral estimation. however, since the lomb-scargle method assumes that there is a single stationary sinusoid wave with infinite support, it introduces spurious periodic components in the periodogram for data with a finite length. in this paper, we propose a new spectral estimation algorithm for unevenly sampled gene expression data. the new method is based on signal reconstruction in a shift-invariant signal space, where a direct spectral estimation procedure is developed using the b-spline basis. experiments on simulated noisy gene expression profiles show that our algorithm is superior to the lomb-scargle algorithm and the classical fourier periodogram based method in detecting periodically expressed genes. we have applied our algorithm to the plasmodium falciparum and yeast gene expression data and the results show that the algorithm is able to detect biologically meaningful periodically expressed genes.  we have proposed an effective method for identifying periodic genes in unevenly sampled space of microarray time series gene expression data. the method can also be used as an effective tool for gene expression time series interpolation or resampling. 