Combinatorial vector fields and the valley structure of fitness landscapes. (English) Zbl 1205.92057
Summary: Adaptive (downhill) walks are a computationally convenient way of analyzing the geometric structure of fitness landscapes. Their inherently stochastic nature has limited their mathematical analysis, however. We develop a framework that interprets adaptive walks as deterministic trajectories in combinatorial vector fields and in return associate these combinatorial vector fields with weights that measure their steepness across the landscape. We show that the combinatorial vector fields and their weights have a product structure that is governed by the neutrality of the landscape. This product structure makes practical computations feasible. The framework presented here also provides an alternative, and mathematically more convenient, way of defining notions of valleys, saddle points, and barriers in landscape. As an application, we propose a refined approximation for transition rates between macrostates that are associated with the valleys of the landscape.
MSC:
| 92D15 | Problems related to evolution |
| 05C90 | Applications of graph theory |
| 90C27 | Combinatorial optimization |
| 05C20 | Directed graphs (digraphs), tournaments |
| 65C20 | Probabilistic models, generic numerical methods in probability and statistics |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Becker OM, Karplus M (1997) The topology of multidimensional potential energy surfaces: Theory and application to peptide structure and kinetics. J Chem Phys 106: 1495–1517 · doi:10.1063/1.473299 |
| [2] | Binder K, Young AP (1986) Spin glasses: experimental facts, theoretical concepts, and open questions. Rev Mod Phys 58: 801–976 · doi:10.1103/RevModPhys.58.801 |
| [3] | Doye JP, Miller MA, Welsh DJ (1999) Evolution of the potential energy surface with size for Lennard–Jones clusters. J Chem Phys 111: 8417–8429 · doi:10.1063/1.480217 |
| [4] | Ferreira FF, Fontanari JF, Stadler PF (2000) Landscape statistics of the low autocorrelated binary string problem. J Phys A Math Gen 33: 8635–8647 · Zbl 0970.82020 · doi:10.1088/0305-4470/33/48/304 |
| [5] | Flamm C, Fontana W, Hofacker I, Schuster P (2000) RNA folding kinetics at elementary step resolution. RNA 6: 325–338 · doi:10.1017/S1355838200992161 |
| [6] | Flamm C, Hofacker IL (2008) Beyond energy minimization: approaches to the kinetic folding of RNA. Chem Monthly 139: 447–457 · doi:10.1007/s00706-008-0895-3 |
| [7] | Flamm C, Hofacker IL, Stadler PF, Wolfinger MT (2002) Barrier trees of degenerate landscapes. Z Phys Chem 216: 155–173 |
| [8] | Flamm C, Stadler BMR, Stadler PF (2007) Saddles and barrier in landscapes of generalized search operators. 9th International Workshop, FOGA 2007, Mexico City, Mexico, January 8–11. In: Stephens CR, Toussaint M, Whitley D, Stadler PF (eds) Foundations of genetic algortithms IX. Lecture Notes in Computer Science, vol 4436. Springer, Berlin, pp 194–212 |
| [9] | Flyvbjerg H, Lautrup B (1992) Evolution in a rugged fitness landscape. Phys Rev A 46: 6714–6723 · doi:10.1103/PhysRevA.46.6714 |
| [10] | Fontana W, Stadler PF, Bornberg-Bauer EG, Griesmacher T, Hofacker IL, Tacker M, Tarazona P, Weinberger ED, Schuster P (1993) RNA folding landscapes and combinatory landscapes. Phys Rev E 47: 2083–2099 · doi:10.1103/PhysRevE.47.2083 |
| [11] | Forman R (1998) Combinatorial vector fields and dynamical systems. Math Z 228: 629–681 · Zbl 0922.58063 · doi:10.1007/PL00004638 |
| [12] | Garey M, Johnson D (1979) Computers and intractability. A guide to the theory of \({{\mathcal NP}}\) completeness. Freeman, San Francisco · Zbl 0411.68039 |
| [13] | Garstecki P, Hoang TX, Cieplak M (1999) Energy landscapes, supergraphs, and ”folding funnels” in spin systems. Phys Rev E 60: 3219–3226 · doi:10.1103/PhysRevE.60.3219 |
| [14] | Gillespie JH (1984) Molecular evolution over the mutational landscape. Evolution 38: 1116–1129 · doi:10.2307/2408444 |
| [15] | Jonsson J (2007) Simplicial complexes of graphs. Springer, Berlin |
| [16] | Kauffman SA, Levin S (1987) Towards a general theory of adaptive walks on rugged landscapes. J Theor Biol 128: 11–45 · doi:10.1016/S0022-5193(87)80029-2 |
| [17] | Klotz T, Kobe S (1994) ”Valley Structures” in the phase space of a finite 3D Ising spin glass with {\(\pm\)} i interactions. J Phys A Math Gen 27: L95–L100 · doi:10.1088/0305-4470/27/4/001 |
| [18] | Macken CA, Hagan PS, Perelson AS (1991) Evolutionary walks on rugged landscapes. SIAM J Appl Math 51: 799–827 · Zbl 0755.92014 · doi:10.1137/0151040 |
| [19] | Macken CA, Perelson AS (1989) Protein evolution on rugged landscapes. Proc Natl Acad Sci USA 86: 6191–6195 · doi:10.1073/pnas.86.16.6191 |
| [20] | Mézard M, Parisi G, Virasoro MA (1987) Spin glass theory and beyond. World Scientific, Singapore · Zbl 0992.82500 |
| [21] | Mezey PG (1987) Potential energy hypersurfaces. Elsevier, Amsterdam |
| [22] | Mirny L, Shakhnovich E (2001) Protein folding theory: from lattice to all-atom models. Annu Rev Biophys Biomol Struct 30: 361–396 · doi:10.1146/annurev.biophys.30.1.361 |
| [23] | Niklas KJ (1997) Adaptive walks through fitness landscapes for early vascular land plants. Am J Bot 84: 16–25 · doi:10.2307/2445878 |
| [24] | Orr HA (1999) The evolutionary genetics of adaptation: a simulation study. Genet Res Camb 74: 207–214 · doi:10.1017/S0016672399004164 |
| [25] | Orr HA (2003) The distribution of fitness effects of beneficial mutations. Genetics 163: 1519–1526 |
| [26] | Perelson AS, Macken CA (1995) Protein evolution on partially correlated landscapes. Proc Natl Acad Sci USA 92: 9657–9661 · Zbl 0832.92014 · doi:10.1073/pnas.92.21.9657 |
| [27] | Prügel-Bennett A, Hallam J (2005) Barrier trees MAX-SAT combinatorial optimization cost landscape heuristic search. IEEE Trans Evol Comput 9: 385–397 · doi:10.1109/TEVC.2005.846818 |
| [28] | Reidys CM, Stadler PF (2002) Combinatorial landscapes. SIAM Rev 44: 3–54 SFI preprint 01-03-14 · Zbl 0996.92026 · doi:10.1137/S0036144501395952 |
| [29] | Rokyta DR, Beisel CJ, Joyce P (2006) Properties of adaptive walks on uncorrelated landscapes under strong selection and weak mutation. J Theor Biol 243: 114–120 · doi:10.1016/j.jtbi.2006.06.008 |
| [30] | Van Nimwegen E, Crutchfield JP (2000) Metastable evolutionary dynamics: crossing fitness barriers or escaping via neutral paths?. Bull Math Biol 62: 799–848 · Zbl 1323.92146 · doi:10.1006/bulm.2000.0180 |
| [31] | Wales DJ, Miller MA, Walsh TR (1998) Archetypal energy landscapes. Nature 394: 758–760 · doi:10.1038/29487 |
| [32] | Weinberger ED (1991) Local properties of Kauffman’s N-k model: a tunably rugged energy landscape. Phys Rev A 44: 6399–6413 · doi:10.1103/PhysRevA.44.6399 |
| [33] | Wolfinger MT, Svrcek-Seiler WA, Flamm C, Hofacker IL, Stadler PF (2004) Exact folding dynamics of RNA secondary structures. J Phys A Math Gen 37: 4731–4741 · Zbl 1050.81729 · doi:10.1088/0305-4470/37/17/005 |
| [34] | Wright S (1932) The roles of mutation, inbreeding, crossbreeeding and selection in evolution. In: Jones DF (ed) Proceedings of the sixth international congress on genetics, vol 1. Brooklyn Botanic Gardens, New York, pp 356–366 |
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.
