×

zbMATH — the first resource for mathematics

Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes. (English) Zbl 06986595
Summary: We show that the number of all maximal \(\alpha\)-gapped repeats and palindromes of a word of length \(n\) is at most \(3(\pi^2 / 6 + 5 / 2) \alpha n\) and \(7(\pi^2 / 6 + 1 / 2) \alpha n - 3 n - 1\), respectively.

MSC:
68R15 Combinatorics on words
Software:
MUMMER; REPuter
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bannai, H.; I, T.; Inenaga, S.; Nakashima, Y.; Takeda, M.; Tsuruta, K., The “runs” theorem, SIAM J. Comput., 46, 5, 1501-1514, (2017) · Zbl 1375.68093
[2] Bannai, H.; Inenaga, S.; Köppl, D., Computing all distinct squares in linear time for integer alphabets, (Proc. CPM, LIPIcs, vol. 78, (2017)), 22:1-22:18
[3] Brodal, G. S.; Lyngsø, R. B.; Pedersen, C. N.S.; Stoye, J., Finding maximal pairs with bounded gap, (Proc. CPM, Lecture Notes in Comput. Sci., vol. 1645, (1999)), 134-149 · Zbl 1063.68614
[4] Crochemore, M.; Iliopoulos, C. S.; Kubica, M.; Radoszewski, J.; Rytter, W.; Walen, T., Extracting powers and periods in a word from its runs structure, Theoret. Comput. Sci., 521, 29-41, (2014) · Zbl 1295.68174
[5] Crochemore, M.; Kolpakov, R.; Kucherov, G., Optimal bounds for computing α-gapped repeats, (Proc. LATA, Lecture Notes in Comput. Sci., vol. 9618, (2016)), 245-255 · Zbl 1443.68137
[6] Delcher, A. L.; Kasif, S.; Fleischmann, R. D.; Peterson, J.; White, O.; Salzberg, S. L., Alignment of whole genomes, Nucleic Acids Res., 27, 11, 2369-2376, (1999)
[7] Duchon, P.; Nicaud, C.; Pivoteau, C., Gapped pattern statistics, (Proc. CPM, LIPIcs, vol. 78, (2017)), 21:1-21:12
[8] Fine, N. J.; Wilf, H. S., Uniqueness theorem for periodic functions, Proc. Amer. Math. Soc., 16, 109-114, (1965) · Zbl 0131.30203
[9] Fujishige, Y.; Nakamura, M.; Inenaga, S.; Bannai, H.; Takeda, M., Finding gapped palindromes online, (Proc. IWOCA, Lecture Notes in Comput. Sci., vol. 9843, (2016)), 191-202 · Zbl 06631021
[10] Gawrychowski, P.; I, T.; Inenaga, S.; Köppl, D.; Manea, F., Tighter bounds and optimal algorithms for all maximal α-gapped repeats and palindromes, Theoret. Comput. Sci., 62, 1, 162-191, (2018) · Zbl 1386.68120
[11] Groult, R.; Prieur, É.; Richomme, G., Counting distinct palindromes in a word in linear time, Inform. Process. Lett., 110, 20, 908-912, (2010) · Zbl 1234.68329
[12] Gusfield, D., Algorithms on Strings, Trees, and Sequences, (1997), Cambridge University Press · Zbl 0934.68103
[13] Jurka, J., Repeats in genomic DNA: mining and meaning, Curr. Opin. Struck. Biol., 8, 3, 333-337, (1998)
[14] Kolpakov, R., On the number of gapped repeats with arbitrary gap, Theoret. Comput. Sci., 723, 11-22, (2018) · Zbl 1393.68143
[15] Kolpakov, R.; Kucherov, G., Finding maximal repetitions in a word in linear time, (Proc. FOCS, (1999)), 596-604
[16] Kolpakov, R.; Kucherov, G., Searching for gapped palindromes, Theoret. Comput. Sci., 410, 51, 5365-5373, (2009) · Zbl 1187.68367
[17] Kolpakov, R.; Podolskiy, M.; Posypkin, M.; Khrapov, N., Searching of gapped repeats and subrepetitions in a word, J. Discrete Algorithms, 46-47, 1-15, (2017) · Zbl 1380.68324
[18] Kurtz, S.; Choudhuri, J. V.; Ohlebusch, E.; Schleiermacher, C.; Stoye, J.; Giegerich, R., REPuter: the manifold applications of repeat analysis on a genomic scale, Nucleic Acids Res., 29, 22, 4633-4642, (2001)
[19] Manacher, G., A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. ACM, 22, 3, 346-351, (1975) · Zbl 0305.68027
[20] Samonte, R. V.; Eichler, E. E., Segmental duplications and the evolution of the primate genome, Nat. Rev. Genet., 3, 1, 65-72, (2002)
[21] Svoboda, P.; Cara, A. D., Hairpin RNA: a secondary structure of primary importance, Cell. Mol. Life Sci., 63, 7, 901-908, (2006)
[22] Tarailo-Graovac, M.; Chen, N., Using RepeatMasker to identify repetitive elements in genomic sequences, Curr. Protoc. Bioinform., 25, 4.10.1-4.10.14, (2009)
[23] Trombetta, B.; Cruciani, F., Y chromosome palindromes and gene conversion, Hum. Genet., 136, 5, 605-619, (May 2017)
[24] Warburton, P.; Giordano, J.; Cheung, F.; Gelfand, Y.; Benson, G., Inverted repeat structure of the human genome: the X-chromosome contains a preponderance of large, highly homologous inverted repeats that contain testes genes, Genome Res., 14, 1861-1869, (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.