Advanced

Homology and linkage in crossover for linear genomes of variable length

Merlevede, Adriaan LU ; Åhl, Henrik and Troein, Carl LU (2019) In PLoS ONE 14(1).
Abstract

The use of variable-length genomes in evolutionary computation has applications in optimisation when the size of the search space is unknown, and provides a unique environment to study the evolutionary dynamics of genome structure. Here, we revisit crossover for linear genomes of variable length, identifying two crucial attributes of successful recombination algorithms: the ability to retain homologous structure, and to reshuffle variant information. We introduce direct measures of these properties—homology score and linkage score—and use them to review existing crossover algorithms, as well as two novel ones. In addition, we measure the performance of these crossover methods on three different benchmark problems, and find that... (More)

The use of variable-length genomes in evolutionary computation has applications in optimisation when the size of the search space is unknown, and provides a unique environment to study the evolutionary dynamics of genome structure. Here, we revisit crossover for linear genomes of variable length, identifying two crucial attributes of successful recombination algorithms: the ability to retain homologous structure, and to reshuffle variant information. We introduce direct measures of these properties—homology score and linkage score—and use them to review existing crossover algorithms, as well as two novel ones. In addition, we measure the performance of these crossover methods on three different benchmark problems, and find that variable-length genomes out-perform fixed-length variants in all three cases. Our homology and linkage scores successfully explain the difference in performance between different crossover methods, providing a simple and insightful framework for crossover in a variable-length setting.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
PLoS ONE
volume
14
issue
1
publisher
Public Library of Science
external identifiers
  • scopus:85059471099
ISSN
1932-6203
DOI
10.1371/journal.pone.0209712
language
English
LU publication?
yes
id
57ccf594-58a9-46f0-ad6c-6327e2f3fa9b
date added to LUP
2019-01-11 09:28:15
date last changed
2019-04-13 03:00:20
@article{57ccf594-58a9-46f0-ad6c-6327e2f3fa9b,
  abstract     = {<p>The use of variable-length genomes in evolutionary computation has applications in optimisation when the size of the search space is unknown, and provides a unique environment to study the evolutionary dynamics of genome structure. Here, we revisit crossover for linear genomes of variable length, identifying two crucial attributes of successful recombination algorithms: the ability to retain homologous structure, and to reshuffle variant information. We introduce direct measures of these properties—homology score and linkage score—and use them to review existing crossover algorithms, as well as two novel ones. In addition, we measure the performance of these crossover methods on three different benchmark problems, and find that variable-length genomes out-perform fixed-length variants in all three cases. Our homology and linkage scores successfully explain the difference in performance between different crossover methods, providing a simple and insightful framework for crossover in a variable-length setting.</p>},
  articleno    = {e0209712},
  author       = {Merlevede, Adriaan and Åhl, Henrik and Troein, Carl},
  issn         = {1932-6203},
  language     = {eng},
  number       = {1},
  publisher    = {Public Library of Science},
  series       = {PLoS ONE},
  title        = {Homology and linkage in crossover for linear genomes of variable length},
  url          = {http://dx.doi.org/10.1371/journal.pone.0209712},
  volume       = {14},
  year         = {2019},
}