{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T16:02:30Z","timestamp":1770480150704,"version":"3.49.0"},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: A tandem repeat in DNA is a sequence of two or more contiguous, approximate copies of a pattern of nucleotides. Tandem repeats occur in the genomes of both eukaryotic and prokaryotic organisms. They are important in numerous fields including disease diagnosis, mapping studies, human identity testing (DNA fingerprinting), sequence homology and population studies. Although tandem repeats have been used by biologists for many years, there are few tools available for performing an exhaustive search for all tandem repeats in a given sequence.<\/jats:p><jats:p>Results: In this paper we describe an efficient algorithm for finding all tandem repeats within a sequence, under the edit distance measure. The contributions of this paper are two-fold: theoretical and practical. We present a precise definition for tandem repeats over the edit distance and an efficient, deterministic algorithm for finding these repeats.<\/jats:p><jats:p>Availability: The algorithm has been implemented in C++, and the software is available upon request and can be used at . The use of this tool will assist biologists in discovering new ways that tandem repeats affect both the structure and function of DNA and protein molecules.<\/jats:p><jats:p>Contact: \u00a0sokol@sci.brooklyn.cuny.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl309","type":"journal-article","created":{"date-parts":[[2007,1,19]],"date-time":"2007-01-19T18:51:12Z","timestamp":1169232672000},"page":"e30-e35","source":"Crossref","is-referenced-by-count":67,"title":["Tandem repeats over the edit distance"],"prefix":"10.1093","volume":"23","author":[{"given":"Dina","family":"Sokol","sequence":"first","affiliation":[{"name":"Department of Computer and Information Science, Brooklyn College of the City University of New York 1 \u00a0 1 \u00a0 \u00a0 Brooklyn, NY, USA"}]},{"given":"Gary","family":"Benson","sequence":"additional","affiliation":[{"name":"Departments of Biology and Computer Science, Boston University 2 \u00a0 2 \u00a0 \u00a0 Boston, USA"}]},{"given":"Justin","family":"Tojeira","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Brooklyn College of the City University of New York 1 \u00a0 1 \u00a0 \u00a0 Brooklyn, NY, USA"}]}],"member":"286","published-online":{"date-parts":[[2007,1,15]]},"reference":[{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/0304-3975(95)92848-R","article-title":"A space efficient algorithm for finding best scoring non-overlapping alignments","volume":"145","author":"Benson","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1089\/cmb.1997.4.351","article-title":"Sequence alignment with tandem duplication","volume":"4","author":"Benson","year":"1997","journal-title":"J. Comput. Biol."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1093\/nar\/27.2.573","article-title":"Tandem repeats finder\u2014a program to analyze DNA sequences","volume":"27","author":"Benson","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1126\/science.1084564","article-title":"The Human Genome Project: lessons from large-scale biology","volume":"300","author":"Collins","year":"2003","journal-title":"Science"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1126\/science.1084566","article-title":"Realizing the potential of the genome revolution: the genomes to life program","volume":"300","author":"Frazier","year":"2003","journal-title":"Science"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"1256","DOI":"10.1126\/science.1546326","article-title":"An unstable triplet repeat in a gene related to myotonic muscular dystrophy","volume":"255","author":"Fu","year":"1992","journal-title":"Science"},{"key":"2023041107142181100_","article-title":"Speeding up the detection of evolutive tandem repeats","author":"Groult","year":"2003"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0304-3975(03)00423-7","article-title":"Speeding up the detection of evolutive tandem repeats","volume":"310","author":"Groult","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"1630","DOI":"10.1126\/science.1111427","article-title":"Microsatellite instability generates diversity in brain and sociobehavioral traits","volume":"308","author":"Hammock","year":"2005","journal-title":"Science"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/S0015-7368(93)73016-9","article-title":"DNA typing: approaches and applications","volume":"33","author":"Jeffreys","year":"1993","journal-title":"J. Forensic Sci. Soc."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1137\/S0097539794262677","article-title":"An algorithm for locating regions of maximum alignment score","volume":"25","author":"Kannan","year":"1996","journal-title":"SIAM J. Comput."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1110\/ps.9.6.1203","article-title":"Amino acid repeat patterns in protein sequences: their diversity and structural-functional implications","volume":"9","author":"Katti","year":"2000","journal-title":"Protein Sci."},{"key":"2023041107142181100_","first-page":"276","article-title":"Multiple alignment of biological sequences containing tandem repeats","volume":"7","author":"Kitada","year":"1996","journal-title":"Genome Inform."},{"key":"2023041107142181100_","first-page":"170","article-title":"Finding approximate repetitions under hamming distance","author":"Kolpakov","year":"2001"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"3672","DOI":"10.1093\/nar\/gkg617","article-title":"mreps: Efficient and flexible detection of tandem repeats in DNA","volume":"31","author":"Kolpakov","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","article-title":"Fast parallel and serial approximate string matching","volume":"10","author":"Landau","year":"1989","journal-title":"J. Algorithm."},{"key":"2023041107142181100_","first-page":"120","article-title":"An algorithm for approximate tandem repeats","author":"Landau","year":"1993"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/S0097539794264810","article-title":"Incremental string comparison","volume":"27","author":"Landau","year":"1998","journal-title":"SIAM J. Comput."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/106652701300099038","article-title":"An algorithm for approximate tandem repeats","volume":"8","author":"Landau","year":"2001","journal-title":"J. Comput. Biol."},{"key":"2023041107142181100_","first-page":"707","article-title":"Binary codes capable of correcting, deletions, insertions and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Phys. Dokl."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","article-title":"An O(n logn) algorithm for finding all repetitions in a string","author":"Main","year":"1984","journal-title":"J. Algorithm."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1137\/S0097539795288489","article-title":"All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings","volume":"27","author":"Schmidt","journal-title":"SIAM J. Comput."},{"key":"2023041107142181100_","first-page":"15","article-title":"A near-extinction event in lynx: do microsatellite data tell the tale?","volume":"6","author":"Spong","year":"2002","journal-title":"Conserv. Ecol."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"The International Human Genome Mapping Consortium.","year":"2001","journal-title":"Nature"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1016\/0959-437X(93)90017-J","article-title":"Microsatellites and their application to population genetic studies","volume":"3","author":"Uform","year":"1993","journal-title":"Curr. Opin. Genet. Dev."},{"key":"2023041107142181100_","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-12689-9_129","article-title":"On approximate string matching","author":"Ukkonen","year":"1983"},{"key":"2023041107142181100_","doi-asserted-by":"crossref","DOI":"10.1145\/974614.974644","article-title":"Finding approximate tandem repeats in genomic sequences","author":"Wexler","year":"2004"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e30\/49820494\/bioinformatics_23_2_e30.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e30\/49820494\/bioinformatics_23_2_e30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T13:04:02Z","timestamp":1683723842000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/e30\/202699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,15]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl309","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2007,1,15]]}}}