×

Wavelet analysis on symbolic sequences and two-fold de Bruijn sequences. (English) Zbl 1348.65185

Summary: The concept of symbolic sequences play important role in study of complex systems. In the work we are interested in ultrametric structure of the set of cyclic sequences naturally arising in theory of dynamical systems. Aimed at construction of analytic and numerical methods for investigation of clusters we introduce operator language on the space of symbolic sequences and propose an approach based on wavelet analysis for study of the cluster hierarchy. The analytic power of the approach is demonstrated by derivation of a formula for counting of two-fold de Bruijn sequences, the extension of the notion of de Bruijn sequences. Possible advantages of the developed description is also discussed in context of applied problem of construction of efficient DNA sequence assembly algorithms.

MSC:

65T60 Numerical methods for wavelets
37N25 Dynamical systems in biology
92D20 Protein sequences, DNA sequences
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Kitchens, B.P.: Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts. Springer, Springer (1998) · Zbl 0892.58020
[2] Hao, B.-L., Zheng, W.-M.: Applied Symbolic Dynamics and Chaos. World Scientific, Singapore (1998) · Zbl 0914.58017 · doi:10.1142/3830
[3] Daw, C.S., Finney, C.E.A., Tracy, E.R.: A review of symbolic analysis of experimental data. Rev. Sci. Instrum. 74, 915 (2003) · doi:10.1063/1.1531823
[4] Berkolaiko, G., Kuchment, P.: Introduction to Quantum Graphs. American Mathematical Society, Providence (2012) · Zbl 1318.81005 · doi:10.1090/surv/186
[5] de Bruijn, N.G.: A combinatorial problem. Indag. Math. 8, 461 (1946) · Zbl 0196.02803
[6] Haussler, D., OBrien, S.J., et al.: Genome 10K: a proposal to obtain whole-genome sequence for 10,000 vertebrate species. J. Hered. 100, 659 (2008)
[7] Gilbert, E.N., Riordan, J.: Symmetry types of periodic sequences. Illinois J. Math. 5, 657 (1961) · Zbl 0105.25101
[8] Bailin, H., Huimin, X.: Factorizable language revisited from dynamics to biology. Int. J. Mod. Phys. B 21, 4077 (2007) · doi:10.1142/S0217979207045244
[9] Brida, J.G.: Symbolic time series analysis and economic regimes. Struct. Chang. Econ. Dyn. 14, 159 (2000) · doi:10.1016/S0954-349X(02)00050-4
[10] Bolshoy, A., Volkovich, Z., Kirzhner, V., Barzily, Z.: Genome Clustering: From Linguistic Models to Classification of Genetic Texts. Springer, Heidelberg (2010) · doi:10.1007/978-3-642-12952-0
[11] Tabor, M.: The Surface of Section in “Chaos and Integrability in Nonlinear Dynamics: An Introduction. Wiley, New York (1989) · Zbl 0682.58003
[12] Ott, E.: Chaos in Dynamical Systems, sec edn, p. 77. Cambridge University Press, Cambridge (2002) · Zbl 1006.37001 · doi:10.1017/CBO9780511803260
[13] Cvitanović, P., Artuso, R., Mainieri, R., Tanner, G., Vattay, G.: Chaos: Classical and Quantum. Niels Bohr Institute, Copenhagen (2012)
[14] Auerbach, D., Cvitanović, P., Eckmann, J.-P., Gunaratne, G.: Exploring chaotic motion through periodic orbits. Phys. Rev. Lett. 23, 2387 (1987) · doi:10.1103/PhysRevLett.58.2387
[15] Artuso, R., Aurell, E., Cvitanović, P.: Recycling of strange sets: I. Cycle expansions, Nonlinearity 3 (1990) 325; Recycling of strange sets: II. Applications. Nonlinearity 3, 361 (1990) · Zbl 0702.58064
[16] Gutzwiller, M.G.: Chaos in Classical and Quantum Mechanics. Springer, New York (1990) · Zbl 0727.70029 · doi:10.1007/978-1-4612-0983-6
[17] Sieber, M., Richter, K.: Correlations between periodic orbits and their role in spectral statistics. Phys. Scr. T90, 128 (2001) · doi:10.1238/Physica.Topical.090a00128
[18] Heusler, S., Müller, S., Braun, P., Haake, F.: Universal spectral form factor for chaotic dynamics. J. Phys. A: Math. Gen 37, L31 (2004) · Zbl 1044.81052 · doi:10.1088/0305-4470/37/3/L02
[19] Haake, F.: Quantuim Signatures of Chaos, 3rd edn. Springer, Heidelberg (2010) · Zbl 1209.81002 · doi:10.1007/978-3-642-05428-0
[20] Gutkin, B., Osipov, VAl: Clustering of periodic orbits in chaotic systems. Nonlinearity 26, 177 (2013) · Zbl 1263.05095 · doi:10.1088/0951-7715/26/1/177
[21] Murtagh, F.; Baier, D. (ed.); Becker, R. (ed.); Schmidt-Thieme, L. (ed.), Identifying and exploiting ultrametricity, 263 (2008), Berlin
[22] Sainte-Marie, C.F.: Solution to question nr. 48. L’intermédiaire des Mathématiciens 1, 107 (1894)
[23] Compeau, P.E.C., Pevzner, P.A., Tesler, G.: How to apply de Bruijn graphs to genome assembly. Nat. Biotechnol. 29, 987 (2011) · doi:10.1038/nbt.2023
[24] Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49, 758 (1946) · Zbl 0060.02701
[25] Good, I.J.: Normal recurring decimals. J. Lond. Math. Soc. 21, 167 (1946) · Zbl 0060.02702 · doi:10.1112/jlms/s1-21.3.167
[26] Chaisson, M.J., Brinza, D., Pevzner, P.A.: De novo fragment assembly with short mate-paired reads: does the read length matter? Genome Res. 19, 336 (2009) · doi:10.1101/gr.079053.108
[27] Conway, T.C., Bromage, A.J.: Succinct data structures for assembling large genomes. Bioinformatics 27, 479 (2011) · doi:10.1093/bioinformatics/btq697
[28] J. Pell, Hintze, A., Canino-Koning, R., Howe, A., Tiedje, J.M., Brown, C.T.: Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. In: Proceedings of the National Academy of Sciences, vol. 109, p. 13272 (2012) · Zbl 1256.68052
[29] Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the Representation of de Bruijn Graphs. Lecture Notes in Computer Science, p. 35. Springer, Berlin (2014)
[30] Avetisov, V.A., Zhuravlev, YuN: An evolutionary interpretation of the \[p\] p-adic ultrametric diffusion equation. Dokl. Math. 75, 453 (2007) · Zbl 1162.35074 · doi:10.1134/S1064562407030325
[31] Avetisov, V.A., Ivanov, V.A., Meshkov, D.A., Nechaev, S.K.: Fractal globules: a new approach to artificial molecular machines. Biophys. J. 107, 2361 (2014) · doi:10.1016/j.bpj.2014.10.019
[32] Messer, P.W., Arndt, P.F., Lässig, M.: Solvable sequence evolution models and genomic correlations. Phys. Rev. Lett. 94, 138103 (2005) · doi:10.1103/PhysRevLett.94.138103
[33] Dragovich, B., Dragovich, A.Y.: A \[p\] p-adic model of DNA sequence and genetic code. p-Adic Numbers Ultramet. Anal. Appl. 1, 34 (2009) · Zbl 1187.92039 · doi:10.1134/S2070046609010038
[34] Gutkin, B., Osipov, VAl: Spectral problem of block-rectangular hierarchical matrices. J. Stat. Phys. 143, 72 (2011) · Zbl 1218.82025 · doi:10.1007/s10955-011-0162-6
[35] Kozyrev, S.V.: Wavelet analysis as a \[p\] p-adic spectral analysis. Izvestia Akademii Nauk Seria Math. 66, 149 (2002) · Zbl 1016.42025 · doi:10.4213/im381
[36] Kozyrev, S.V., Khrennikov, A.Y., Shelkovich, V.M.: \[p\] p-Adic wavelets and their applications. Proc. Steklov Inst. Math. 285, 157 (2014) · Zbl 1308.42031 · doi:10.1134/S0081543814040129
[37] Navarro, G., Navarro, G.: Wavelet Trees for All. Lecture Notes in Computer Science, p. 2. Springer, Berlin (2014) · Zbl 1284.68217
[38] Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999) · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[39] Weisstein, E.W.: Line Graph, From MathWorld-A Wolfram Web Resource. http://mathworld.wolfram.com/LineGraph.html · Zbl 0951.68117
[40] Aardenne-Ehrenfest, T., Bruijn, N.G.: Circuits and trees in oriented linear graphs. Simon Stevin 28, 203 (1951) · Zbl 0044.38201
[41] Rosenfeld, V.R.: Enumerating de Bruijn sequences. Commun. Math. Comput. Chem. 45, 71 (2002) · Zbl 1030.05006
[42] Gutkin, B., Osipov, VAl: Clustering of periodic orbits and ensembles of truncated unitary matrices. J. Stat. Phys. 153, 1049 (2013) · Zbl 1285.81031 · doi:10.1007/s10955-013-0859-9
[43] Sharp, R.: Degeneracy in the length spectrum for metric graphs. Geom. Dedic. 149, 177 (2010) · Zbl 1221.05191 · doi:10.1007/s10711-010-9475-x
[44] Tanner, G.: Spectral statistics for unitary transfer matrices of binary graphs. J. Phys. A 33, 3567 (2000) · Zbl 0948.82016 · doi:10.1088/0305-4470/33/18/304
[45] Nagao, T., Braun, P., Müller, S., Saito, K., Heusler, S., Haake, F.: Semiclassical theory for parametric correlation of energy levels. J. Phys. A: Math. Theor. 40, 47 (2007) · Zbl 1105.81040 · doi:10.1088/1751-8113/40/1/003
[46] Wan, Z., Xiong, R., Yu, M.: On the number of cycles of short length in the de Bruijn-Good graph \[G_n\] Gn. Discret. Math. 62, 85 (1986) · Zbl 0599.05038 · doi:10.1016/0012-365X(86)90044-0
[47] Kapoor, S., Ramesh, H.: An algorithm for enumerating all spanning trees of a directed graph. Algorithmica 27, 120 (2000) · Zbl 0951.68117 · doi:10.1007/s004530010008
[48] Hamming, R.W.: Error detecting and error correcting codes. Bell Syst. Tech. J. 29, 147 (1950) · Zbl 1402.94084 · doi:10.1002/j.1538-7305.1950.tb00463.x
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.