title: Statistical significance approximation in local trend analysis of high-throughput time-series data using the theory of Markov chains.
abstract: BACKGROUND
  Local trend (i.e. shape) analysis of time series data reveals co-changing patterns in dynamics of biological systems. However, slow permutation procedures to evaluate the statistical significance of local trend scores have limited its applications to high-throughput time series data analysis, e.g., data from the next generation sequencing technology based studies.
  
  
  RESULTS
  By extending the theories for the tail probability of the range of sum of Markovian random variables, we propose formulae for approximating the statistical significance of local trend scores. Using simulations and real data, we show that the approximate p-value is close to that obtained using a large number of permutations (starting at time points >20 with no delay and >30 with delay of at most three time steps) in that the non-zero decimals of the p-values obtained by the approximation and the permutations are mostly the same when the approximate p-value is less than 0.05. In addition, the approximate p-value is slightly larger than that based on permutations making hypothesis testing based on the approximate p-value conservative. The approximation enables efficient calculation of p-values for pairwise local trend analysis, making large scale all-versus-all comparisons possible. We also propose a hybrid approach by integrating the approximation and permutations to obtain accurate p-values for significantly associated pairs. We further demonstrate its use with the analysis of the Polymouth Marine Laboratory (PML) microbial community time series from high-throughput sequencing data and found interesting organism co-occurrence dynamic patterns.
  
  
  BACKGROUND
  The software tool is integrated into the eLSA software package that now provides accelerated local trend and similarity analysis pipelines for time series data. The package is freely available from the eLSA website: http://bitbucket.org/charade/elsa.
authors.affiliation: Department of Medicine, Division of Oncology, Stanford University School of Medicine, Stanford, 94305-5151, CA, USA.|Department of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, 19104, PA, USA.
authors.forename: Li C
authors.initials: LC
authors.lastname: Xia
authors.affiliation: School of Mathematics and Physics, University of Science and Technology Beijing, Beijing, 100083, China.
authors.forename: Dongmei
authors.initials: D
authors.lastname: Ai
authors.affiliation: Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, 90089-0371, CA, USA.
authors.forename: Jacob A
authors.initials: JA
authors.lastname: Cram
authors.affiliation: School of Mathematics and Physics, University of Science and Technology Beijing, Beijing, 100083, China.
authors.forename: Xiaoyi
authors.initials: X
authors.lastname: Liang
authors.affiliation: Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, 90089-0371, CA, USA.
authors.forename: Jed A
authors.initials: JA
authors.lastname: Fuhrman
authors.affiliation: Molecular and Computational Biology, Department of Biological Sciences, University of Southern California, Los Angeles, 90089-2910, CA, USA. fsun@usc.edu.|Centre for Computational Systems Biology, Fudan University, Shanghai, 200433, China. fsun@usc.edu.
authors.forename: Fengzhu
authors.initials: F
authors.lastname: Sun
mesh_terms: D000465:Algorithms; D001419:Bacteria / Q000235:genetics*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D008390:Markov Chains; D011336:Probability; D012984:Software; D013997:Time Factors