[{"oa":1,"publisher":"Springer","quality_controlled":"1","date_created":"2018-12-11T11:51:27Z","date_published":"2017-06-01T00:00:00Z","doi":"10.1007/s00453-016-0212-1","page":"681 - 713","publication":"Algorithmica","day":"01","year":"2017","isi":1,"has_accepted_license":"1","project":[{"call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","grant_number":"618091","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation"}],"title":"Towards a runtime comparison of natural and artificial evolution","external_id":{"isi":["000400379500013"]},"article_processing_charge":"No","author":[{"first_name":"Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","full_name":"Paixao, Tiago","orcid":"0000-0003-2361-3953","last_name":"Paixao"},{"last_name":"Pérez Heredia","full_name":"Pérez Heredia, Jorge","first_name":"Jorge"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"},{"id":"42302D54-F248-11E8-B48F-1D18A9856A87","first_name":"Barbora","last_name":"Trubenova","full_name":"Trubenova, Barbora","orcid":"0000-0002-6873-2967"}],"publist_id":"5931","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Paixao, Tiago, et al. “Towards a Runtime Comparison of Natural and Artificial Evolution.” Algorithmica, vol. 78, no. 2, Springer, 2017, pp. 681–713, doi:10.1007/s00453-016-0212-1.","short":"T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 78 (2017) 681–713.","ieee":"T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “Towards a runtime comparison of natural and artificial evolution,” Algorithmica, vol. 78, no. 2. Springer, pp. 681–713, 2017.","ama":"Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. Towards a runtime comparison of natural and artificial evolution. Algorithmica. 2017;78(2):681-713. doi:10.1007/s00453-016-0212-1","apa":"Paixao, T., Pérez Heredia, J., Sudholt, D., & Trubenova, B. (2017). Towards a runtime comparison of natural and artificial evolution. Algorithmica. Springer. https://doi.org/10.1007/s00453-016-0212-1","chicago":"Paixao, Tiago, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “Towards a Runtime Comparison of Natural and Artificial Evolution.” Algorithmica. Springer, 2017. https://doi.org/10.1007/s00453-016-0212-1.","ista":"Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2017. Towards a runtime comparison of natural and artificial evolution. Algorithmica. 78(2), 681–713."},"intvolume":" 78","month":"06","scopus_import":"1","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient."}],"ec_funded":1,"issue":"2","volume":78,"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"7873f665a0c598ac747c908f34cb14b9","file_id":"4805","file_size":710206,"date_updated":"2020-07-14T12:44:44Z","creator":"system","file_name":"IST-2016-658-v1+1_s00453-016-0212-1.pdf","date_created":"2018-12-12T10:10:19Z"}],"publication_status":"published","publication_identifier":{"issn":["01784617"]},"pubrep_id":"658","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","_id":"1336","file_date_updated":"2020-07-14T12:44:44Z","department":[{"_id":"NiBa"},{"_id":"CaGu"}],"ddc":["576"],"date_updated":"2023-09-20T11:14:42Z"},{"publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":118,"related_material":{"record":[{"relation":"research_data","status":"public","id":"9710"}]},"abstract":[{"text":"Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5176114/"}],"scopus_import":"1","intvolume":" 118","month":"01","date_updated":"2023-09-20T11:17:47Z","department":[{"_id":"NiBa"}],"_id":"1199","type":"journal_article","status":"public","year":"2017","isi":1,"publication":"Heredity","day":"01","page":"96 - 109","date_created":"2018-12-11T11:50:40Z","doi":"10.1038/hdy.2016.109","date_published":"2017-01-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Nature Publishing Group","citation":{"chicago":"Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?” Heredity. Nature Publishing Group, 2017. https://doi.org/10.1038/hdy.2016.109.","ista":"Barton NH. 2017. How does epistasis influence the response to selection? Heredity. 118, 96–109.","mla":"Barton, Nicholas H. “How Does Epistasis Influence the Response to Selection?” Heredity, vol. 118, Nature Publishing Group, 2017, pp. 96–109, doi:10.1038/hdy.2016.109.","apa":"Barton, N. H. (2017). How does epistasis influence the response to selection? Heredity. Nature Publishing Group. https://doi.org/10.1038/hdy.2016.109","ama":"Barton NH. How does epistasis influence the response to selection? Heredity. 2017;118:96-109. doi:10.1038/hdy.2016.109","short":"N.H. Barton, Heredity 118 (2017) 96–109.","ieee":"N. H. Barton, “How does epistasis influence the response to selection?,” Heredity, vol. 118. Nature Publishing Group, pp. 96–109, 2017."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000392229100011"]},"article_processing_charge":"No","author":[{"first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","last_name":"Barton"}],"publist_id":"6151","title":"How does epistasis influence the response to selection?","project":[{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","call_identifier":"FP7","_id":"25B07788-B435-11E9-9278-68D0E5697425"}]},{"oa":1,"publisher":"Genetics Society of America","quality_controlled":"1","year":"2017","has_accepted_license":"1","isi":1,"publication":"Genetics","day":"01","page":"367 - 374","date_created":"2018-12-11T11:50:31Z","doi":"10.1534/genetics.116.193946","date_published":"2017-01-01T00:00:00Z","project":[{"name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation"}],"citation":{"ista":"Novak S, Kollár R. 2017. Spatial gene frequency waves under genotype dependent dispersal. Genetics. 205(1), 367–374.","chicago":"Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under Genotype Dependent Dispersal.” Genetics. Genetics Society of America, 2017. https://doi.org/10.1534/genetics.116.193946.","apa":"Novak, S., & Kollár, R. (2017). Spatial gene frequency waves under genotype dependent dispersal. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.116.193946","ama":"Novak S, Kollár R. Spatial gene frequency waves under genotype dependent dispersal. Genetics. 2017;205(1):367-374. doi:10.1534/genetics.116.193946","short":"S. Novak, R. Kollár, Genetics 205 (2017) 367–374.","ieee":"S. Novak and R. Kollár, “Spatial gene frequency waves under genotype dependent dispersal,” Genetics, vol. 205, no. 1. Genetics Society of America, pp. 367–374, 2017.","mla":"Novak, Sebastian, and Richard Kollár. “Spatial Gene Frequency Waves under Genotype Dependent Dispersal.” Genetics, vol. 205, no. 1, Genetics Society of America, 2017, pp. 367–74, doi:10.1534/genetics.116.193946."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000393677300025"]},"article_processing_charge":"No","publist_id":"6188","author":[{"first_name":"Sebastian","id":"461468AE-F248-11E8-B48F-1D18A9856A87","last_name":"Novak","orcid":"0000-0002-2519-824X","full_name":"Novak, Sebastian"},{"first_name":"Richard","full_name":"Kollár, Richard","last_name":"Kollár"}],"title":"Spatial gene frequency waves under genotype dependent dispersal","abstract":[{"text":"Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.","lang":"eng"}],"oa_version":"Submitted Version","scopus_import":"1","intvolume":" 205","month":"01","publication_status":"published","publication_identifier":{"issn":["00166731"]},"language":[{"iso":"eng"}],"file":[{"file_id":"4833","checksum":"7c8ab79cda1f92760bbbbe0f53175bfc","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:10:43Z","file_name":"IST-2016-727-v1+1_SFC_Genetics_final.pdf","date_updated":"2020-07-14T12:44:37Z","file_size":361500,"creator":"system"}],"ec_funded":1,"issue":"1","volume":205,"_id":"1169","type":"journal_article","pubrep_id":"727","status":"public","date_updated":"2023-09-20T11:24:21Z","ddc":["576"],"file_date_updated":"2020-07-14T12:44:37Z","department":[{"_id":"NiBa"}]},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["00166731"]},"ec_funded":1,"volume":205,"issue":"2","pmid":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Adaptation depends critically on the effects of new mutations and their dependency on the genetic background in which they occur. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyze populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high-fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection; effectively removing this barrier to adaptation."}],"intvolume":" 205","month":"02","main_file_link":[{"url":"https://doi.org/10.1534/genetics.116.189340","open_access":"1"}],"scopus_import":"1","date_updated":"2023-09-20T11:35:03Z","department":[{"_id":"NiBa"}],"_id":"1111","status":"public","type":"journal_article","article_type":"original","publication":"Genetics","day":"01","year":"2017","isi":1,"date_created":"2018-12-11T11:50:12Z","date_published":"2017-02-01T00:00:00Z","doi":"10.1534/genetics.116.189340","page":"803 - 825","oa":1,"publisher":"Genetics Society of America","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Heredia, Jorge, et al. “Selection Limits to Adaptive Walks on Correlated Landscapes.” Genetics, vol. 205, no. 2, Genetics Society of America, 2017, pp. 803–25, doi:10.1534/genetics.116.189340.","short":"J. Heredia, B. Trubenova, D. Sudholt, T. Paixao, Genetics 205 (2017) 803–825.","ieee":"J. Heredia, B. Trubenova, D. Sudholt, and T. Paixao, “Selection limits to adaptive walks on correlated landscapes,” Genetics, vol. 205, no. 2. Genetics Society of America, pp. 803–825, 2017.","ama":"Heredia J, Trubenova B, Sudholt D, Paixao T. Selection limits to adaptive walks on correlated landscapes. Genetics. 2017;205(2):803-825. doi:10.1534/genetics.116.189340","apa":"Heredia, J., Trubenova, B., Sudholt, D., & Paixao, T. (2017). Selection limits to adaptive walks on correlated landscapes. Genetics. Genetics Society of America. https://doi.org/10.1534/genetics.116.189340","chicago":"Heredia, Jorge, Barbora Trubenova, Dirk Sudholt, and Tiago Paixao. “Selection Limits to Adaptive Walks on Correlated Landscapes.” Genetics. Genetics Society of America, 2017. https://doi.org/10.1534/genetics.116.189340.","ista":"Heredia J, Trubenova B, Sudholt D, Paixao T. 2017. Selection limits to adaptive walks on correlated landscapes. Genetics. 205(2), 803–825."},"title":"Selection limits to adaptive walks on correlated landscapes","article_processing_charge":"No","external_id":{"pmid":["27881471"],"isi":["000394144900025"]},"author":[{"full_name":"Heredia, Jorge","last_name":"Heredia","first_name":"Jorge"},{"first_name":"Barbora","id":"42302D54-F248-11E8-B48F-1D18A9856A87","last_name":"Trubenova","orcid":"0000-0002-6873-2967","full_name":"Trubenova, Barbora"},{"last_name":"Sudholt","full_name":"Sudholt, Dirk","first_name":"Dirk"},{"last_name":"Paixao","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","first_name":"Tiago"}],"publist_id":"6256","project":[{"grant_number":"618091","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}]},{"abstract":[{"text":"Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the fX174 phage family by first reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 14","month":"01","publication_status":"published","publication_identifier":{"issn":["17425689"]},"language":[{"iso":"eng"}],"file":[{"success":1,"file_id":"5843","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2017_JRSI_Redondo.pdf","date_created":"2019-01-18T09:14:02Z","creator":"dernst","file_size":1092015,"date_updated":"2019-01-18T09:14:02Z"}],"ec_funded":1,"volume":14,"issue":"126","related_material":{"record":[{"relation":"research_data","status":"public","id":"9864"}]},"_id":"1077","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","status":"public","date_updated":"2023-09-20T11:56:34Z","ddc":["570"],"file_date_updated":"2019-01-18T09:14:02Z","department":[{"_id":"NiBa"},{"_id":"JoBo"}],"oa":1,"quality_controlled":"1","publisher":"Royal Society of London","year":"2017","has_accepted_license":"1","isi":1,"publication":"Journal of the Royal Society Interface","day":"04","date_created":"2018-12-11T11:50:01Z","date_published":"2017-01-04T00:00:00Z","doi":"10.1098/rsif.2016.0139","article_number":"20160139","project":[{"grant_number":"250152","name":"Limits to selection in biology and in evolutionary computation","_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"H2020","_id":"2578D616-B435-11E9-9278-68D0E5697425","name":"Selective Barriers to Horizontal Gene Transfer","grant_number":"648440"}],"citation":{"chicago":"Fernandes Redondo, Rodrigo A, Harold de Vladar, Tomasz Włodarski, and Jonathan P Bollback. “Evolutionary Interplay between Structure, Energy and Epistasis in the Coat Protein of the ΦX174 Phage Family.” Journal of the Royal Society Interface. Royal Society of London, 2017. https://doi.org/10.1098/rsif.2016.0139.","ista":"Fernandes Redondo RA, de Vladar H, Włodarski T, Bollback JP. 2017. Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family. Journal of the Royal Society Interface. 14(126), 20160139.","mla":"Fernandes Redondo, Rodrigo A., et al. “Evolutionary Interplay between Structure, Energy and Epistasis in the Coat Protein of the ΦX174 Phage Family.” Journal of the Royal Society Interface, vol. 14, no. 126, 20160139, Royal Society of London, 2017, doi:10.1098/rsif.2016.0139.","short":"R.A. Fernandes Redondo, H. de Vladar, T. Włodarski, J.P. Bollback, Journal of the Royal Society Interface 14 (2017).","ieee":"R. A. Fernandes Redondo, H. de Vladar, T. Włodarski, and J. P. Bollback, “Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family,” Journal of the Royal Society Interface, vol. 14, no. 126. Royal Society of London, 2017.","ama":"Fernandes Redondo RA, de Vladar H, Włodarski T, Bollback JP. Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family. Journal of the Royal Society Interface. 2017;14(126). doi:10.1098/rsif.2016.0139","apa":"Fernandes Redondo, R. A., de Vladar, H., Włodarski, T., & Bollback, J. P. (2017). Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family. Journal of the Royal Society Interface. Royal Society of London. https://doi.org/10.1098/rsif.2016.0139"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000393380400001"]},"article_processing_charge":"Yes (in subscription journal)","publist_id":"6303","author":[{"id":"409D5C96-F248-11E8-B48F-1D18A9856A87","first_name":"Rodrigo A","last_name":"Fernandes Redondo","full_name":"Fernandes Redondo, Rodrigo A","orcid":"0000-0002-5837-2793"},{"id":"2A181218-F248-11E8-B48F-1D18A9856A87","first_name":"Harold","last_name":"Vladar","full_name":"Vladar, Harold","orcid":"0000-0002-5985-7653"},{"full_name":"Włodarski, Tomasz","last_name":"Włodarski","first_name":"Tomasz"},{"first_name":"Jonathan P","id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","last_name":"Bollback","orcid":"0000-0002-4624-4612","full_name":"Bollback, Jonathan P"}],"title":"Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family"}]