{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T02:42:13Z","timestamp":1768272133072,"version":"3.49.0"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Local similarity analysis of biological time series data helps elucidate the varying dynamics of biological systems. However, its applications to large scale high-throughput data are limited by slow permutation procedures for statistical significance evaluation.<\/jats:p>\n               <jats:p>Results: We developed a theoretical approach to approximate the statistical significance of local similarity analysis based on the approximate tail distribution of the maximum partial sum of independent identically distributed (i.i.d.) random variables. Simulations show that the derived formula approximates the tail distribution reasonably well (starting at time points with no delay and with delay) and provides P-values comparable with those from permutations. The new approach enables efficient calculation of statistical significance for pairwise local similarity analysis, making possible all-to-all local association studies otherwise prohibitive. As a demonstration, local similarity analysis of human microbiome time series shows that core operational taxonomic units (OTUs) are highly synergetic and some of the associations are body-site specific across samples.<\/jats:p>\n               <jats:p>Availability: The new approach is implemented in our eLSA package, which now provides pipelines for faster local similarity analysis of time series data. The tool is freely available from eLSA\u2019s website: http:\/\/meta.usc.edu\/softs\/lsa.<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <jats:p>Contact: \u00a0fsun@usc.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts668","type":"journal-article","created":{"date-parts":[[2012,11,25]],"date-time":"2012-11-25T01:24:07Z","timestamp":1353806647000},"page":"230-237","source":"Crossref","is-referenced-by-count":121,"title":["Efficient statistical significance approximation for local similarity analysis of high-throughput time series data"],"prefix":"10.1093","volume":"29","author":[{"given":"Li C.","family":"Xia","sequence":"first","affiliation":[{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."}]},{"given":"Dongmei","family":"Ai","sequence":"additional","affiliation":[{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."},{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."}]},{"given":"Jacob","family":"Cram","sequence":"additional","affiliation":[{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."}]},{"given":"Jed A.","family":"Fuhrman","sequence":"additional","affiliation":[{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."}]},{"given":"Fengzhu","family":"Sun","sequence":"additional","affiliation":[{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."},{"name":"1 Molecular and Computational Biology Program, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-2910, USA, 2Department of Information and Computational Sciences, University of Science and Technology Beijing, Beijing, 100083, China, 3Marine and Environmental Biology, Department of Biological Sciences, University of Southern California, Los Angeles, CA 90089-0371, USA and 4TNLIST\/Department of Automation, Tsinghua University, Beijing, China."}]}],"member":"286","published-online":{"date-parts":[[2012,11,23]]},"reference":[{"key":"2023012810164134300_bts668-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023012810164134300_bts668-B2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1146\/annurev.bioeng.9.060906.151904","article-title":"Analysis of time-series gene expression data: methods, challenges, and opportunities","volume":"9","author":"Androulakis","year":"2007","journal-title":"Annu. Rev. Biomed. Eng."},{"key":"2023012810164134300_bts668-B3","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1093\/bioinformatics\/bti095","article-title":"Clustering of gene expression data using a local shape-based similarity measure","volume":"21","author":"Balasubramaniyan","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012810164134300_bts668-B4","doi-asserted-by":"crossref","first-page":"2493","DOI":"10.1093\/bioinformatics\/bth283","article-title":"Analyzing time series gene expression data","volume":"20","author":"Bar-Joseph","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012810164134300_bts668-B5","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1038\/ismej.2010.204","article-title":"Co-occurrence patterns for abundant marine archaeal and bacterial lineages in the deep chlorophyll maximum of coastal california","volume":"5","author":"Beman","year":"2011","journal-title":"ISME J."},{"key":"2023012810164134300_bts668-B6","doi-asserted-by":"crossref","first-page":"R50","DOI":"10.1186\/gb-2011-12-5-r50","article-title":"Moving pictures of the human microbiome","volume":"12","author":"Caporaso","year":"2011","journal-title":"Genome Biol."},{"key":"2023012810164134300_bts668-B7","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1101\/gr.104521.109","article-title":"A global network of coexisting microbes from environmental and whole-genome sequence data","volume":"20","author":"Chaffron","year":"2010","journal-title":"Genome Res."},{"key":"2023012810164134300_bts668-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-4149(03)00061-9","article-title":"Asymptotic behavior of the local score of independent and identically distributed random sequences","volume":"107","author":"Daudin","year":"2003","journal-title":"Stoch. Proc. Appl."},{"key":"2023012810164134300_bts668-B28","doi-asserted-by":"crossref","first-page":"S3","DOI":"10.1186\/1471-2164-14-S1-S3","article-title":"Expanding the boundaries of local similarity analysis","volume":"14","author":"Durno","year":"2013","journal-title":"BMC Genomics"},{"key":"2023012810164134300_bts668-B9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1023\/B:MCAP.0000026559.87023.ec","article-title":"Approximation of the distribution of the supremum of a centered random walk application to the local score","volume":"6","author":"Etienne","year":"2004","journal-title":"Methodol. Comput. Appl."},{"key":"2023012810164134300_bts668-B10","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1214\/aoms\/1177729589","article-title":"The asymptotic distribution of the range of sums of independent random variables","volume":"22","author":"Feller","year":"1951","journal-title":"Ann. Math. Stat."},{"key":"2023012810164134300_bts668-B11","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1038\/ismej.2011.107","article-title":"Defining seasonal marine microbial community dynamics","volume":"6","author":"Gilbert","year":"2011","journal-title":"ISME J."},{"key":"2023012810164134300_bts668-B12","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1186\/1471-2105-7-69","article-title":"In search of functional association from time-series microarray data based on the change trend and level of gene expression","volume":"7","author":"He","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023012810164134300_bts668-B13","first-page":"247","article-title":"Oligonucleotide profiling for discriminating bacteria in bacterial communities","volume":"10","author":"He","year":"2007","journal-title":"Comb. Chem. High T. Scr."},{"key":"2023012810164134300_bts668-B14","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1093\/bioinformatics\/bti026","article-title":"Identifying time-lagged gene clusters using gene expression data","volume":"21","author":"Ji","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012810164134300_bts668-B15","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1214\/aos\/1176347616","article-title":"Statistical composition of high-scoring segments from molecular sequences","volume":"18","author":"Karlin","year":"1990","journal-title":"Ann. Stat."},{"key":"2023012810164134300_bts668-B16","doi-asserted-by":"crossref","first-page":"5873","DOI":"10.1073\/pnas.90.12.5873","article-title":"Applications and statistics for multiple high-scoring segments in molecular sequences","volume":"90","author":"Karlin","year":"1993","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810164134300_bts668-B17","doi-asserted-by":"crossref","first-page":"16875","DOI":"10.1073\/pnas.252466999","article-title":"Genome-wide coexpression dynamics: theory and application","volume":"99","author":"Li","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012810164134300_bts668-B18","doi-asserted-by":"crossref","first-page":"3017","DOI":"10.1093\/bioinformatics\/bti448","article-title":"False discovery rate, sensitivity and sample size for microarray studies","volume":"21","author":"Pawitan","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012810164134300_bts668-B19","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1006\/jmbi.2000.5219","article-title":"Beyond synexpression relationships: local clustering of time-shifted and inverted gene expression profiles identifies new, biologically relevant interactions","volume":"314","author":"Qian","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023012810164134300_bts668-B20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511806384","volume-title":"Experimental Design and Data Analysis for Biologists","author":"Quinn","year":"2002"},{"key":"2023012810164134300_bts668-B21","doi-asserted-by":"crossref","first-page":"2532","DOI":"10.1093\/bioinformatics\/btl417","article-title":"Local similarity analysis reveals unique associations among marine bacterioplankton species and environmental factors","volume":"22","author":"Ruan","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012810164134300_bts668-B22","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1111\/j.1462-2920.2009.02087.x","article-title":"Differential bacterial dynamics promote emergent community robustness to lake mixing: an epilimnion to hypolimnion transplant experiment","volume":"12","author":"Shade","year":"2010","journal-title":"Environ. Microbiol."},{"key":"2023012810164134300_bts668-B23","first-page":"1","article-title":"A method of establishing groups of equal amplitude in plant sociology based on similarity of species content","volume":"4","author":"Sorensen","year":"1948","journal-title":"Biol. Krifter Bd."},{"key":"2023012810164134300_bts668-B24","doi-asserted-by":"crossref","first-page":"3273","DOI":"10.1091\/mbc.9.12.3273","article-title":"Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces Cerevisiae by microarray hybridization","volume":"9","author":"Spellman","year":"1998","journal-title":"Mol. Biol. Cell"},{"key":"2023012810164134300_bts668-B25","doi-asserted-by":"crossref","first-page":"1414","DOI":"10.1038\/ismej.2011.24","article-title":"Marine bacterial, archaeal and protistan association networks reveal ecological linkages","volume":"5","author":"Steele","year":"2011","journal-title":"ISME J."},{"key":"2023012810164134300_bts668-B26","doi-asserted-by":"crossref","first-page":"e27992","DOI":"10.1371\/journal.pone.0027992","article-title":"Accurate genome relative abundance estimation based on shotgun metagenomic reads","volume":"6","author":"Xia","year":"2011","journal-title":"PLoS One"},{"key":"2023012810164134300_bts668-B27","doi-asserted-by":"crossref","first-page":"S15","DOI":"10.1186\/1752-0509-5-S2-S15","article-title":"Extended local similarity analysis (elsa) of microbial community and other time series data with replicates","volume":"5","author":"Xia","year":"2011","journal-title":"BMC Syst. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/2\/230\/48888746\/bioinformatics_29_2_230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/2\/230\/48888746\/bioinformatics_29_2_230.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T11:27:48Z","timestamp":1674905268000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/2\/230\/202138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,23]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts668","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,1,15]]},"published":{"date-parts":[[2012,11,23]]}}}