The generation of random equilateral polygons. (English) Zbl 1222.82069
Four popular methods to generate random equilateral polygons in three-space are described: the polygonal folding method, the Grankshaft rotation method, the Hedgehog method, and the triangle method. The authors compare the implementation and efficacy of these procedures, especially with regards to the population distribution of polygons in the space of polygonal knots, the distribution of edge vectors, the local curvature, and the local torsion. The authors give a rigorous proof that the Grankshaft rotation method is ergodic and they also show that this provides a fast, attractive alternative to the polygonal folding method, which was already known to be ergodic.
Reviewer: Nasir N. Ganikhodjaev (Kuantan)
MSC:
| 82C41 | Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics |
| 82C32 | Neural nets applied to problems in time-dependent statistical mechanics |
Keywords:
knot space; probability of knotting; Monte Carlo method; Pivot method; polygonal folding; Grankshaft rotations; Hedgehog method; triangle methodReferences:
| [1] | Amzallag, A., Vaillant, C., Jacob, J., Unser, M., Bednar, J., Kahn, J.D., Dubochet, J., Stasiak, A., Maddocks, J.H.: 3d reconstruction and comparison of shapes of DNA minicircles observed by cryo-electron microscopy. Nucleic Acids Res. 34, e125-1-8 (2006) · doi:10.1093/nar/gkl675 |
| [2] | Arsuaga, J., Vazquez, M., Trigueros, S., Sumners, D.W., Roca, J.: Knotting probability of DNA molecules confined in restricted volumes: DNA knotting in phage capsids. Proc. Natl. Acad. Sci. USA 99, 5373–5377 (2002) · doi:10.1073/pnas.032095099 |
| [3] | Arsuaga, J., Vazquez, M., McGuirk, P., Trigueros, S., Sumners, D.W., Roca, J.: DNA knots reveal a chiral organization of DNA in phage capsids. Proc. Natl. Acad. Sci. USA 102(26), 9165–9169 (2005) · doi:10.1073/pnas.0409323102 |
| [4] | Calvo, J.A.: Geometric knot theory: the classification of spatial polygons with a small number of edges. Ph.D. thesis, University of California, Santa Barbara (1998) |
| [5] | Calvo, J.A., Millett, K.C.: Minimal edge piecewise linear knots. In: Ideal Knots, pp. 107–128. World Sci. Publishing, Singapore (1998) · Zbl 0946.57008 |
| [6] | Calvo, J.A., Millett, K.C.: Minimal edge piecewise linear knots. In: Ideal Knots. Ser. Knots Everything, vol. 19, pp. 107–128. World Sci. Publ., River Edge (1998) · Zbl 0946.57008 |
| [7] | Cerny, V.: A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 51–51 (1985) · Zbl 0534.90091 · doi:10.1007/BF00940812 |
| [8] | Chakravarti, I.M., Laha, R.G., Roy, J.: Handbook of Methods of Applied Statistics, vol. I. Wiley, New York (1967) · Zbl 0203.51503 |
| [9] | de Gennes, P.G.: Collapse of a polymer chain in poor solvents. J. Phys. Lett. 36, 55–57 (1975) · doi:10.1051/jphyslet:0197500360305500 |
| [10] | de Gennes, P.G.: Scaling Concepts in Polymer Physics. Cornell University Press, Ithaca (1979) |
| [11] | Deguchi, T., Shimamura, M.K.: Topological effects on the average size of random knots. In: Physical Knots: Knotting, Linking, and Folding Geometric Objects in \(\mathbb{R}\)3. Contemp. Math., vol. 304, pp. 93–114. Amer. Math. Soc., Providence (2002) · Zbl 1010.82042 |
| [12] | Deguchi, T., Tsurusaki, K.: A statistical study of random knotting using the Vassiliev invariants. J. Knot Theory Ramif. 3(3), 321–353 (1994). Random knotting and linking (Vancouver, BC, 1993) · Zbl 0841.57010 · doi:10.1142/S0218216594000241 |
| [13] | Deguchi, T., Tsurusaki, K.: Numerical application of knot invariants and universality of random knotting. In: Knot Theory, Warsaw, 1995. Banach Center Publ., vol. 42, pp. 77–85. Polish Acad. Sci., Warsaw (1998) · Zbl 0901.57013 |
| [14] | des Cloizeaux, J.: Ring polymers in solution: Topological effects. J. Phys. Lett. 42, 433–436 (1981) · doi:10.1051/jphyslet:019810042019043300 |
| [15] | Deutsch, J.M.: Equilibrium size of large ring molecules. Phys. Rev. E 59(3), 2539–2541 (1999) · Zbl 0960.94036 · doi:10.1103/PhysRevE.59.R2539 |
| [16] | Diao, Y., Ernst, C., Janse van Rensburg, E.J.: In search of a good polygonal knot energy. J. Knot Theory Ramif. 6(5), 633–657 (1997) · Zbl 0889.57004 · doi:10.1142/S0218216597000352 |
| [17] | Diao, Y., Ernst, C.: The average crossing number of Gaussian random walks and polygons. In: Physical and Numerical Models in Knot Theory. Series on Knots and Everything, vol. 36, pp. 275–292. World Sci. Publ., River Edge (2005) · Zbl 1104.57005 |
| [18] | Diao, Y., Dobay, A., Kusner, R.B., Millett, K.C., Stasiak, A.: The average crossing number of equilateral random polygons. J. Phys. A 36(46), 11,561–11,574 (2003) · Zbl 1052.57006 · doi:10.1088/0305-4470/36/46/002 |
| [19] | do Carmo, M.P.: Differential Geometry of Curves and Surfaces. Prentice-Hall Inc., Englewood Cliffs (1976). Translated from the Portuguese |
| [20] | Dobay, A., Sottas, P., Dubochet, J., Stasiak, A.: Predicting optimal lengths of random knots. Lett. Math. Phys. 55(3), 239–247 (2001). Topological and geometrical methods (Dijon, 2000) · Zbl 1012.82033 · doi:10.1023/A:1010921318473 |
| [21] | Dobay, A., Dubochet, J., Millett, K.C., Sottas, P., Stasiak, A.: Scaling behavior of random knots. Proc. Natl. Acad. Sci. USA 100(10), 5611–5615 (2003) · Zbl 1063.82013 · doi:10.1073/pnas.0330884100 |
| [22] | Drube, E., Alim, K., Witz, G., Dietler, G., Frey, E.: Excluded volume effects on semiflexible ring polymers. Nano Lett. 10, 1445–1449 (2010) · doi:10.1021/nl1003575 |
| [23] | Ercolini, E., Valle, E., Adamcik, J., Witz, G., Metzler, R., De Los Rios, P., Roca, J., Dietler, G.: Fractal dimension and localization of DNA knots. Phys. Rev. Lett. 98 058102 (2007) · doi:10.1103/PhysRevLett.98.058102 |
| [24] | Ewing, B., Millett, K.C.: Computational algorithms and the complexity of link polynomials. In: Progress in Knot Theory and Related Topics, pp. 51–68. Hermann, Paris (1997) · Zbl 0930.57007 |
| [25] | Ferrenberg, A.M., Swendsen, R.H.: Application of the Monte Carlo method to the lattice-gas model. Phys. Rev. Lett. 61, 2635–2638 (1988) · doi:10.1103/PhysRevLett.61.2635 |
| [26] | Forsén, S. (ed.): Nobel Lectures, Chemistry 1971–1980. World Scientific, Singapore (1993) |
| [27] | Freyd, P., Yetter, D., Hoste, J., Lickorish, W.B.R., Millett, K.C., Ocneanu, A.: A new polynomial invariant of knots and links. Bull., New Ser., Am. Math. Soc. 12(2), 239–246 (1985) · Zbl 0572.57002 · doi:10.1090/S0273-0979-1985-15361-3 |
| [28] | Geyer, C.J.: Markov chain Monte Carlo maximum likelihood. In: Computing Science and Statistics: Proc. 23rd Symp. on the Interface, pp. 156–163 (1991) |
| [29] | Grosberg, A.Y.: Critical exponents for random knots. Phys. Rev. Lett. 85(18), 3858–3861 (2000) · doi:10.1103/PhysRevLett.85.3858 |
| [30] | Grosberg, A.Y.: Total curvature and total torsion of a freely jointed circular polymer with n segments. Macromolecules 41(12), 4524–4527 (2008) · doi:10.1021/ma800299c |
| [31] | Haahr, M.: True random number service. http://www.random.org . Cited Nov 2007 |
| [32] | Hoste, J.: The enumeration and classification of knots and links. In: Handbook of Knot Theory, pp. 209–232. Elsevier, Amsterdam (2005) · Zbl 1096.57003 |
| [33] | Hoste, J., Thistlethwaite, M., Weeks, J.: The first 1,701,936 knots. Math. Intell. 20(4), 33–48 (1998) · Zbl 0916.57008 · doi:10.1007/BF03025227 |
| [34] | Kapovich, M., Millson, J.J.: The symplectic geometry of polygons in Euclidean space. J. Differ. Geom. 44, 479–513 (1996) · Zbl 0889.58017 |
| [35] | Kirpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [36] | Klenin, K.V., Vologodskii, A.V., Anshelevich, V.V., Dykhne, A.M., Frank-Kamenetskii, M.D.: Effect of excluded volume on topological properties of circular DNA. J. Biomol. Struct. Dyn. 5, 1173–1185 (1988) · doi:10.1080/07391102.1988.10506462 |
| [37] | Lal, M.: Monte Carlo computer simulation of chain molecules. I. Mol. Phys. 17, 57–64 (1969) · doi:10.1080/00268976900100781 |
| [38] | Larsen, R.J., Marx, M.L.: An Introduction to Mathematical Statistics and Its Applications, 3rd edn. Prentice Hall, Upper Saddle River (2001) · Zbl 0615.62002 |
| [39] | Le Bret, M.: Monte Carlo computation of the supercoiling energy. The sedimentation constant, and the radius of gyration of unknotted and knotted circular DNA. Biopolymers 19(3), 619–637 (1980) · doi:10.1002/bip.1980.360190312 |
| [40] | Madras, N., Slade, G.: The Self-Avoiding Walk. Birkhäuser, Boston (1996) · Zbl 0872.60076 |
| [41] | Madras, N., Sokal, A.D.: The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk. J. Stat. Phys. 50, 109–186 (1988) · Zbl 1084.82503 · doi:10.1007/BF01022990 |
| [42] | Marenduzzo, D., Orlandini, E., Stasiak, A., Sumners, D.W., Tubiana, L., Micheletti, C.: Application of the Monte Carlo method to the lattice-gas model. Proc. Natl. Acad. Sci. USA 106, 22269–22274 (2009) · doi:10.1073/pnas.0907524106 |
| [43] | Metropolis, N.C., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087–1092 (1953) · doi:10.1063/1.1699114 |
| [44] | Micheletti, C., Marenduzzo, D., Orlandini, E., Sumners, D.W.: Application of the Monte Carlo method to the lattice-gas model. J. Chem. Phys. 124, 64903-1-10 (2006) |
| [45] | Micheletti, C., Marenduzzo, D., Orlandini, E., Sumners, D.W.: Application of the Monte Carlo method to the lattice-gas model. Biophys. J. 95, 3591–3599 (2008) · doi:10.1529/biophysj.108.137653 |
| [46] | Millett, K.C.: Knotting of regular polygons in 3-space. J. Knot Theory Ramif. 3(3), 263–278 (1994). Random knotting and linking (Vancouver, BC, 1993) · Zbl 0838.57008 · doi:10.1142/S0218216594000204 |
| [47] | Millett, K.C.: Monte Carlo explorations of polygonal knot spaces. In: Knots in Hellas ’98 (Delphi). Ser. Knots Everything, vol. 24, pp. 306–334. World Sci. Publ., River Edge (2000) · Zbl 0970.57007 |
| [48] | Millett, K.C.: An investigation of equilateral knot spaces and ideal physical knot configurations. In: Physical Knots: Knotting, Linking, and Folding Geometric Objects in \(\mathbb{R}\)3. Contemp. Math., vol. 304, pp. 77–91. Amer. Math. Soc., Providence (2002) · Zbl 1013.57008 |
| [49] | Millett, K.C., Rawdon, E.J.: Energy ropelength, and other physical aspects of equilateral knots. J. Comput. Phys. 186(2), 426–456 (2003) · Zbl 1072.74533 · doi:10.1016/S0021-9991(03)00026-3 |
| [50] | Millett, K.C., Dobay, A., Stasiak, A.: Linear random knots and their scaling behavior. Macromolecules 38(2), 601–606 (2005) · doi:10.1021/ma048779a |
| [51] | Millett, K.C., Piatek, M., Rawdon, E.J.: Polygonal knot space near ropelength-minimized knots. J. Knot Theory Ramif. 17(5), 601–631 (2008) · Zbl 1152.57005 · doi:10.1142/S0218216508006282 |
| [52] | Millett, K.C., Rawdon, E.J., Tran, V.T., Stasiak, A.: Symmetry-breaking in cumulative measures of shapes of polymer models. J. Chem. Phys. 133(15), 154113 (2010). Also cross-listed in the Virtual Journal of Biological Physics Research in the November 1, 2010 issue (volume 20, issue 9) |
| [53] | Moore, N.T., Grosberg, A.Y.: Limits of analogy between self-avoidance and topology-driven swelling of polymer loops. Phys. Rev. E, Stat. Nonlinear Soft Matter Phys. 72(6), 061803-1-10 (2005) · doi:10.1103/PhysRevE.72.061803 |
| [54] | Moore, N.T., Grosberg, A.Y.: The abundance of unknots in various models of polymer loops. J. Phys. A, Math. Gen. 39, 9081–9092 (2006) · Zbl 1099.82521 · doi:10.1088/0305-4470/39/29/005 |
| [55] | Moore, N.T., Lua, R.C., Grosberg, A.Y.: Topologically driven swelling of a polymer loop. Proc. Natl. Acad. Sci. USA 101(37), 13431–13435 (2004) · doi:10.1073/pnas.0403383101 |
| [56] | Moore, N.T., Lua, R.C., Grosberg, A.Y.: Under-knotted and over-knotted polymers: 1. Unrestricted loops. In: Calvo, J.A., Millett, K.C., Rawdon, E.J., Stasiak, A. (eds.) Physical and Numerical Models in Knot Theory. Ser. Knots Everything, vol. 36, pp. 363–384. World Sci. Publishing, Singapore (2005) · Zbl 1092.82054 |
| [57] | Moore, N.T., Lua, R.C., Grosberg, A.Y.: Under-knotted and over-knotted polymers: 2. Compact self-avoiding loops. In: Calvo, J.A., Millett, K.C., Rawdon, E.J., Stasiak, A. (eds.) Physical and Numerical Models in Knot Theory. Ser. Knots Everything, vol. 36, pp. 385–398. World Sci. Publishing, Singapore (2005) · Zbl 1092.82053 |
| [58] | Orlandini, E., Whittington, S.: Statistical topology of closed curves: Some applications in polymer physics. Rev. Mod. Phys. 79, 611–642 (2007) · Zbl 1205.82153 · doi:10.1103/RevModPhys.79.611 |
| [59] | Orlandini, E., Tesi, M.C., Janse van Rensburg, E.J., Whittington, S.G.: Asymptotics of knotted lattice polygons. J. Phys. A 31(28), 5953–5967 (1998) · Zbl 0953.82031 · doi:10.1088/0305-4470/31/28/010 |
| [60] | Plunkett, P., Piatek, M., Dobay, A., Kern, J.C., Millett, K.C., Stasiak, A., Rawdon, E.J.: Total curvature and total torsion of knotted polymers. Macromolecules 40(10), 3860–3867 (2007) · doi:10.1021/ma0627673 |
| [61] | Rawdon, E.J., Scharein, R.G.: Upper bounds for equilateral stick numbers. In: Physical Knots: Knotting, Linking, and Folding Geometric Objects in \(\mathbb{R}\)3, Las Vegas, NV, 2001. Contemp. Math., vol. 304, pp. 55–75. Amer. Math. Soc., Providence (2002) |
| [62] | Rawdon, E.J., Dobay, A., Kern, J.C., Millett, K.C., Piatek, M., Plunkett, P., Stasiak, A.: Scaling behavior and equilibrium lengths of knotted polymers. Macromolecules 41(12), 4444–4451 (2008) · doi:10.1021/ma8000803 |
| [63] | Rawdon, E.J., Kern, J.C., Piatek, M., Plunkett, P., Millett, K.C., Stasiak, A.: The effect of knotting on the shape of polymers. Macromolecules 41, 8281–8287 (2008) · doi:10.1021/ma801389c |
| [64] | Rivetti, C., Walker, C., Bustamante, C.: Polymer chain statistics and conformational analysis of DNA molecules with bends or sections of different flexibility. J. Mol. Biol. 280, 058102 (1988) |
| [65] | Salzburg, Z.W., Jacobson, J.D., Fickett, W., Wood, W.W.: Application of the Monte Carlo method to the lattice-gas model. J. Chem. Phys. 30, 65 (1959) · doi:10.1063/1.1729945 |
| [66] | Shimamura, M.K., Deguchi, T.: Anomalous finite-size effects for the mean-squared gyration radius of Gaussian random knots. J. Phys. A 35(18), 241–246 (2002) · Zbl 1053.82507 · doi:10.1088/0305-4470/35/18/102 |
| [67] | Shimamura, M.K., Deguchi, T.: Finite-size and asymptotic behaviors of the gyration radius of knotted cylindrical self-avoiding polygons. Phys. Rev. E, Stat. Nonlinear Soft Matter Phys. 65(5), 051802 (2002) · Zbl 1053.82507 · doi:10.1103/PhysRevE.65.051802 |
| [68] | Tesi, M.C., Janse Van Rensburg, E.J., Orlandini, E., Whittington, S.G.: Monte Carlo study of the interacting self-avoiding walk model in three dimensions. J. Stat. Phys. 82, 155–181 (1996) · Zbl 1042.82555 · doi:10.1007/BF02189229 |
| [69] | Toussaint, G.: The Erdös-Nagy theorem and its ramifications. Comput. Geom. 31, 219–236 (2005) · Zbl 1081.65024 · doi:10.1016/j.comgeo.2004.12.005 |
| [70] | Valle, E., Favre, M., De Los Rios, A., Rosa, A., Dietler, G.: Scaling exponents and probability distributions of DNA end-to-end distance. Phys. Rev. Lett. 95, 158105 (2006) |
| [71] | Vanderzande, C.: Lattice Models of Polymers. Cambridge University Press, Cambridge (1998) · Zbl 0922.76004 |
| [72] | Vologodskii, A.V., Anshelevich, V.V., Lukashin, A.V., Frank-Kamenetskii, M.D.: Statistical mechanics of supercoils and the torsional stiffness of the DNA double helix. Nature 280, 294–298 (1979) · doi:10.1038/280294a0 |
| [73] | Wolfram Research, Inc.: Date and time functions. In: Wolfram Mathematica 7 Documentation. http://reference.wolfram.com/mathematica/tutorial/DateAndTimeFunctions.html . Cited Jan. 2010 |
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.
