I, Tomohiro; Köppl, Dominik Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes. (English) Zbl 1495.68186 Theor. Comput. Sci. 753, 1-15 (2019). 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. Cited in 3 Documents MSC: 68R15 Combinatorics on words Keywords:combinatorics on words; repetitions; gapped repeats; gapped palindromes Software:REPuter; MUMMER PDFBibTeX XMLCite \textit{T. I} and \textit{D. Köppl}, Theor. Comput. Sci. 753, 1--15 (2019; Zbl 1495.68186) Full Text: DOI arXiv 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 1478.68460 [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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.