×

Controlled non-uniform random generation of decomposable structures. (English) Zbl 1273.05232

Summary: Consider a class of decomposable combinatorial structures, using different types of atoms \(\mathcal{Z} = \{Z_1,\dots,Z_{|Z|}\}\). We address the random generation of such structures with respect to a size \(n\) and a targeted distribution in \(k\) of its distinguished atoms. We consider two variations on this problem.
In the first alternative, the targeted distribution is given by \(k\) real numbers \(\mu_1,\dots,\mu_k\) such that \(0 < \mu_i < 1\) for all \(i\) and \(\mu_1+\dots+\mu_k \leq 1\). We aim to generate random structures among the whole set of structures of a given size \(n\), in such a way that the expected frequency of any distinguished atom \(Z_i\) equals \(\mu_i\). We address this problem by weighting the atoms with a \(k\)-tuple \(\pi\) of real-valued weights, inducing a weighted distribution over the set of structures of size \(n\). We first adapt the classical recursive random generation scheme into an algorithm taking \(\mathcal{O}(n^{1+o(1)}+mn\log n)\) arithmetic operations to draw m structures from the \(\pi\)-weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i.e., for large values of \(n\). We derive systems of functional equations whose resolution gives an explicit relationship between \(\pi\) and \(\mu_1,\dots,\mu_k\). Lastly, we give an algorithm in \(\mathcal{O}(kn^4)\) for the inverse problem, i.e., computing the frequencies associated with a given \(k\)-tuple \(\pi\) of weights, and an optimized version in \(\mathcal{O}(kn^2)\) in the case of context-free languages. This allows for a heuristic resolution of the weights/frequencies relationship suitable for complex specifications.
In the second alternative, the targeted distribution is given by \(k\) natural numbers \(n_1,\dots,n_k\) such that \(n_1+\dots+n_k+r = n\) where \(r \geq 0\) is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size \(n\) that contain exactly \(n_i\) atoms \(Z_i\) (\(1\leq i \leq k\)). We give a \(\mathcal{O}\left(r^2 \prod_{i=1}^k n_i^2 + mnk\log n\right)\) algorithm for generating \(m\) structures, which simplifies into a \(\mathcal{O}\left(r \prod_{i=1}^k n_i + mn\right)\) for regular specifications.

MSC:

05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05A17 Combinatorial aspects of partitions of integers
05C80 Random graphs (graph-theoretic aspects)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68R05 Combinatorics in computer science

Software:

CONDOR; gfun; GenRGenS; FGb
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Flajolet, P.; Zimmermann, P.; Van Cutsem, B., A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, 132, 1-35 (1994) · Zbl 0799.68143
[2] Duchon, P.; Flajolet, P.; Louchard, G.; Schaeffer, G., Boltzmann samplers for the random generation of combinatorial structures, Combinatorics, Probability, and Computing, 13, 4-5, 577-625 (2004), (special issue on Analysis of Algorithms) · Zbl 1081.65007
[3] Flajolet, P.; Fusy, E.; Pivoteau, C., Boltzmann sampling of unlabeled structures, (Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, ANALCO (2007), SIAM), 201-211 · Zbl 1430.68164
[4] Brlek, S.; Pergola, E.; Roques, O., Non uniform random generation of generalized Motzkin paths, Acta Informatica, 42, 8, 603-616 (2006) · Zbl 1089.05004
[5] Dutour, I.; Fédou, J.-M., Object grammars and random generation, Discrete Mathematics and Theoretical Computer Science, 2, 47-61 (1998) · Zbl 0947.68082
[6] Bertoni, A.; Massazza, P.; Radicioni, R., Random generations of words in regular languages with fixed occurrences of symbols, (Proceedings of Words’03, vol. 27 (2003), TUCS Gen. Publ., Turku Cent. Comput. Sci: TUCS Gen. Publ., Turku Cent. Comput. Sci Turku, Finland), 332-343 · Zbl 1040.68071
[7] Nijenhuis, A.; Wilf, H., Combinatorial Algorithms (1979), Academic Press Inc.
[8] van der Hoeven, J., Relax, but don’t be too lazy, Journal of Symbolic Computation, 34, 6, 479-542 (2002) · Zbl 1011.68189
[9] Lipshitz, L., \(D\)-finite power series, Journal of Algebra, 122, 2, 353-373 (1989) · Zbl 0695.12018
[10] Bostan, A.; Chyzak, F.; Lecerf, G.e.; Salvy, B.; Schost, E., Differential equations for algebraic functions, (Brown, C. W., ISSAC’07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (2007), ACM Press), 25-32 · Zbl 1190.68085
[11] Goldwurm, M., Random generation of words in an algebraic language in linear binary space, Information Processing Letters, 54, 229-233 (1995) · Zbl 0875.68532
[12] Schönhage, A.; Strassen, V., Schnelle multiplikation großer Zahlen. (German) [Fast multiplication of large numbers], Computing, 7, 3-4, 281-292 (1971) · Zbl 0223.68007
[13] M. Fürer, Faster integer multiplication, in: Proceedings of the 39th ACM STOC 2007 Conference, 2007, pp. 57-66.; M. Fürer, Faster integer multiplication, in: Proceedings of the 39th ACM STOC 2007 Conference, 2007, pp. 57-66. · Zbl 1179.68198
[14] Denise, A.; Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic, Theoretical Computer Science, 218, 233-248 (1999) · Zbl 0933.68154
[15] P. Flajolet, P. Zimmermann, B. Van Cutsem, A calculus of random generation: unlabelled structures, unpublished manuscript, 1997.; P. Flajolet, P. Zimmermann, B. Van Cutsem, A calculus of random generation: unlabelled structures, unpublished manuscript, 1997.
[16] Drmota, M., Systems of functional equations, Random Structures and Algorithms, 10, 1-2, 103-124 (1997) · Zbl 0869.39010
[17] Denise, A.; Roques, O.; Termier, M., Random generation of words of context-free languages according to the frequencies of letters, (Gardy, D.; Mokkadem, A., Mathematics and Computer Science: Algorithms, Trees, Combinatorics and probabilities. Mathematics and Computer Science: Algorithms, Trees, Combinatorics and probabilities, Trends in Mathematics (2000), Birkhaüser), 113-125 · Zbl 0965.68047
[18] Flajolet, P.; Odlyzko, A., Singularity analysis of generating functions, SIAM Journal on Discrete Mathematics, 3, 2, 216-240 (1990) · Zbl 0712.05004
[19] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press · Zbl 1165.05001
[20] Faugère, J., A new efficient algorithm for computing Gröbner bases (f4), Journal of Pure and Applied Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174
[21] Nicodème, P.; Salvy, B.; Flajolet, P., Motif statistics, Theoretical Computer Science, 287, 2, 593-618 (2002) · Zbl 1061.68118
[22] Waterman, M. S., Secondary structure of single stranded nucleic acids, Advances in Mathematics Supplementary Studies, 1, 1, 167-212 (1978) · Zbl 0434.05007
[23] Vauchaussade de Chaumont, M.; Viennot, X. G., Enumeration of RNA secondary structures by complexity, (Capasso, V.; Grosso, E.; Paven-Fontana, S., Mathematics in Medecine and Biology. Mathematics in Medecine and Biology, Lecture Notes in Biomathematics, vol. 57 (1985)), 360-365 · Zbl 0579.92012
[24] Salvy, B.; Zimmerman, P., GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Transactions on Mathematical Software, 20, 2, 163-177 (1994) · Zbl 0888.65010
[25] Berghen, F. V.; Bersini, H., CONDOR, a new parallel, constrained extension of Powell’s UOBYQA algorithm: experimental results and comparison with the DFO algorithm, Journal of Computational and Applied Mathematics, 181, 1, 157-175 (2005) · Zbl 1072.65088
[26] Ponty, Y.; Termier, M.; Denise, A., GenRGenS: software for generating random genomic sequences and structures, Bioinformatics, 22, 12, 1534-1535 (2006)
[27] C. Pivoteau, B. Salvy, M. Soria, Boltzmann oracle for combinatorial systems, in: DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science, 2008, pp. 475-488.; C. Pivoteau, B. Salvy, M. Soria, Boltzmann oracle for combinatorial systems, in: DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science, 2008, pp. 475-488. · Zbl 1355.05029
[28] X.G. Viennot, Une théorie combinatoire des polynômes orthogonaux, Publications du LACIM, Universié de Montréal, 1994, reprint 1991.; X.G. Viennot, Une théorie combinatoire des polynômes orthogonaux, Publications du LACIM, Universié de Montréal, 1994, reprint 1991.
[29] Dershowitz, N.; Zaks, S., The cycle lemma and some applications, European Journal of Combinatorics, 11, 35-40 (1990) · Zbl 0715.05004
[30] Nebel, M., Combinatorial properties of RNA secondary structures, Journal of Computational Biology, 3, 9, 541-574 (2003)
[31] Fontana, W.; Konings, D. A.; Stadler, P. F.; Schuster, P., Statistics of RNA secondary structures, Biopolymers, 33, 9, 1389-1404 (1993)
[32] Hofacker, I. L.; Schuster, P.; Stadler, P., Combinatorics of RNA secondary structures, Discrete Applied Mathematics, 88, 207-237 (1998) · Zbl 0918.05004
[33] Jin, E. Y.; Qin, J.; Reidys, C. M., Combinatorics of RNA structures with pseudoknots, Bulletin of Mathematical Biology, 70, 1, 45-67 (2008) · Zbl 1281.92055
[34] Y. Ponty, Etudes combinatoire et génération aléatoire des structures secondaires d’ARN, Master’s Thesis, Université Paris Sud, 2003. http://www.lri.fr/ ponty/docs/DEA.ps; Y. Ponty, Etudes combinatoire et génération aléatoire des structures secondaires d’ARN, Master’s Thesis, Université Paris Sud, 2003. http://www.lri.fr/ ponty/docs/DEA.ps
[35] Mathews, D.; Sabina, J.; Zuker, M.; Turner, D., Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure, Journal of Molecular Biology, 288, 911-940 (1999)
[36] Mathews, D. H., Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization, RNA, 10, 8, 1178-1190 (2004)
[37] Nebel, M., Identifying good predictions of RNA secondary structure, (Pacific Symposium on Biocomputing, vol. 9 (2004)), 423-434
[38] Hofacker, I. L.; Fontana, W.; Stadler, P. F.; Bonhoeffer, S. L.; Tacker, M.; Schuster, P., Fast folding and comparison of RNA secondary structures, Chemical Monthly, 125, 167-188 (1994)
[39] Greene, D. H.; Knuth, D. E., Mathematics for the Analysis of Algorithms (1981), Birkhauser: Birkhauser Boston · Zbl 0481.68042
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.