{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T04:14:37Z","timestamp":1728360877076},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T00:00:00Z","timestamp":1115078400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T00:00:00Z","timestamp":1115078400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>Searching for small tandem\/disperse repetitive DNA sequences streamlines many biomedical research processes. For instance, whole genomic array analysis in yeast has revealed 22 PHO-regulated genes. The promoter regions of all but one of them contain at least one of the two core Pho4p binding sites, CACGTG and CACGTT. In humans, microsatellites play a role in a number of rare neurodegenerative diseases such as spinocerebellar ataxia type 1 (SCA1). SCA1 is a hereditary neurodegenerative disease caused by an expanded CAG repeat in the coding sequence of the gene. In bacterial pathogens, microsatellites are proposed to regulate expression of some virulence factors. For example, bacteria commonly generate intra-strain diversity through phase variation which is strongly associated with virulence determinants. A recent analysis of the complete sequences of the <jats:italic>Helicobacter pylori<\/jats:italic> strains 26695 and J99 has identified 46 putative phase-variable genes among the two genomes through their association with homopolymeric tracts and dinucleotide repeats. Life scientists are increasingly interested in studying the function of small sequences of DNA. However, current search algorithms often generate thousands of matches \u2013 most of which are irrelevant to the researcher.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We present our hash function as well as our search algorithm to locate small sequences of DNA within multiple genomes. Our system applies information retrieval algorithms to discover knowledge of cross-species conservation of repeat sequences. We discuss our incorporation of the Gene Ontology (GO) database into these algorithms. We conduct an exhaustive time analysis of our system for various repetitive sequence lengths. For instance, a search for eight bases of sequence within 3.224 GBases on 49 different chromosomes takes 1.147 seconds on average. To illustrate the relevance of the search results, we conduct a search with and without added annotation terms for the yeast Pho4p binding sites, CACGTG and CACGTT. Also, a cross-species search is presented to illustrate how potential hidden correlations in genomic data can be quickly discerned. The findings in one species are used as a catalyst to discover something new in another species. These experiments also demonstrate that our system performs well while searching multiple genomes \u2013 without the main memory constraints present in other systems.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>We present a time-efficient algorithm to locate small segments of DNA and concurrently to search the annotation data accompanying the sequence. Genome-wide searches for short sequences often return hundreds of hits. Our experiments show that subsequently searching the annotation data can refine and focus the results for the user. Our algorithms are also space-efficient in terms of main memory requirements. Source code is available upon request.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-111","type":"journal-article","created":{"date-parts":[[2005,5,4]],"date-time":"2005-05-04T06:13:46Z","timestamp":1115187226000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Refined repetitive sequence searches utilizing a fast hash function and cross species information retrievals"],"prefix":"10.1186","volume":"6","author":[{"given":"Jeff","family":"Reneker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chi-Ren","family":"Shyu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,3]]},"reference":[{"key":"436_CR1","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1093\/nar\/27.2.573","volume":"27","author":"G Benson","year":"1999","unstructured":"Benson G: Tandem repeat finder: a program to analyze DNA sequences. Nucleic Acids Research 1999, 27: 573\u2013580. 10.1093\/nar\/27.2.573","journal-title":"Nucleic Acids Research"},{"key":"436_CR2","doi-asserted-by":"publisher","first-page":"S5","DOI":"10.1093\/bioinformatics\/17.suppl_1.S5","volume":"17","author":"E Adebiyi","year":"2001","unstructured":"Adebiyi E, Jiang T, Kaufmann M: An efficient algorithm for finding short approximate non-tandem repeats. Bioinformatics 2001, 17: S5-S12.","journal-title":"Bioinformatics"},{"key":"436_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"G Landau","year":"2001","unstructured":"Landau G, Schmidt J, Sokol D: An algorithm for approximate tandem repeats. Journal of Computational Biology 2001, 8: 1\u201318. 10.1089\/106652701300099038","journal-title":"Journal of Computational Biology"},{"key":"436_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1093\/bioinformatics\/18.4.634","volume":"18","author":"A Castelo","year":"2002","unstructured":"Castelo A, Martins W, Gao G: TROLL \u2013 Tandem Repeat Occurrence Locator. Bioinformatics 2002, 18: 634\u2013636. 10.1093\/bioinformatics\/18.4.634","journal-title":"Bioinformatics"},{"key":"436_CR5","doi-asserted-by":"publisher","first-page":"3672","DOI":"10.1093\/nar\/gkg617","volume":"31","author":"R Kolpakov","year":"2003","unstructured":"Kolpakov R, Bana G, Kucherov G: mreps: efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Research 2003, 31: 3672\u20133678. 10.1093\/nar\/gkg617","journal-title":"Nucleic Acids Research"},{"key":"436_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S Altschul","year":"1990","unstructured":"Altschul S, Gish W, Miller W, Myers E, Lipman D: Basic local alignment search tool. Journal of Molecular Biology 1990, 215: 403\u2013410. 10.1006\/jmbi.1990.9999","journal-title":"Journal of Molecular Biology"},{"key":"436_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge, UK: Cambridge University Press; 1997."},{"key":"436_CR8","doi-asserted-by":"publisher","first-page":"S31","DOI":"10.1093\/bioinformatics\/18.suppl_1.S31","volume":"18","author":"A Hauth","year":"2002","unstructured":"Hauth A, Joseph D: Beyond tandem repeats: complex pattern structures and distant regions of similarity. Bioinformatics 2002, 18: S31-S37.","journal-title":"Bioinformatics"},{"key":"436_CR9","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"S Altschul","year":"1997","unstructured":"Altschul S, Madden T, Schaffer A, Zhang J, Zhang Z, Miller W, Lipman D: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research 1997, 25: 3389\u20133402. 10.1093\/nar\/25.17.3389","journal-title":"Nucleic Acids Research"},{"key":"436_CR10","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1101\/gr.194201","volume":"11","author":"Z Ning","year":"2001","unstructured":"Ning Z, Cox A, Mullikin J: SSAHA: A Fast Search Method for Large DNA Databases. Genome Research 2001, 11: 1725\u20131729. 10.1101\/gr.194201","journal-title":"Genome Research"},{"key":"436_CR11","volume-title":"Modern Information Retrieval","author":"R Baeza-Yates","year":"1999","unstructured":"Baeza-Yates R, Ribeiro-Neto B: Modern Information Retrieval. New York, NY: ACM Press; 1999."},{"issue":"4","key":"436_CR12","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1101\/gr.229202. Article published online before March 2002","volume":"12","author":"WJ Kent","year":"2002","unstructured":"Kent WJ: BLAT \u2013 the BLAST-like alignment tool. Genome Research 2002, 12(4):656\u2013664. 10.1101\/gr.229202. Article published online before March 2002","journal-title":"Genome Research"},{"key":"436_CR13","first-page":"353","volume-title":"Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, Bethesda, MD","author":"A Califano","year":"1993","unstructured":"Califano A, Rigoutsos I: FLASH: A fast look-up algorithm for string homology. Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, Bethesda, MD 1993, 353\u2013359."},{"issue":"1","key":"436_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1093\/bioinformatics\/14.1.55","volume":"14","author":"I Rigoutsos","year":"1998","unstructured":"Rigoutsos I, Floratos A: Combinatorial pattern discovery in biological sequences: the TEIRESAIS algorithm. Bioinformatics 1998, 14(1):55\u201367. 10.1093\/bioinformatics\/14.1.55","journal-title":"Bioinformatics"},{"key":"436_CR15","doi-asserted-by":"publisher","first-page":"4309","DOI":"10.1091\/mbc.11.12.4309","volume":"12","author":"N Ogawa","year":"2000","unstructured":"Ogawa N, DeRisi J, Brown P: New Components of a System for Phosphate Accumulation and Polyphosphate Metabolism in Saccharomyces cerevisiae Revealed by Genomic Expression Analysis. Molecular Biology Cell 2000, 12: 4309\u20134321.","journal-title":"Molecular Biology Cell"},{"key":"436_CR16","unstructured":"Advanced Content Match Engine for Sequences (ACMES)[http:\/\/acmes.rnet.missouri.edu\/]"},{"issue":"Web Server issu","key":"436_CR17","doi-asserted-by":"publisher","first-page":"W649","DOI":"10.1093\/nar\/gkh455","volume":"32","author":"J Reneker","year":"2004","unstructured":"Reneker J, Shyu CR, Zeng P, Polacco JC, Gassmann W: ACMES: fast multiple-genome searches for short repeat sequences with concurrent cross-species information retrieval. Nucleic Acids Research 2004, (32(Web Server issue)):W649\u201353.","journal-title":"Nucleic Acids Research"},{"key":"436_CR18","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1099\/mic.0.26993-0","volume":"150","author":"L Sala\u00fcn","year":"2004","unstructured":"Sala\u00fcn L, Linz B, Suerbaum S, Saunders N: The diversity within an expanded and redefined repertoire of phase-variable genes in Helicobacter pylori . Microbiology 2004, 150: 817\u2013830. 10.1099\/mic.0.26993-0","journal-title":"Microbiology"},{"issue":"20","key":"436_CR19","doi-asserted-by":"publisher","first-page":"11121","DOI":"10.1073\/pnas.93.20.11121","volume":"93","author":"D Hood","year":"1996","unstructured":"Hood D, Deadman M, Jennings M, Bisercic M, Fleischmann R, Venter C, Moxon R: DNA repeats identify novel virulence genes in Haemophilus influenzae . Proceedings of the National Academy of Science 1996, 93(20):11121\u201311125. 10.1073\/pnas.93.20.11121","journal-title":"Proceedings of the National Academy of Science"},{"key":"436_CR20","unstructured":"National Center for Biotechnology Information (NCBI)[ftp:\/\/ftp.ncbi.nih.gov\/genomes\/]"},{"key":"436_CR21","unstructured":"National Center for Biotechnology Information (NCBI) BLAST database[ftp:\/\/ftp.ncbi.nlm.nih.gov\/blast\/db\/FASTA\/human_genomic.gz]"},{"key":"436_CR22","unstructured":"Gene Ontology (GO) Consortium[http:\/\/www.geneontology.org\/]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-111.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-111\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-111.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:11:38Z","timestamp":1728303098000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,3]]},"references-count":22,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["436"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-111","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2005,5,3]]},"assertion":[{"value":"28 December 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"111"}}