---
_id: '723'
abstract:
- lang: eng
text: Escaping local optima is one of the major obstacles to function optimisation.
Using the metaphor of a fitness landscape, local optima correspond to hills separated
by fitness valleys that have to be overcome. We define a class of fitness valleys
of tunable difficulty by considering their length, representing the Hamming path
between the two optima and their depth, the drop in fitness. For this function
class we present a runtime comparison between stochastic search algorithms using
different search strategies. The (1+1) EA is a simple and well-studied evolutionary
algorithm that has to jump across the valley to a point of higher fitness because
it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm
and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population
genetics, are both able to cross the fitness valley by accepting worsening moves.
We show that the runtime of the (1+1) EA depends critically on the length of the
valley while the runtimes of the non-elitist algorithms depend crucially on the
depth of the valley. Moreover, we show that both SSWM and Metropolis can also
efficiently optimise a rugged function consisting of consecutive valleys.
article_processing_charge: No
author:
- first_name: Pietro
full_name: Oliveto, Pietro
last_name: Oliveto
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Jorge
full_name: Pérez Heredia, Jorge
last_name: Pérez Heredia
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
citation:
ama: Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. How to escape
local optima in black box optimisation when non elitism outperforms elitism. Algorithmica.
2018;80(5):1604-1633. doi:10.1007/s00453-017-0369-2
apa: Oliveto, P., Paixao, T., Pérez Heredia, J., Sudholt, D., & Trubenova, B.
(2018). How to escape local optima in black box optimisation when non elitism
outperforms elitism. Algorithmica. Springer. https://doi.org/10.1007/s00453-017-0369-2
chicago: Oliveto, Pietro, Tiago Paixao, Jorge Pérez Heredia, Dirk Sudholt, and Barbora
Trubenova. “How to Escape Local Optima in Black Box Optimisation When Non Elitism
Outperforms Elitism.” Algorithmica. Springer, 2018. https://doi.org/10.1007/s00453-017-0369-2.
ieee: P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “How
to escape local optima in black box optimisation when non elitism outperforms
elitism,” Algorithmica, vol. 80, no. 5. Springer, pp. 1604–1633, 2018.
ista: Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2018. How to
escape local optima in black box optimisation when non elitism outperforms elitism.
Algorithmica. 80(5), 1604–1633.
mla: Oliveto, Pietro, et al. “How to Escape Local Optima in Black Box Optimisation
When Non Elitism Outperforms Elitism.” Algorithmica, vol. 80, no. 5, Springer,
2018, pp. 1604–33, doi:10.1007/s00453-017-0369-2.
short: P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica
80 (2018) 1604–1633.
date_created: 2018-12-11T11:48:09Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2023-09-11T14:11:35Z
day: '01'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1007/s00453-017-0369-2
ec_funded: 1
external_id:
isi:
- '000428239300010'
file:
- access_level: open_access
checksum: 7d92f5d7be81e387edeec4f06442791c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:14Z
date_updated: 2020-07-14T12:47:54Z
file_id: '4674'
file_name: IST-2018-1014-v1+1_2018_Paixao_Escape.pdf
file_size: 691245
relation: main_file
file_date_updated: 2020-07-14T12:47:54Z
has_accepted_license: '1'
intvolume: ' 80'
isi: 1
issue: '5'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 1604 - 1633
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '6957'
pubrep_id: '1014'
quality_controlled: '1'
scopus_import: '1'
status: public
title: How to escape local optima in black box optimisation when non elitism outperforms
elitism
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 80
year: '2018'
...
---
_id: '1111'
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.
article_processing_charge: No
article_type: original
author:
- first_name: Jorge
full_name: Heredia, Jorge
last_name: Heredia
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
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.
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.
ista: Heredia J, Trubenova B, Sudholt D, Paixao T. 2017. Selection limits to adaptive
walks on correlated landscapes. Genetics. 205(2), 803–825.
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.
date_created: 2018-12-11T11:50:12Z
date_published: 2017-02-01T00:00:00Z
date_updated: 2023-09-20T11:35:03Z
day: '01'
department:
- _id: NiBa
doi: 10.1534/genetics.116.189340
ec_funded: 1
external_id:
isi:
- '000394144900025'
pmid:
- '27881471'
intvolume: ' 205'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1534/genetics.116.189340
month: '02'
oa: 1
oa_version: Published Version
page: 803 - 825
pmid: 1
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: Genetics
publication_identifier:
issn:
- '00166731'
publication_status: published
publisher: Genetics Society of America
publist_id: '6256'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Selection limits to adaptive walks on correlated landscapes
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 205
year: '2017'
...
---
_id: '1112'
abstract:
- lang: eng
text: There has been renewed interest in modelling the behaviour of evolutionary
algorithms by more traditional mathematical objects, such as ordinary differential
equations or Markov chains. The advantage is that the analysis becomes greatly
facilitated due to the existence of well established methods. However, this typically
comes at the cost of disregarding information about the process. Here, we introduce
the use of stochastic differential equations (SDEs) for the study of EAs. SDEs
can produce simple analytical results for the dynamics of stochastic processes,
unlike Markov chains which can produce rigorous but unwieldy expressions about
the dynamics. On the other hand, unlike ordinary differential equations (ODEs),
they do not discard information about the stochasticity of the process. We show
that these are especially suitable for the analysis of fixed budget scenarios
and present analogs of the additive and multiplicative drift theorems for SDEs.
We exemplify the use of these methods for two model algorithms ((1+1) EA and RLS)
on two canonical problems(OneMax and LeadingOnes).
author:
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Jorge
full_name: Pérez Heredia, Jorge
last_name: Pérez Heredia
citation:
ama: 'Paixao T, Pérez Heredia J. An application of stochastic differential equations
to evolutionary algorithms. In: Proceedings of the 14th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms. ACM; 2017:3-11. doi:10.1145/3040718.3040729'
apa: 'Paixao, T., & Pérez Heredia, J. (2017). An application of stochastic differential
equations to evolutionary algorithms. In Proceedings of the 14th ACM/SIGEVO
Conference on Foundations of Genetic Algorithms (pp. 3–11). Copenhagen, Denmark:
ACM. https://doi.org/10.1145/3040718.3040729'
chicago: Paixao, Tiago, and Jorge Pérez Heredia. “An Application of Stochastic Differential
Equations to Evolutionary Algorithms.” In Proceedings of the 14th ACM/SIGEVO
Conference on Foundations of Genetic Algorithms, 3–11. ACM, 2017. https://doi.org/10.1145/3040718.3040729.
ieee: T. Paixao and J. Pérez Heredia, “An application of stochastic differential
equations to evolutionary algorithms,” in Proceedings of the 14th ACM/SIGEVO
Conference on Foundations of Genetic Algorithms, Copenhagen, Denmark, 2017,
pp. 3–11.
ista: 'Paixao T, Pérez Heredia J. 2017. An application of stochastic differential
equations to evolutionary algorithms. Proceedings of the 14th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms. FOGA: Foundations of Genetic Algorithms,
3–11.'
mla: Paixao, Tiago, and Jorge Pérez Heredia. “An Application of Stochastic Differential
Equations to Evolutionary Algorithms.” Proceedings of the 14th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms, ACM, 2017, pp. 3–11, doi:10.1145/3040718.3040729.
short: T. Paixao, J. Pérez Heredia, in:, Proceedings of the 14th ACM/SIGEVO Conference
on Foundations of Genetic Algorithms, ACM, 2017, pp. 3–11.
conference:
end_date: 2017-01-15
location: Copenhagen, Denmark
name: 'FOGA: Foundations of Genetic Algorithms'
start_date: 2017-01-12
date_created: 2018-12-11T11:50:12Z
date_published: 2017-01-12T00:00:00Z
date_updated: 2021-01-12T06:48:22Z
day: '12'
department:
- _id: NiBa
doi: 10.1145/3040718.3040729
language:
- iso: eng
month: '01'
oa_version: None
page: 3 - 11
publication: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic
Algorithms
publication_identifier:
isbn:
- 978-145034651-1
publication_status: published
publisher: ACM
publist_id: '6255'
quality_controlled: '1'
scopus_import: 1
status: public
title: An application of stochastic differential equations to evolutionary algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '696'
abstract:
- lang: eng
text: Mutator strains are expected to evolve when the availability and effect of
beneficial mutations are high enough to counteract the disadvantage from deleterious
mutations that will inevitably accumulate. As the population becomes more adapted
to its environment, both availability and effect of beneficial mutations necessarily
decrease and mutation rates are predicted to decrease. It has been shown that
certain molecular mechanisms can lead to increased mutation rates when the organism
finds itself in a stressful environment. While this may be a correlated response
to other functions, it could also be an adaptive mechanism, raising mutation rates
only when it is most advantageous. Here, we use a mathematical model to investigate
the plausibility of the adaptive hypothesis. We show that such a mechanism can
be mantained if the population is subjected to diverse stresses. By simulating
various antibiotic treatment schemes, we find that combination treatments can
reduce the effectiveness of second-order selection on stress-induced mutagenesis.
We discuss the implications of our results to strategies of antibiotic therapy.
article_number: e1005609
article_type: original
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
orcid: 0000-0002-2519-824X
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: 'Lukacisinova M, Novak S, Paixao T. Stress induced mutagenesis: Stress diversity
facilitates the persistence of mutator genes. PLoS Computational Biology.
2017;13(7). doi:10.1371/journal.pcbi.1005609'
apa: 'Lukacisinova, M., Novak, S., & Paixao, T. (2017). Stress induced mutagenesis:
Stress diversity facilitates the persistence of mutator genes. PLoS Computational
Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005609'
chicago: 'Lukacisinova, Marta, Sebastian Novak, and Tiago Paixao. “Stress Induced
Mutagenesis: Stress Diversity Facilitates the Persistence of Mutator Genes.” PLoS
Computational Biology. Public Library of Science, 2017. https://doi.org/10.1371/journal.pcbi.1005609.'
ieee: 'M. Lukacisinova, S. Novak, and T. Paixao, “Stress induced mutagenesis: Stress
diversity facilitates the persistence of mutator genes,” PLoS Computational
Biology, vol. 13, no. 7. Public Library of Science, 2017.'
ista: 'Lukacisinova M, Novak S, Paixao T. 2017. Stress induced mutagenesis: Stress
diversity facilitates the persistence of mutator genes. PLoS Computational Biology.
13(7), e1005609.'
mla: 'Lukacisinova, Marta, et al. “Stress Induced Mutagenesis: Stress Diversity
Facilitates the Persistence of Mutator Genes.” PLoS Computational Biology,
vol. 13, no. 7, e1005609, Public Library of Science, 2017, doi:10.1371/journal.pcbi.1005609.'
short: M. Lukacisinova, S. Novak, T. Paixao, PLoS Computational Biology 13 (2017).
date_created: 2018-12-11T11:47:58Z
date_published: 2017-07-18T00:00:00Z
date_updated: 2024-03-25T23:30:14Z
day: '18'
ddc:
- '576'
department:
- _id: ToBo
- _id: NiBa
- _id: CaGu
doi: 10.1371/journal.pcbi.1005609
ec_funded: 1
file:
- access_level: open_access
checksum: 9143c290fa6458ed2563bff4b295554a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:01Z
date_updated: 2020-07-14T12:47:46Z
file_id: '5117'
file_name: IST-2017-894-v1+1_journal.pcbi.1005609.pdf
file_size: 3775716
relation: main_file
file_date_updated: 2020-07-14T12:47:46Z
has_accepted_license: '1'
intvolume: ' 13'
issue: '7'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: PLoS Computational Biology
publication_identifier:
issn:
- 1553734X
publication_status: published
publisher: Public Library of Science
publist_id: '7004'
pubrep_id: '894'
quality_controlled: '1'
related_material:
record:
- id: '9849'
relation: research_data
status: public
- id: '9850'
relation: research_data
status: public
- id: '9851'
relation: research_data
status: public
- id: '9852'
relation: research_data
status: public
- id: '6263'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: 'Stress induced mutagenesis: Stress diversity facilitates the persistence of
mutator genes'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2017'
...
---
_id: '1336'
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.
article_processing_charge: No
author:
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Jorge
full_name: Pérez Heredia, Jorge
last_name: Pérez Heredia
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
citation:
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.
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.
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.
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.
date_created: 2018-12-11T11:51:27Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T11:14:42Z
day: '01'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1007/s00453-016-0212-1
ec_funded: 1
external_id:
isi:
- '000400379500013'
file:
- access_level: open_access
checksum: 7873f665a0c598ac747c908f34cb14b9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:19Z
date_updated: 2020-07-14T12:44:44Z
file_id: '4805'
file_name: IST-2016-658-v1+1_s00453-016-0212-1.pdf
file_size: 710206
relation: main_file
file_date_updated: 2020-07-14T12:44:44Z
has_accepted_license: '1'
intvolume: ' 78'
isi: 1
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 681 - 713
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: Algorithmica
publication_identifier:
issn:
- '01784617'
publication_status: published
publisher: Springer
publist_id: '5931'
pubrep_id: '658'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Towards a runtime comparison of natural and artificial evolution
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 78
year: '2017'
...
---
_id: '1351'
abstract:
- lang: eng
text: The behaviour of gene regulatory networks (GRNs) is typically analysed using
simulation-based statistical testing-like methods. In this paper, we demonstrate
that we can replace this approach by a formal verification-like method that gives
higher assurance and scalability. We focus on Wagner’s weighted GRN model with
varying weights, which is used in evolutionary biology. In the model, weight parameters
represent the gene interaction strength that may change due to genetic mutations.
For a property of interest, we synthesise the constraints over the parameter space
that represent the set of GRNs satisfying the property. We experimentally show
that our parameter synthesis procedure computes the mutational robustness of GRNs—an
important problem of interest in evolutionary biology—more efficiently than the
classical simulation method. We specify the property in linear temporal logic.
We employ symbolic bounded model checking and SMT solving to compute the space
of GRNs that satisfy the property, which amounts to synthesizing a set of linear
constraints on the weights.
article_processing_charge: No
author:
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking
the evolution of gene regulatory networks. Acta Informatica. 2017;54(8):765-787.
doi:10.1007/s00236-016-0278-x
apa: Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., & Petrov,
T. (2017). Model checking the evolution of gene regulatory networks. Acta Informatica.
Springer. https://doi.org/10.1007/s00236-016-0278-x
chicago: Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago
Paixao, and Tatjana Petrov. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica. Springer, 2017. https://doi.org/10.1007/s00236-016-0278-x.
ieee: M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov,
“Model checking the evolution of gene regulatory networks,” Acta Informatica,
vol. 54, no. 8. Springer, pp. 765–787, 2017.
ista: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2017. Model
checking the evolution of gene regulatory networks. Acta Informatica. 54(8), 765–787.
mla: Giacobbe, Mirco, et al. “Model Checking the Evolution of Gene Regulatory Networks.”
Acta Informatica, vol. 54, no. 8, Springer, 2017, pp. 765–87, doi:10.1007/s00236-016-0278-x.
short: M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, Acta
Informatica 54 (2017) 765–787.
date_created: 2018-12-11T11:51:32Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2025-05-28T11:57:04Z
day: '01'
ddc:
- '006'
- '576'
department:
- _id: ToHe
- _id: CaGu
- _id: NiBa
doi: 10.1007/s00236-016-0278-x
ec_funded: 1
external_id:
isi:
- '000414343200003'
file:
- access_level: open_access
checksum: 4e661d9135d7f8c342e8e258dee76f3e
content_type: application/pdf
creator: dernst
date_created: 2019-01-17T15:57:29Z
date_updated: 2020-07-14T12:44:46Z
file_id: '5841'
file_name: 2017_ActaInformatica_Giacobbe.pdf
file_size: 755241
relation: main_file
file_date_updated: 2020-07-14T12:44:46Z
has_accepted_license: '1'
intvolume: ' 54'
isi: 1
issue: '8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 765 - 787
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: Acta Informatica
publication_identifier:
issn:
- '00015903'
publication_status: published
publisher: Springer
publist_id: '5898'
pubrep_id: '649'
quality_controlled: '1'
related_material:
record:
- id: '1835'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Model checking the evolution of gene regulatory networks
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...
---
_id: '954'
abstract:
- lang: eng
text: Understanding the relation between genotype and phenotype remains a major
challenge. The difficulty of predicting individual mutation effects, and particularly
the interactions between them, has prevented the development of a comprehensive
theory that links genotypic changes to their phenotypic effects. We show that
a general thermodynamic framework for gene regulation, based on a biophysical
understanding of protein-DNA binding, accurately predicts the sign of epistasis
in a canonical cis-regulatory element consisting of overlapping RNA polymerase
and repressor binding sites. Sign and magnitude of individual mutation effects
are sufficient to predict the sign of epistasis and its environmental dependence.
Thus, the thermodynamic model offers the correct null prediction for epistasis
between mutations across DNA-binding sites. Our results indicate that a predictive
theory for the effects of cis-regulatory mutations is possible from first principles,
as long as the essential molecular mechanisms and the constraints these impose
on a biological system are accounted for.
article_number: e25192
article_processing_charge: Yes
author:
- first_name: Mato
full_name: Lagator, Mato
id: 345D25EC-F248-11E8-B48F-1D18A9856A87
last_name: Lagator
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Jonathan P
full_name: Bollback, Jonathan P
id: 2C6FA9CC-F248-11E8-B48F-1D18A9856A87
last_name: Bollback
orcid: 0000-0002-4624-4612
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
citation:
ama: Lagator M, Paixao T, Barton NH, Bollback JP, Guet CC. On the mechanistic nature
of epistasis in a canonical cis-regulatory element. eLife. 2017;6. doi:10.7554/eLife.25192
apa: Lagator, M., Paixao, T., Barton, N. H., Bollback, J. P., & Guet, C. C.
(2017). On the mechanistic nature of epistasis in a canonical cis-regulatory element.
ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.25192
chicago: Lagator, Mato, Tiago Paixao, Nicholas H Barton, Jonathan P Bollback, and
Calin C Guet. “On the Mechanistic Nature of Epistasis in a Canonical Cis-Regulatory
Element.” ELife. eLife Sciences Publications, 2017. https://doi.org/10.7554/eLife.25192.
ieee: M. Lagator, T. Paixao, N. H. Barton, J. P. Bollback, and C. C. Guet, “On the
mechanistic nature of epistasis in a canonical cis-regulatory element,” eLife,
vol. 6. eLife Sciences Publications, 2017.
ista: Lagator M, Paixao T, Barton NH, Bollback JP, Guet CC. 2017. On the mechanistic
nature of epistasis in a canonical cis-regulatory element. eLife. 6, e25192.
mla: Lagator, Mato, et al. “On the Mechanistic Nature of Epistasis in a Canonical
Cis-Regulatory Element.” ELife, vol. 6, e25192, eLife Sciences Publications,
2017, doi:10.7554/eLife.25192.
short: M. Lagator, T. Paixao, N.H. Barton, J.P. Bollback, C.C. Guet, ELife 6 (2017).
date_created: 2018-12-11T11:49:23Z
date_published: 2017-05-18T00:00:00Z
date_updated: 2023-09-22T10:01:17Z
day: '18'
ddc:
- '576'
department:
- _id: CaGu
- _id: NiBa
- _id: JoBo
doi: 10.7554/eLife.25192
ec_funded: 1
external_id:
isi:
- '000404024800001'
file:
- access_level: open_access
checksum: 59cdd4400fb41280122d414fea971546
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:49Z
date_updated: 2020-07-14T12:48:16Z
file_id: '5306'
file_name: IST-2017-841-v1+1_elife-25192-v2.pdf
file_size: 2441529
relation: main_file
- access_level: open_access
checksum: b69024880558b858eb8c5d47a92b6377
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:50Z
date_updated: 2020-07-14T12:48:16Z
file_id: '5307'
file_name: IST-2017-841-v1+2_elife-25192-figures-v2.pdf
file_size: 3752660
relation: main_file
file_date_updated: 2020-07-14T12:48:16Z
has_accepted_license: '1'
intvolume: ' 6'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 2578D616-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '648440'
name: Selective Barriers to Horizontal Gene Transfer
publication: eLife
publication_identifier:
issn:
- 2050084X
publication_status: published
publisher: eLife Sciences Publications
publist_id: '6460'
pubrep_id: '841'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the mechanistic nature of epistasis in a canonical cis-regulatory element
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 6
year: '2017'
...
---
_id: '9849'
abstract:
- lang: eng
text: This text provides additional information about the model, a derivation of
the analytic results in Eq (4), and details about simulations of an additional
parameter set.
article_processing_charge: No
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Lukacisinova M, Novak S, Paixao T. Modelling and simulation details. 2017.
doi:10.1371/journal.pcbi.1005609.s001
apa: Lukacisinova, M., Novak, S., & Paixao, T. (2017). Modelling and simulation
details. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005609.s001
chicago: Lukacisinova, Marta, Sebastian Novak, and Tiago Paixao. “Modelling and
Simulation Details.” Public Library of Science, 2017. https://doi.org/10.1371/journal.pcbi.1005609.s001.
ieee: M. Lukacisinova, S. Novak, and T. Paixao, “Modelling and simulation details.”
Public Library of Science, 2017.
ista: Lukacisinova M, Novak S, Paixao T. 2017. Modelling and simulation details,
Public Library of Science, 10.1371/journal.pcbi.1005609.s001.
mla: Lukacisinova, Marta, et al. Modelling and Simulation Details. Public
Library of Science, 2017, doi:10.1371/journal.pcbi.1005609.s001.
short: M. Lukacisinova, S. Novak, T. Paixao, (2017).
date_created: 2021-08-09T14:02:34Z
date_published: 2017-07-18T00:00:00Z
date_updated: 2023-02-23T12:55:39Z
day: '18'
department:
- _id: ToBo
- _id: NiBa
- _id: CaGu
doi: 10.1371/journal.pcbi.1005609.s001
month: '07'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '696'
relation: used_in_publication
status: public
status: public
title: Modelling and simulation details
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2017'
...
---
_id: '9850'
abstract:
- lang: eng
text: In this text, we discuss how a cost of resistance and the possibility of lethal
mutations impact our model.
article_processing_charge: No
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Lukacisinova M, Novak S, Paixao T. Extensions of the model. 2017. doi:10.1371/journal.pcbi.1005609.s002
apa: Lukacisinova, M., Novak, S., & Paixao, T. (2017). Extensions of the model.
Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005609.s002
chicago: Lukacisinova, Marta, Sebastian Novak, and Tiago Paixao. “Extensions of
the Model.” Public Library of Science, 2017. https://doi.org/10.1371/journal.pcbi.1005609.s002.
ieee: M. Lukacisinova, S. Novak, and T. Paixao, “Extensions of the model.” Public
Library of Science, 2017.
ista: Lukacisinova M, Novak S, Paixao T. 2017. Extensions of the model, Public Library
of Science, 10.1371/journal.pcbi.1005609.s002.
mla: Lukacisinova, Marta, et al. Extensions of the Model. Public Library
of Science, 2017, doi:10.1371/journal.pcbi.1005609.s002.
short: M. Lukacisinova, S. Novak, T. Paixao, (2017).
date_created: 2021-08-09T14:05:24Z
date_published: 2017-07-18T00:00:00Z
date_updated: 2023-02-23T12:55:39Z
day: '18'
department:
- _id: ToBo
- _id: CaGu
- _id: NiBa
doi: 10.1371/journal.pcbi.1005609.s002
month: '07'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '696'
relation: used_in_publication
status: public
status: public
title: Extensions of the model
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2017'
...
---
_id: '9851'
abstract:
- lang: eng
text: Based on the intuitive derivation of the dynamics of SIM allele frequency
pM in the main text, we present a heuristic prediction for the long-term SIM allele
frequencies with χ > 1 stresses and compare it to numerical simulations.
article_processing_charge: No
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Lukacisinova M, Novak S, Paixao T. Heuristic prediction for multiple stresses.
2017. doi:10.1371/journal.pcbi.1005609.s003
apa: Lukacisinova, M., Novak, S., & Paixao, T. (2017). Heuristic prediction
for multiple stresses. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005609.s003
chicago: Lukacisinova, Marta, Sebastian Novak, and Tiago Paixao. “Heuristic Prediction
for Multiple Stresses.” Public Library of Science, 2017. https://doi.org/10.1371/journal.pcbi.1005609.s003.
ieee: M. Lukacisinova, S. Novak, and T. Paixao, “Heuristic prediction for multiple
stresses.” Public Library of Science, 2017.
ista: Lukacisinova M, Novak S, Paixao T. 2017. Heuristic prediction for multiple
stresses, Public Library of Science, 10.1371/journal.pcbi.1005609.s003.
mla: Lukacisinova, Marta, et al. Heuristic Prediction for Multiple Stresses.
Public Library of Science, 2017, doi:10.1371/journal.pcbi.1005609.s003.
short: M. Lukacisinova, S. Novak, T. Paixao, (2017).
date_created: 2021-08-09T14:08:14Z
date_published: 2017-07-18T00:00:00Z
date_updated: 2023-02-23T12:55:39Z
day: '18'
department:
- _id: ToBo
- _id: CaGu
- _id: NiBa
doi: 10.1371/journal.pcbi.1005609.s003
month: '07'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '696'
relation: used_in_publication
status: public
status: public
title: Heuristic prediction for multiple stresses
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2017'
...
---
_id: '9852'
abstract:
- lang: eng
text: We show how different combination strategies affect the fraction of individuals
that are multi-resistant.
article_processing_charge: No
author:
- first_name: Marta
full_name: Lukacisinova, Marta
id: 4342E402-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisinova
orcid: 0000-0002-2519-8004
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Lukacisinova M, Novak S, Paixao T. Resistance frequencies for different combination
strategies. 2017. doi:10.1371/journal.pcbi.1005609.s004
apa: Lukacisinova, M., Novak, S., & Paixao, T. (2017). Resistance frequencies
for different combination strategies. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1005609.s004
chicago: Lukacisinova, Marta, Sebastian Novak, and Tiago Paixao. “Resistance Frequencies
for Different Combination Strategies.” Public Library of Science, 2017. https://doi.org/10.1371/journal.pcbi.1005609.s004.
ieee: M. Lukacisinova, S. Novak, and T. Paixao, “Resistance frequencies for different
combination strategies.” Public Library of Science, 2017.
ista: Lukacisinova M, Novak S, Paixao T. 2017. Resistance frequencies for different
combination strategies, Public Library of Science, 10.1371/journal.pcbi.1005609.s004.
mla: Lukacisinova, Marta, et al. Resistance Frequencies for Different Combination
Strategies. Public Library of Science, 2017, doi:10.1371/journal.pcbi.1005609.s004.
short: M. Lukacisinova, S. Novak, T. Paixao, (2017).
date_created: 2021-08-09T14:11:40Z
date_published: 2017-07-18T00:00:00Z
date_updated: 2023-02-23T12:55:39Z
day: '18'
department:
- _id: ToBo
- _id: CaGu
- _id: NiBa
doi: 10.1371/journal.pcbi.1005609.s004
month: '07'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '696'
relation: used_in_publication
status: public
status: public
title: Resistance frequencies for different combination strategies
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2017'
...
---
_id: '1349'
abstract:
- lang: eng
text: Crossing fitness valleys is one of the major obstacles to function optimization.
In this paper we investigate how the structure of the fitness valley, namely its
depth d and length ℓ, influence the runtime of different strategies for crossing
these valleys. We present a runtime comparison between the (1+1) EA and two non-elitist
nature-inspired algorithms, Strong Selection Weak Mutation (SSWM) and the Metropolis
algorithm. While the (1+1) EA has to jump across the valley to a point of higher
fitness because it does not accept decreasing moves, the non-elitist algorithms
may cross the valley by accepting worsening moves. We show that while the runtime
of the (1+1) EA algorithm depends critically on the length of the valley, the
runtimes of the non-elitist algorithms depend crucially only on the depth of the
valley. In particular, the expected runtime of both SSWM and Metropolis is polynomial
in ℓ and exponential in d while the (1+1) EA is efficient only for valleys of
small length. Moreover, we show that both SSWM and Metropolis can also efficiently
optimize a rugged function consisting of consecutive valleys.
author:
- first_name: Pietro
full_name: Oliveto, Pietro
last_name: Oliveto
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Jorge
full_name: Heredia, Jorge
last_name: Heredia
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
citation:
ama: 'Oliveto P, Paixao T, Heredia J, Sudholt D, Trubenova B. When non-elitism outperforms
elitism for crossing fitness valleys. In: Proceedings of the Genetic and Evolutionary
Computation Conference 2016 . ACM; 2016:1163-1170. doi:10.1145/2908812.2908909'
apa: 'Oliveto, P., Paixao, T., Heredia, J., Sudholt, D., & Trubenova, B. (2016).
When non-elitism outperforms elitism for crossing fitness valleys. In Proceedings
of the Genetic and Evolutionary Computation Conference 2016 (pp. 1163–1170).
Denver, CO, USA: ACM. https://doi.org/10.1145/2908812.2908909'
chicago: Oliveto, Pietro, Tiago Paixao, Jorge Heredia, Dirk Sudholt, and Barbora
Trubenova. “When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys.”
In Proceedings of the Genetic and Evolutionary Computation Conference 2016
, 1163–70. ACM, 2016. https://doi.org/10.1145/2908812.2908909.
ieee: P. Oliveto, T. Paixao, J. Heredia, D. Sudholt, and B. Trubenova, “When non-elitism
outperforms elitism for crossing fitness valleys,” in Proceedings of the Genetic
and Evolutionary Computation Conference 2016 , Denver, CO, USA, 2016, pp.
1163–1170.
ista: 'Oliveto P, Paixao T, Heredia J, Sudholt D, Trubenova B. 2016. When non-elitism
outperforms elitism for crossing fitness valleys. Proceedings of the Genetic and
Evolutionary Computation Conference 2016 . GECCO: Genetic and evolutionary computation
conference, 1163–1170.'
mla: Oliveto, Pietro, et al. “When Non-Elitism Outperforms Elitism for Crossing
Fitness Valleys.” Proceedings of the Genetic and Evolutionary Computation Conference
2016 , ACM, 2016, pp. 1163–70, doi:10.1145/2908812.2908909.
short: P. Oliveto, T. Paixao, J. Heredia, D. Sudholt, B. Trubenova, in:, Proceedings
of the Genetic and Evolutionary Computation Conference 2016 , ACM, 2016, pp. 1163–1170.
conference:
end_date: 2016-07-24
location: Denver, CO, USA
name: 'GECCO: Genetic and evolutionary computation conference'
start_date: 2016-07-20
date_created: 2018-12-11T11:51:31Z
date_published: 2016-07-20T00:00:00Z
date_updated: 2021-01-12T06:50:03Z
day: '20'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1145/2908812.2908909
ec_funded: 1
file:
- access_level: open_access
checksum: a1896e39e4113f2711e46b435d5f3e69
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:27Z
date_updated: 2020-07-14T12:44:45Z
file_id: '5214'
file_name: IST-2016-650-v1+1_p1163-oliveto.pdf
file_size: 979026
relation: main_file
file_date_updated: 2020-07-14T12:44:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 1163 - 1170
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: 'Proceedings of the Genetic and Evolutionary Computation Conference 2016 '
publication_status: published
publisher: ACM
publist_id: '5900'
pubrep_id: '650'
quality_controlled: '1'
scopus_import: 1
status: public
title: When non-elitism outperforms elitism for crossing fitness valleys
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '1359'
abstract:
- lang: eng
text: "The role of gene interactions in the evolutionary process has long\r\nbeen
controversial. Although some argue that they are not of\r\nimportance, because
most variation is additive, others claim that\r\ntheir effect in the long term
can be substantial. Here, we focus on\r\nthe long-term effects of genetic interactions
under directional\r\nselection assuming no mutation or dominance, and that epistasis
is\r\nsymmetrical overall. We ask by how much the mean of a complex\r\ntrait can
be increased by selection and analyze two extreme\r\nregimes, in which either
drift or selection dominate the dynamics\r\nof allele frequencies. In both scenarios,
epistatic interactions affect\r\nthe long-term response to selection by modulating
the additive\r\ngenetic variance. When drift dominates, we extend Robertson\r\n’\r\ns\r\n[Robertson
A (1960)\r\nProc R Soc Lond B Biol Sci\r\n153(951):234\r\n−\r\n249]\r\nargument
to show that, for any form of epistasis, the total response\r\nof a haploid population
is proportional to the initial total genotypic\r\nvariance. In contrast, the total
response of a diploid population is\r\nincreased by epistasis, for a given initial
genotypic variance. When\r\nselection dominates, we show that the total selection
response can\r\nonly be increased by epistasis when s\r\nome initially deleterious
alleles\r\nbecome favored as the genetic background changes. We find a sim-\r\nple
approximation for this effect and show that, in this regime, it is\r\nthe structure
of the genotype - phenotype map that matters and not\r\nthe variance components
of the population."
article_processing_charge: No
article_type: original
author:
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Paixao T, Barton NH. The effect of gene interactions on the long-term response
to selection. PNAS. 2016;113(16):4422-4427. doi:10.1073/pnas.1518830113
apa: Paixao, T., & Barton, N. H. (2016). The effect of gene interactions on
the long-term response to selection. PNAS. National Academy of Sciences.
https://doi.org/10.1073/pnas.1518830113
chicago: Paixao, Tiago, and Nicholas H Barton. “The Effect of Gene Interactions
on the Long-Term Response to Selection.” PNAS. National Academy of Sciences,
2016. https://doi.org/10.1073/pnas.1518830113.
ieee: T. Paixao and N. H. Barton, “The effect of gene interactions on the long-term
response to selection,” PNAS, vol. 113, no. 16. National Academy of Sciences,
pp. 4422–4427, 2016.
ista: Paixao T, Barton NH. 2016. The effect of gene interactions on the long-term
response to selection. PNAS. 113(16), 4422–4427.
mla: Paixao, Tiago, and Nicholas H. Barton. “The Effect of Gene Interactions on
the Long-Term Response to Selection.” PNAS, vol. 113, no. 16, National
Academy of Sciences, 2016, pp. 4422–27, doi:10.1073/pnas.1518830113.
short: T. Paixao, N.H. Barton, PNAS 113 (2016) 4422–4427.
date_created: 2018-12-11T11:51:34Z
date_published: 2016-04-19T00:00:00Z
date_updated: 2021-01-12T06:50:08Z
day: '19'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1073/pnas.1518830113
ec_funded: 1
external_id:
pmid:
- '27044080'
intvolume: ' 113'
issue: '16'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4843425/
month: '04'
oa: 1
oa_version: Published Version
page: 4422 - 4427
pmid: 1
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: PNAS
publication_status: published
publisher: National Academy of Sciences
publist_id: '5886'
quality_controlled: '1'
scopus_import: 1
status: public
title: The effect of gene interactions on the long-term response to selection
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 113
year: '2016'
...
---
_id: '1666'
abstract:
- lang: eng
text: Evolution of gene regulation is crucial for our understanding of the phenotypic
differences between species, populations and individuals. Sequence-specific binding
of transcription factors to the regulatory regions on the DNA is a key regulatory
mechanism that determines gene expression and hence heritable phenotypic variation.
We use a biophysical model for directional selection on gene expression to estimate
the rates of gain and loss of transcription factor binding sites (TFBS) in finite
populations under both point and insertion/deletion mutations. Our results show
that these rates are typically slow for a single TFBS in an isolated DNA region,
unless the selection is extremely strong. These rates decrease drastically with
increasing TFBS length or increasingly specific protein-DNA interactions, making
the evolution of sites longer than ∼ 10 bp unlikely on typical eukaryotic speciation
timescales. Similarly, evolution converges to the stationary distribution of binding
sequences very slowly, making the equilibrium assumption questionable. The availability
of longer regulatory sequences in which multiple binding sites can evolve simultaneously,
the presence of “pre-sites” or partially decayed old sites in the initial sequence,
and biophysical cooperativity between transcription factors, can all facilitate
gain of TFBS and reconcile theoretical calculations with timescales inferred from
comparative genomics.
author:
- first_name: Murat
full_name: Tugrul, Murat
id: 37C323C6-F248-11E8-B48F-1D18A9856A87
last_name: Tugrul
orcid: 0000-0002-8523-0758
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Gasper
full_name: Tkacik, Gasper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkacik
orcid: 0000-0002-6699-1455
citation:
ama: Tugrul M, Paixao T, Barton NH, Tkačik G. Dynamics of transcription factor binding
site evolution. PLoS Genetics. 2015;11(11). doi:10.1371/journal.pgen.1005639
apa: Tugrul, M., Paixao, T., Barton, N. H., & Tkačik, G. (2015). Dynamics of
transcription factor binding site evolution. PLoS Genetics. Public Library
of Science. https://doi.org/10.1371/journal.pgen.1005639
chicago: Tugrul, Murat, Tiago Paixao, Nicholas H Barton, and Gašper Tkačik. “Dynamics
of Transcription Factor Binding Site Evolution.” PLoS Genetics. Public
Library of Science, 2015. https://doi.org/10.1371/journal.pgen.1005639.
ieee: M. Tugrul, T. Paixao, N. H. Barton, and G. Tkačik, “Dynamics of transcription
factor binding site evolution,” PLoS Genetics, vol. 11, no. 11. Public
Library of Science, 2015.
ista: Tugrul M, Paixao T, Barton NH, Tkačik G. 2015. Dynamics of transcription factor
binding site evolution. PLoS Genetics. 11(11).
mla: Tugrul, Murat, et al. “Dynamics of Transcription Factor Binding Site Evolution.”
PLoS Genetics, vol. 11, no. 11, Public Library of Science, 2015, doi:10.1371/journal.pgen.1005639.
short: M. Tugrul, T. Paixao, N.H. Barton, G. Tkačik, PLoS Genetics 11 (2015).
date_created: 2018-12-11T11:53:21Z
date_published: 2015-11-06T00:00:00Z
date_updated: 2023-09-07T11:53:49Z
day: '06'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
- _id: GaTk
doi: 10.1371/journal.pgen.1005639
ec_funded: 1
file:
- access_level: open_access
checksum: a4e72fca5ccf40ddacf4d08c8e46b554
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:58Z
date_updated: 2020-07-14T12:45:10Z
file_id: '4657'
file_name: IST-2016-463-v1+1_journal.pgen.1005639.pdf
file_size: 2580778
relation: main_file
file_date_updated: 2020-07-14T12:45:10Z
has_accepted_license: '1'
intvolume: ' 11'
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: PLoS Genetics
publication_status: published
publisher: Public Library of Science
publist_id: '5483'
pubrep_id: '463'
quality_controlled: '1'
related_material:
record:
- id: '9712'
relation: research_data
status: public
- id: '1131'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Dynamics of transcription factor binding site evolution
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2015'
...
---
_id: '1835'
abstract:
- lang: eng
text: The behaviour of gene regulatory networks (GRNs) is typically analysed using
simulation-based statistical testing-like methods. In this paper, we demonstrate
that we can replace this approach by a formal verification-like method that gives
higher assurance and scalability. We focus on Wagner’s weighted GRN model with
varying weights, which is used in evolutionary biology. In the model, weight parameters
represent the gene interaction strength that may change due to genetic mutations.
For a property of interest, we synthesise the constraints over the parameter space
that represent the set of GRNs satisfying the property. We experimentally show
that our parameter synthesis procedure computes the mutational robustness of GRNs
–an important problem of interest in evolutionary biology– more efficiently than
the classical simulation method. We specify the property in linear temporal logics.
We employ symbolic bounded model checking and SMT solving to compute the space
of GRNs that satisfy the property, which amounts to synthesizing a set of linear
constraints on the weights.
acknowledgement: "SNSF Early Postdoc.Mobility Fellowship, the grant number P2EZP2
148797.\r\n"
alternative_title:
- LNCS
author:
- first_name: Mirco
full_name: Giacobbe, Mirco
id: 3444EA5E-F248-11E8-B48F-1D18A9856A87
last_name: Giacobbe
orcid: 0000-0001-8180-0904
- first_name: Calin C
full_name: Guet, Calin C
id: 47F8433E-F248-11E8-B48F-1D18A9856A87
last_name: Guet
orcid: 0000-0001-6220-2052
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Tatjana
full_name: Petrov, Tatjana
id: 3D5811FC-F248-11E8-B48F-1D18A9856A87
last_name: Petrov
orcid: 0000-0002-9041-0905
citation:
ama: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking
gene regulatory networks. 2015;9035:469-483. doi:10.1007/978-3-662-46681-0_47
apa: 'Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., &
Petrov, T. (2015). Model checking gene regulatory networks. Presented at the TACAS:
Tools and Algorithms for the Construction and Analysis of Systems, London, United
Kingdom: Springer. https://doi.org/10.1007/978-3-662-46681-0_47'
chicago: Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago
Paixao, and Tatjana Petrov. “Model Checking Gene Regulatory Networks.” Lecture
Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-46681-0_47.
ieee: M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov,
“Model checking gene regulatory networks,” vol. 9035. Springer, pp. 469–483, 2015.
ista: Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2015. Model
checking gene regulatory networks. 9035, 469–483.
mla: Giacobbe, Mirco, et al. Model Checking Gene Regulatory Networks. Vol.
9035, Springer, 2015, pp. 469–83, doi:10.1007/978-3-662-46681-0_47.
short: M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, 9035
(2015) 469–483.
conference:
end_date: 2015-04-18
location: London, United Kingdom
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2015-04-11
date_created: 2018-12-11T11:54:16Z
date_published: 2015-04-01T00:00:00Z
date_updated: 2025-05-28T11:57:04Z
day: '01'
department:
- _id: ToHe
- _id: CaGu
- _id: NiBa
doi: 10.1007/978-3-662-46681-0_47
ec_funded: 1
intvolume: ' 9035'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1410.7704
month: '04'
oa: 1
oa_version: Preprint
page: 469 - 483
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '5267'
quality_controlled: '1'
related_material:
record:
- id: '1351'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Model checking gene regulatory networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9035
year: '2015'
...
---
_id: '1542'
abstract:
- lang: eng
text: 'The theory of population genetics and evolutionary computation have been
evolving separately for nearly 30 years. Many results have been independently
obtained in both fields and many others are unique to its respective field. We
aim to bridge this gap by developing a unifying framework for evolutionary processes
that allows both evolutionary algorithms and population genetics models to be
cast in the same formal framework. The framework we present here decomposes the
evolutionary process into its several components in order to facilitate the identification
of similarities between different models. In particular, we propose a classification
of evolutionary operators based on the defining properties of the different components.
We cast several commonly used operators from both fields into this common framework.
Using this, we map different evolutionary and genetic algorithms to different
evolutionary regimes and identify candidates with the most potential for the translation
of results between the fields. This provides a unified description of evolutionary
processes and represents a stepping stone towards new tools and results to both
fields. '
author:
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Golnaz
full_name: Badkobeh, Golnaz
last_name: Badkobeh
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Doğan
full_name: Çörüş, Doğan
last_name: Çörüş
- first_name: Duccuong
full_name: Dang, Duccuong
last_name: Dang
- first_name: Tobias
full_name: Friedrich, Tobias
last_name: Friedrich
- first_name: Per
full_name: Lehre, Per
last_name: Lehre
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Andrew
full_name: Sutton, Andrew
last_name: Sutton
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
citation:
ama: Paixao T, Badkobeh G, Barton NH, et al. Toward a unifying framework for evolutionary
processes. Journal of Theoretical Biology. 2015;383:28-43. doi:10.1016/j.jtbi.2015.07.011
apa: Paixao, T., Badkobeh, G., Barton, N. H., Çörüş, D., Dang, D., Friedrich, T.,
… Trubenova, B. (2015). Toward a unifying framework for evolutionary processes.
Journal of Theoretical Biology. Elsevier. https://doi.org/10.1016/j.jtbi.2015.07.011
chicago: Paixao, Tiago, Golnaz Badkobeh, Nicholas H Barton, Doğan Çörüş, Duccuong
Dang, Tobias Friedrich, Per Lehre, Dirk Sudholt, Andrew Sutton, and Barbora Trubenova.
“Toward a Unifying Framework for Evolutionary Processes.” Journal of Theoretical
Biology. Elsevier, 2015. https://doi.org/10.1016/j.jtbi.2015.07.011.
ieee: T. Paixao et al., “Toward a unifying framework for evolutionary processes,”
Journal of Theoretical Biology, vol. 383. Elsevier, pp. 28–43, 2015.
ista: Paixao T, Badkobeh G, Barton NH, Çörüş D, Dang D, Friedrich T, Lehre P, Sudholt
D, Sutton A, Trubenova B. 2015. Toward a unifying framework for evolutionary processes. Journal
of Theoretical Biology. 383, 28–43.
mla: Paixao, Tiago, et al. “Toward a Unifying Framework for Evolutionary Processes.”
Journal of Theoretical Biology, vol. 383, Elsevier, 2015, pp. 28–43, doi:10.1016/j.jtbi.2015.07.011.
short: T. Paixao, G. Badkobeh, N.H. Barton, D. Çörüş, D. Dang, T. Friedrich, P.
Lehre, D. Sudholt, A. Sutton, B. Trubenova, Journal of Theoretical Biology 383
(2015) 28–43.
date_created: 2018-12-11T11:52:37Z
date_published: 2015-10-21T00:00:00Z
date_updated: 2021-01-12T06:51:29Z
day: '21'
ddc:
- '570'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1016/j.jtbi.2015.07.011
ec_funded: 1
file:
- access_level: open_access
checksum: 33b60ecfea60764756a9ee9df5eb65ca
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:53Z
date_updated: 2020-07-14T12:45:01Z
file_id: '5244'
file_name: IST-2016-483-v1+1_1-s2.0-S0022519315003409-main.pdf
file_size: 595307
relation: main_file
file_date_updated: 2020-07-14T12:45:01Z
has_accepted_license: '1'
intvolume: ' 383'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '10'
oa: 1
oa_version: Published Version
page: 28 - 43
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
- _id: 25B07788-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '250152'
name: Limits to selection in biology and in evolutionary computation
publication: ' Journal of Theoretical Biology'
publication_status: published
publisher: Elsevier
publist_id: '5629'
pubrep_id: '483'
quality_controlled: '1'
scopus_import: 1
status: public
title: Toward a unifying framework for evolutionary processes
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 383
year: '2015'
...
---
_id: '1430'
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 their runtime 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
occurrence of new mutations is much longer than the time it takes for a new beneficial
mutation to take over the population. In this situation, the population only contains
copies of one genotype and evolution can be modelled as a (1+1)-type process where
the probability of accepting a new genotype (improvements or worsenings) depends
on the change in fitness. We present an initial runtime analysis of SSWM, quantifying
its performance for various parameters and investigating differences to the (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.
author:
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Dirk
full_name: Sudholt, Dirk
last_name: Sudholt
- first_name: Jorge
full_name: Heredia, Jorge
last_name: Heredia
- first_name: Barbora
full_name: Trubenova, Barbora
id: 42302D54-F248-11E8-B48F-1D18A9856A87
last_name: Trubenova
orcid: 0000-0002-6873-2967
citation:
ama: 'Paixao T, Sudholt D, Heredia J, Trubenova B. First steps towards a runtime
comparison of natural and artificial evolution. In: Proceedings of the 2015
Annual Conference on Genetic and Evolutionary Computation. ACM; 2015:1455-1462.
doi:10.1145/2739480.2754758'
apa: 'Paixao, T., Sudholt, D., Heredia, J., & Trubenova, B. (2015). First steps
towards a runtime comparison of natural and artificial evolution. In Proceedings
of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp.
1455–1462). Madrid, Spain: ACM. https://doi.org/10.1145/2739480.2754758'
chicago: Paixao, Tiago, Dirk Sudholt, Jorge Heredia, and Barbora Trubenova. “First
Steps towards a Runtime Comparison of Natural and Artificial Evolution.” In Proceedings
of the 2015 Annual Conference on Genetic and Evolutionary Computation, 1455–62.
ACM, 2015. https://doi.org/10.1145/2739480.2754758.
ieee: T. Paixao, D. Sudholt, J. Heredia, and B. Trubenova, “First steps towards
a runtime comparison of natural and artificial evolution,” in Proceedings of
the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid,
Spain, 2015, pp. 1455–1462.
ista: 'Paixao T, Sudholt D, Heredia J, Trubenova B. 2015. First steps towards a
runtime comparison of natural and artificial evolution. Proceedings of the 2015
Annual Conference on Genetic and Evolutionary Computation. GECCO: Genetic and
evolutionary computation conference, 1455–1462.'
mla: Paixao, Tiago, et al. “First Steps towards a Runtime Comparison of Natural
and Artificial Evolution.” Proceedings of the 2015 Annual Conference on Genetic
and Evolutionary Computation, ACM, 2015, pp. 1455–62, doi:10.1145/2739480.2754758.
short: T. Paixao, D. Sudholt, J. Heredia, B. Trubenova, in:, Proceedings of the
2015 Annual Conference on Genetic and Evolutionary Computation, ACM, 2015, pp.
1455–1462.
conference:
end_date: 2015-07-15
location: Madrid, Spain
name: 'GECCO: Genetic and evolutionary computation conference'
start_date: 2015-07-11
date_created: 2018-12-11T11:51:58Z
date_published: 2015-07-11T00:00:00Z
date_updated: 2021-01-12T06:50:41Z
day: '11'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1145/2739480.2754758
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.06260
month: '07'
oa: 1
oa_version: Preprint
page: 1455 - 1462
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '618091'
name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary
Computation
publication_status: published
publisher: ACM
publist_id: '5768'
quality_controlled: '1'
scopus_import: 1
status: public
title: First steps towards a runtime comparison of natural and artificial evolution
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '9712'
article_processing_charge: No
author:
- first_name: Murat
full_name: Tugrul, Murat
id: 37C323C6-F248-11E8-B48F-1D18A9856A87
last_name: Tugrul
orcid: 0000-0002-8523-0758
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Gašper
full_name: Tkačik, Gašper
id: 3D494DCA-F248-11E8-B48F-1D18A9856A87
last_name: Tkačik
orcid: 0000-0002-6699-1455
citation:
ama: Tugrul M, Paixao T, Barton NH, Tkačik G. Other fitness models for comparison
& for interacting TFBSs. 2015. doi:10.1371/journal.pgen.1005639.s001
apa: Tugrul, M., Paixao, T., Barton, N. H., & Tkačik, G. (2015). Other fitness
models for comparison & for interacting TFBSs. Public Library of Science.
https://doi.org/10.1371/journal.pgen.1005639.s001
chicago: Tugrul, Murat, Tiago Paixao, Nicholas H Barton, and Gašper Tkačik. “Other
Fitness Models for Comparison & for Interacting TFBSs.” Public Library of
Science, 2015. https://doi.org/10.1371/journal.pgen.1005639.s001.
ieee: M. Tugrul, T. Paixao, N. H. Barton, and G. Tkačik, “Other fitness models for
comparison & for interacting TFBSs.” Public Library of Science, 2015.
ista: Tugrul M, Paixao T, Barton NH, Tkačik G. 2015. Other fitness models for comparison
& for interacting TFBSs, Public Library of Science, 10.1371/journal.pgen.1005639.s001.
mla: Tugrul, Murat, et al. Other Fitness Models for Comparison & for Interacting
TFBSs. Public Library of Science, 2015, doi:10.1371/journal.pgen.1005639.s001.
short: M. Tugrul, T. Paixao, N.H. Barton, G. Tkačik, (2015).
date_created: 2021-07-23T12:00:37Z
date_published: 2015-11-06T00:00:00Z
date_updated: 2025-05-28T11:57:04Z
day: '06'
department:
- _id: NiBa
- _id: CaGu
- _id: GaTk
doi: 10.1371/journal.pgen.1005639.s001
month: '11'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '1666'
relation: used_in_publication
status: public
status: public
title: Other fitness models for comparison & for interacting TFBSs
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2015'
...
---
_id: '2169'
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Sebastian
full_name: Novak, Sebastian
id: 461468AE-F248-11E8-B48F-1D18A9856A87
last_name: Novak
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
citation:
ama: Barton NH, Novak S, Paixao T. Diverse forms of selection in evolution and computer
science. PNAS. 2014;111(29):10398-10399. doi:10.1073/pnas.1410107111
apa: Barton, N. H., Novak, S., & Paixao, T. (2014). Diverse forms of selection
in evolution and computer science. PNAS. National Academy of Sciences.
https://doi.org/10.1073/pnas.1410107111
chicago: Barton, Nicholas H, Sebastian Novak, and Tiago Paixao. “Diverse Forms of
Selection in Evolution and Computer Science.” PNAS. National Academy of
Sciences, 2014. https://doi.org/10.1073/pnas.1410107111.
ieee: N. H. Barton, S. Novak, and T. Paixao, “Diverse forms of selection in evolution
and computer science,” PNAS, vol. 111, no. 29. National Academy of Sciences,
pp. 10398–10399, 2014.
ista: Barton NH, Novak S, Paixao T. 2014. Diverse forms of selection in evolution
and computer science. PNAS. 111(29), 10398–10399.
mla: Barton, Nicholas H., et al. “Diverse Forms of Selection in Evolution and Computer
Science.” PNAS, vol. 111, no. 29, National Academy of Sciences, 2014, pp.
10398–99, doi:10.1073/pnas.1410107111.
short: N.H. Barton, S. Novak, T. Paixao, PNAS 111 (2014) 10398–10399.
date_created: 2018-12-11T11:56:07Z
date_published: 2014-07-22T00:00:00Z
date_updated: 2021-01-12T06:55:45Z
day: '22'
department:
- _id: NiBa
doi: 10.1073/pnas.1410107111
intvolume: ' 111'
issue: '29'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4115508/
month: '07'
oa: 1
oa_version: Submitted Version
page: 10398 - 10399
publication: PNAS
publication_status: published
publisher: National Academy of Sciences
publist_id: '4815'
quality_controlled: '1'
scopus_import: 1
status: public
title: Diverse forms of selection in evolution and computer science
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 111
year: '2014'
...
---
_id: '2252'
abstract:
- lang: eng
text: The pattern of inheritance and mechanism of sex determination can have important
evolutionary consequences. We studied probabilistic sex determination in the ciliate
Tetrahymena thermophila, which was previously shown to cause evolution of skewed
sex ratios. We find that the genetic background alters the sex determination patterns
of mat alleles in heterozygotes and that allelic interaction can differentially
influence the expression probability of the 7 sexes. We quantify the dominance
relationships between several mat alleles and find that A-type alleles, which
specify sex I, are indeed recessive to B-type alleles, which are unable to specify
that sex. Our results provide additional support for the presence of modifier
loci and raise implications for the dynamics of sex ratios in populations of T.
thermophila.
article_processing_charge: No
author:
- first_name: Sujal
full_name: Phadke, Sujal
last_name: Phadke
- first_name: Tiago
full_name: Paixao, Tiago
id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
last_name: Paixao
orcid: 0000-0003-2361-3953
- first_name: Tuan
full_name: Pham, Tuan
last_name: Pham
- first_name: Stephanie
full_name: Pham, Stephanie
last_name: Pham
- first_name: Rebecca
full_name: Zufall, Rebecca
last_name: Zufall
citation:
ama: Phadke S, Paixao T, Pham T, Pham S, Zufall R. Genetic background alters dominance
relationships between mat alleles in the ciliate Tetrahymena Thermophila. Journal
of Heredity. 2014;105(1):130-135. doi:10.1093/jhered/est063
apa: Phadke, S., Paixao, T., Pham, T., Pham, S., & Zufall, R. (2014). Genetic
background alters dominance relationships between mat alleles in the ciliate Tetrahymena
Thermophila. Journal of Heredity. Oxford University Press. https://doi.org/10.1093/jhered/est063
chicago: Phadke, Sujal, Tiago Paixao, Tuan Pham, Stephanie Pham, and Rebecca Zufall.
“Genetic Background Alters Dominance Relationships between Mat Alleles in the
Ciliate Tetrahymena Thermophila.” Journal of Heredity. Oxford University
Press, 2014. https://doi.org/10.1093/jhered/est063.
ieee: S. Phadke, T. Paixao, T. Pham, S. Pham, and R. Zufall, “Genetic background
alters dominance relationships between mat alleles in the ciliate Tetrahymena
Thermophila,” Journal of Heredity, vol. 105, no. 1. Oxford University Press,
pp. 130–135, 2014.
ista: Phadke S, Paixao T, Pham T, Pham S, Zufall R. 2014. Genetic background alters
dominance relationships between mat alleles in the ciliate Tetrahymena Thermophila.
Journal of Heredity. 105(1), 130–135.
mla: Phadke, Sujal, et al. “Genetic Background Alters Dominance Relationships between
Mat Alleles in the Ciliate Tetrahymena Thermophila.” Journal of Heredity,
vol. 105, no. 1, Oxford University Press, 2014, pp. 130–35, doi:10.1093/jhered/est063.
short: S. Phadke, T. Paixao, T. Pham, S. Pham, R. Zufall, Journal of Heredity 105
(2014) 130–135.
date_created: 2018-12-11T11:56:35Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2022-08-25T14:45:42Z
day: '01'
department:
- _id: NiBa
doi: 10.1093/jhered/est063
intvolume: ' 105'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 130 - 135
publication: Journal of Heredity
publication_identifier:
issn:
- '00221503'
publication_status: published
publisher: Oxford University Press
publist_id: '4695'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Genetic background alters dominance relationships between mat alleles in the
ciliate Tetrahymena Thermophila
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 105
year: '2014'
...