{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T05:28:21Z","timestamp":1768886901487,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"S1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Genomics"],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Pairwise comparison of time series data for both local and time-lagged relationships is a computationally challenging problem relevant to many fields of inquiry. The Local Similarity Analysis (LSA) statistic identifies the existence of local and lagged relationships, but determining significance through a <jats:italic>p<\/jats:italic>-value has been algorithmically cumbersome due to an intensive permutation test, shuffling rows and columns and repeatedly calculating the statistic. Furthermore, this <jats:italic>p<\/jats:italic>-value is calculated with the assumption of normality -- a statistical luxury dissociated from most real world datasets.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>To improve the performance of LSA on big datasets, an asymptotic upper bound on the <jats:italic>p<\/jats:italic>-value calculation was derived without the assumption of normality. This change in the bound calculation markedly improved computational speed from <jats:italic>O<\/jats:italic>(<jats:italic>pm<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              <jats:italic>n<\/jats:italic>) to <jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              <jats:italic>n<\/jats:italic>), where <jats:italic>p<\/jats:italic> is the number of permutations in a permutation test, <jats:italic>m<\/jats:italic> is the number of time series, and <jats:italic>n<\/jats:italic> is the length of each time series. The bounding process is implemented as a computationally efficient software package, <jats:sc>FAST<\/jats:sc> LSA, written in C and optimized for threading on multi-core computers, improving its practical computation time. We computationally compare our approach to previous implementations of LSA, demonstrate broad applicability by analyzing time series data from public health, microbial ecology, and social media, and visualize resulting networks using the Cytoscape software.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The <jats:sc>FAST<\/jats:sc> LSA software package expands the boundaries of LSA allowing analysis on datasets with millions of co-varying time series. Mapping metadata onto force-directed graphs derived from <jats:sc>FAST<\/jats:sc> LSA allows investigators to view correlated cliques and explore previously unrecognized network relationships. The software is freely available for download at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.cmde.science.ubc.ca\/hallam\/fastLSA\/\" ext-link-type=\"uri\">http:\/\/www.cmde.science.ubc.ca\/hallam\/fastLSA\/<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2164-14-s1-s3","type":"journal-article","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T15:16:26Z","timestamp":1358781386000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Expanding the boundaries of local similarity analysis"],"prefix":"10.1186","volume":"14","author":[{"given":"W Evan","family":"Durno","sequence":"first","affiliation":[]},{"given":"Niels W","family":"Hanson","sequence":"additional","affiliation":[]},{"given":"Kishori M","family":"Konwar","sequence":"additional","affiliation":[]},{"given":"Steven J","family":"Hallam","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,21]]},"reference":[{"issue":"7209","key":"4618_CR1","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1038\/455028a","volume":"455","author":"C Lynch","year":"2008","unstructured":"Lynch C: Big data: How do your data grow?. Nature. 2008, 455 (7209): 28-29. 10.1038\/455028a.","journal-title":"Nature"},{"issue":"5919","key":"4618_CR2","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.1170411","volume":"323","author":"G Bell","year":"2009","unstructured":"Bell G, Hey T, Szalay A: Computer science. Beyond the data deluge. Science. 2009, 323 (5919): 1297-1298. 10.1126\/science.1170411.","journal-title":"Science"},{"issue":"9","key":"4618_CR3","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1038\/nrg2857","volume":"11","author":"EE Schadt","year":"2010","unstructured":"Schadt EE, Linderman MD, Sorenson J, Lee L, Nolan GP: Computational solutions to large-scale data management and analysis. Nature Reviews Genetics. 2010, 11 (9): 647-657. 10.1038\/nrg2857.","journal-title":"Nature Reviews Genetics"},{"issue":"10","key":"4618_CR4","doi-asserted-by":"publisher","first-page":"4479","DOI":"10.1128\/AEM.67.10.4479-4487.2001","volume":"67","author":"L Ranjard","year":"2001","unstructured":"Ranjard L, Poly F, Lata JC, Mougel C, Thioulouse J, Nazaret S: Characterization of bacterial and fungal soil communities by automated ribosomal intergenic spacer analysis fingerprints: biological and methodological variability. Applied and Environmental Microbiology. 2001, 67 (10): 4479-4487. 10.1128\/AEM.67.10.4479-4487.2001.","journal-title":"Applied and Environmental Microbiology"},{"key":"4618_CR5","first-page":"1056","volume-title":"Limnology and Oceanography","author":"BASV Mooy","year":"2004","unstructured":"Mooy BASV, Devol AH, Keil RG: Relationship between bacterial community structure, light, and carbon cycling in the eastern subarctic North Pacific. Limnology and Oceanography. 2004, 1056-1062."},{"issue":"20","key":"4618_CR6","doi-asserted-by":"publisher","first-page":"2532","DOI":"10.1093\/bioinformatics\/btl417","volume":"22","author":"Q Ruan","year":"2006","unstructured":"Ruan Q, Dutta D, Schwalbach MS, Steele JA, Fuhrman JA, Sun F: Local similarity analysis reveals unique associations among marine bacterioplankton species and environmental factors. Bioinformatics. 2006, 22 (20): 2532-2538. 10.1093\/bioinformatics\/btl417.","journal-title":"Bioinformatics"},{"issue":"Suppl 2","key":"4618_CR7","doi-asserted-by":"publisher","first-page":"S15","DOI":"10.1186\/1752-0509-5-S2-S15","volume":"5","author":"LC Xia","year":"2011","unstructured":"Xia LC, Steele JA, Cram JA, Cardon ZG, Simmons SL, Vallino JJ, Fuhrman JA, Sun F: Extended local similarity analysis (eLSA) of microbial community and other time series data with replicates. BMC Syst Biol. 2011, 5 (Suppl 2): S15-10.1186\/1752-0509-5-S2-S15.","journal-title":"BMC Syst Biol"},{"key":"4618_CR8","doi-asserted-by":"publisher","first-page":"R50","DOI":"10.1186\/gb-2011-12-5-r50","volume":"12","author":"JG Caporaso","year":"2011","unstructured":"Caporaso JG, Lauber CL, Costello EK, Berg-Lyons D, Gonzalez A, Stombaugh J, Knights D, Gajer P, Ravel J, Fierer N, Gordon JI, Knight R: Moving pictures of the human microbiome. Genome Biol. 2011, 12: R50-10.1186\/gb-2011-12-5-r50.","journal-title":"Genome Biol"},{"issue":"12","key":"4618_CR9","doi-asserted-by":"publisher","first-page":"3273","DOI":"10.1091\/mbc.9.12.3273","volume":"9","author":"PT Spellman","year":"1998","unstructured":"Spellman PT, Sherlock G, Zhang MQ, Iyer VR, Anders K, Eisen MB, Brown PO, Botstein D, Futcher B: Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces cerevisiae by microarray hybridization. Molecular Biology of the Cell. 1998, 9 (12): 3273-3297. 10.1091\/mbc.9.12.3273.","journal-title":"Molecular Biology of the Cell"},{"key":"4618_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/1935826.1935863","volume-title":"Proceedings of the Fourth ACM International Conference on Web Search and Data Mining","author":"J Yang","year":"2011","unstructured":"Yang J, Leskovec J: Patterns of temporal variation in online media. Proceedings of the Fourth ACM International Conference on Web Search and Data Mining. 2011, 177-186."},{"issue":"11","key":"4618_CR11","doi-asserted-by":"publisher","first-page":"2498","DOI":"10.1101\/gr.1239303","volume":"13","author":"P Shannon","year":"2003","unstructured":"Shannon P, Markiel A, Ozier O, Baliga NS, Wang JT, Ramage D, Amin N, Schwikowski B, Ideker T: Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Research. 2003, 13 (11): 2498-2504. 10.1101\/gr.1239303.","journal-title":"Genome Research"},{"key":"4618_CR12","doi-asserted-by":"publisher","first-page":"344","DOI":"10.2307\/1426323","volume":"2","author":"L Takacs","year":"1970","unstructured":"Takacs L: On the distribution of the maximum of sums of mutually independent and identically distributed random variables. Advances in Applied Probability. 1970, 2: 344-354. 10.2307\/1426323.","journal-title":"Advances in Applied Probability"},{"key":"4618_CR13","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1090\/S0002-9904-1948-09021-8","volume":"54","author":"A Wald","year":"1948","unstructured":"Wald A: On the distribution of the maximum of successive cumulative sum of independent but not identically distributed chance variables. Bulletin of the American Mathematical Society. 1948, 54: 422-430. 10.1090\/S0002-9904-1948-09021-8.","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"4","key":"4618_CR14","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/1114083","volume":"14","author":"VB Nevzorov","year":"1969","unstructured":"Nevzorov VB, Petrov VV: On the distribution of the maximum cumulative sum of independent random variables. Theory of Probability and its Applications. 1969, 14 (4): 682-687. 10.1137\/1114083.","journal-title":"Theory of Probability and its Applications"},{"key":"4618_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01494395","volume":"15","author":"J Lindeberg","year":"1922","unstructured":"Lindeberg J: Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift. 1922, 15: 211-225. 10.1007\/BF01494395.","journal-title":"Mathematische Zeitschrift"},{"key":"4618_CR16","doi-asserted-by":"publisher","first-page":"69","DOI":"10.3354\/ame01222","volume":"53","author":"JA Fuhrman","year":"2008","unstructured":"Fuhrman JA, Steele JA: Community structure of marine bacterioplankton: patterns, networks, and relationships to function. Aquatic Microbial Ecology. 2008, 53: 69-81.","journal-title":"Aquatic Microbial Ecology"},{"issue":"9","key":"4618_CR17","doi-asserted-by":"publisher","first-page":"1414","DOI":"10.1038\/ismej.2011.24","volume":"5","author":"JA Steele","year":"2011","unstructured":"Steele JA, Countway PD, Xia L, Vigil PD, Beman JM, Kim DY, Chow CET, Sachdeva R, Jones AC, Schwalbach MS, Rose JM, Hewson I, Patel A, Sun F, Caron DA, Fuhrman JA: Marine bacterial, archaeal and protistan association networks reveal ecological linkages. The ISME Journal. 2011, 5 (9): 1414-1425. 10.1038\/ismej.2011.24.","journal-title":"The ISME Journal"},{"key":"4618_CR18","doi-asserted-by":"publisher","first-page":"D700","DOI":"10.1093\/nar\/gkr1029","volume":"40","author":"JM Cherry","year":"2012","unstructured":"Cherry JM, Hong EL, Amundsen C, Balakrishnan R, Binkley G, Chan ET, Christie KR, Costanzo MC, Dwight SS, Engel SR, Fisk DG, Hirschman JE, Hitz BC, Karra K, Krieger CJ, Miyasato SR, Nash RS, Park J, Skrzypek MS, Simison M, Weng S, Wong ED: Saccharomyces Genome Database: the genomics resource of budding yeast. Nucleic Acids Res. 2012, 40: D700-D705. 10.1093\/nar\/gkr1029.","journal-title":"Nucleic Acids Res"},{"key":"4618_CR19","doi-asserted-by":"publisher","first-page":"6040","DOI":"10.1074\/jbc.M708248200","volume":"283","author":"M Ashe","year":"2007","unstructured":"Ashe M, deBruin RA, Kalashnikova T, McDonald WJ, Yates JR, Wittenberg C: The SBF- and MBF-associated protein Msa1 is required for proper timing of G1-specific transcription in Saccharomyces cerevisae. Journal of Biological Chemistry. 2007, 283: 6040-6049.","journal-title":"Journal of Biological Chemistry"},{"key":"4618_CR20","doi-asserted-by":"publisher","first-page":"2265","DOI":"10.1101\/gad.842100","volume":"14","author":"ME Ewen","year":"2000","unstructured":"Ewen ME: Where the cell cycle and histones meet. Genes Dev. 2000, 14: 2265-2270. 10.1101\/gad.842100.","journal-title":"Genes Dev"}],"container-title":["BMC Genomics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2164-14-S1-S3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:29:57Z","timestamp":1630531797000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcgenomics.biomedcentral.com\/articles\/10.1186\/1471-2164-14-S1-S3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":20,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["4618"],"URL":"https:\/\/doi.org\/10.1186\/1471-2164-14-s1-s3","relation":{},"ISSN":["1471-2164"],"issn-type":[{"value":"1471-2164","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]},"assertion":[{"value":"21 January 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S3"}}