{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T03:21:44Z","timestamp":1792898504367,"version":"4.5.0"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,5,23]],"date-time":"2005-05-23T00:00:00Z","timestamp":1116806400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,5,23]],"date-time":"2005-05-23T00:00:00Z","timestamp":1116806400000},"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>Sequence comparison by alignment is a fundamental tool of molecular biology. In this paper we show how a number of sequence comparison tasks, including the detection of unique genomic regions, can be accomplished efficiently without an alignment step. Our procedure for nucleotide sequence comparison is based on shortest unique substrings. These are substrings which occur only once within the sequence or set of sequences analysed and which cannot be further reduced in length without losing the property of uniqueness. Such substrings can be detected using generalized suffix trees.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>We find that the shortest unique substrings in <jats:italic>Caenorhabditis elegans<\/jats:italic>, human and mouse are no longer than 11 bp in the autosomes of these organisms. In mouse and human these unique substrings are significantly clustered in upstream regions of known genes. Moreover, the probability of finding such short unique substrings in the genomes of human or mouse by chance is extremely small. We derive an analytical expression for the null distribution of shortest unique substrings, given the GC-content of the query sequences. Furthermore, we apply our method to rapidly detect unique genomic regions in the genome of <jats:italic>Staphylococcus aureus<\/jats:italic> strain MSSA476 compared to four other staphylococcal genomes.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>We combine a method to rapidly search for shortest unique substrings in DNA sequences and a derivation of their null distribution. We show that unique regions in an arbitrary sample of genomes can be efficiently detected with this method. The corresponding programs shustring (SHortest Unique subSTRING) and shulen are written in C and available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/adenine.biz.fh-weihenstephan.de\/shustring\/\">http:\/\/adenine.biz.fh-weihenstephan.de\/shustring\/<\/jats:ext-link>.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-123","type":"journal-article","created":{"date-parts":[[2005,5,24]],"date-time":"2005-05-24T06:13:39Z","timestamp":1116915219000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":77,"title":["Genome comparison without alignment using shortest unique substrings"],"prefix":"10.1186","volume":"6","author":[{"given":"Bernhard","family":"Haubold","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nora","family":"Pierstorff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedrich","family":"M\u00f6ller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Wiehe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,5,23]]},"reference":[{"key":"448_CR1","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 1970, 48: 443\u2013453. 10.1016\/0022-2836(70)90057-4","journal-title":"Journal of Molecular Biology"},{"key":"448_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS: Identification of common molecular subsequences. Journal of Molecular Biology 1981, 147: 195\u2013197. 10.1016\/0022-2836(81)90087-5","journal-title":"Journal of Molecular Biology"},{"key":"448_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: 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":"448_CR4","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: Cambridge University Press; 1997."},{"key":"448_CR5","doi-asserted-by":"publisher","first-page":"2012","DOI":"10.1126\/science.282.5396.2012","volume":"282","author":"The C elegans Sequencing Consortium","year":"1998","unstructured":"The C elegans Sequencing Consortium: Genome sequence of the nematode C. elegans: a platform for investigating biology. Science 1998, 282: 2012\u20132018. 10.1126\/science.282.5396.2012","journal-title":"Science"},{"key":"448_CR6","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1038\/35057062","volume":"409","author":"International Human Genome Sequencing Consortium","year":"2001","unstructured":"International Human Genome Sequencing Consortium: Initial sequencing and analysis of the human genome. Nature 2001, 409: 860\u2013921. 10.1038\/35057062","journal-title":"Nature"},{"key":"448_CR7","doi-asserted-by":"publisher","first-page":"9786","DOI":"10.1073\/pnas.0402521101","volume":"101","author":"MT Holden","year":"2004","unstructured":"Holden MT, Feil EJ, Lindsay JA, Peacock SJ, Day NP, Enright MC, Foster TJ, Moore CE, Hurst L, Atkin R, Barron A, Bason N, Bentley SD, Chillingworth C, Chillingworth T, Churcher C, Clark L, Corton C, Cronin A, Doggett J, Dowd L, Feltwell T, Hance Z, Harris B, Hauser H, Holroyd S, Jagels K, James KD, Lennard N, Line A, Mayes R, Moule S, Mungall K, Ormond D, Quail MA, Rabbinowitsch E, Rutherford K, Sanders M, Sharp S, Simmonds M, Stevens K, Whitehead S, Barrell BG, Spratt BG, Parkhill J: Complete genomes of two clinical Staphylococcus aureus strains: evidence for the rapid evolution of virulence and drug resistance. Proc Natl Acad Sci U S A 2004, 101: 9786\u20139791. 10.1073\/pnas.0402521101","journal-title":"Proc Natl Acad Sci U S A"},{"key":"448_CR8","first-page":"405","volume":"91","author":"B Haubold","year":"2004","unstructured":"Haubold B, Wiehe T: Comparative genomics: methods and applications. Naturwissenschaften 2004, 91: 405\u2013421.","journal-title":"Naturwissenschaften"},{"key":"448_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C: Introduction to Algorithms. The MIT Press; 2001."},{"key":"448_CR10","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1038\/nature01262","volume":"420","author":"Mouse Genome Sequencing Consortium","year":"2002","unstructured":"Mouse Genome Sequencing Consortium: Initial sequencing and comparative analysis of the mouse genome. Nature 2002, 420: 520\u2013561. 10.1038\/nature01262","journal-title":"Nature"},{"key":"448_CR11","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1126\/science.270.5235.397","volume":"270","author":"CM Fraser","year":"1995","unstructured":"Fraser CM, Gocayne JD, White O, Adams MD, Clayton RA, Fleischmann RD, Bult CJ, Kerlavage AR, Sutton GG, Kelley JM, Fritchman JL, Weidman JF, Small KV, Sandusky M, Fuhrmann JL, Nguyen DT, Utterback T, Saudek DM, Phillips CA, Merrick JM, Tomb J, Dougherty BA, Bott KF, Hu PC, Lucier TS, Peterson SN, Smith HO, Venter JC: The minimal gene complement of Mycoplasma genitalium. Science 1995, 270: 397\u2013403.","journal-title":"Science"},{"key":"448_CR12","doi-asserted-by":"publisher","first-page":"1819","DOI":"10.1016\/S0140-6736(02)08713-5","volume":"359","author":"T Baba","year":"2002","unstructured":"Baba T, Takeuchi F, Kuroda M, Yuzawa H, Aoki K, Oguchi A, Nagai Y, Iwama N, Asano K, Naimi T, Kuroda H, Cui L, Yamamoto K, Hiramatsu K: Genome and virulence determinants of high virulence community-acquired MRSA. Lancet 2002, 359: 1819\u20131827. 10.1016\/S0140-6736(02)08713-5","journal-title":"Lancet"},{"key":"448_CR13","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1016\/S0140-6736(00)04403-2","volume":"357","author":"M Kuroda","year":"2001","unstructured":"Kuroda M, Ohta T, Uchiyama I, Baba T, Yuzawa H, Kobayashi I, Cui L, Oguchi A, Aoki K, Nagai Y, Lian J, Ito T, Kanamori M, Matsumaru H, Maruyama A, Murakami H, Hosoyama A, Mizutani-Ui Y, Takahashi NK, Sawano T, Inoue R, Kaito C, Sekimizu K, Hirakawa H, Kuhara S, Goto S, Yabuzaki J, Kanehisa M, Yamashita A, Oshima K, Furuya K, Yoshino C, Shiba T, Hattori M, Ogasawara N, Hayashi H, Hiramatsu K: Whole genome sequencing of meticillin-resistant Staphylococcus aureus. Lancet 2001, 357: 1225\u20131240. 10.1016\/S0140-6736(00)04403-2","journal-title":"Lancet"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-123.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-123\/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-123.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:12:31Z","timestamp":1728303151000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,23]]},"references-count":13,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["448"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-123","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5,23]]},"assertion":[{"value":"9 November 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"123"}}