Advanced search
1 file | 10.92 MB

Heuristic exploitation of genetic structure in marker-assisted gene pyramiding problems

Author
Organization
Project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
Abstract
Background: Over the last decade genetic marker-based plant breeding strategies have gained increasing attention because genotyping technologies are no longer limiting. Now the challenge is to optimally use genetic markers in practical breeding schemes. For simple traits such as some disease resistances it is possible to target a fixed multi-locus allele configuration at a small number of causal or linked loci. Efficiently obtaining this genetic ideotype from a given set of parental genotypes is known as the marker-assisted gene pyramiding problem. Previous methods either imposed strong restrictions or used black box integer programming solutions, while this paper explores the power of an explicit heuristic approach that exploits the underlying genetic structure to prune the search space. Results: Gene Stacker is introduced as a novel approach to marker-assisted gene pyramiding, combining an explicit directed acyclic graph model with a pruned generation algorithm inspired by a simple exhaustive search. Both exact and heuristic pruning criteria are applied to reduce the number of generated schedules. It is shown that this approach can effectively be used to obtain good solutions for stacking problems of varying complexity. For more complex problems, the heuristics allow to obtain valuable approximations. For smaller problems, fewer heuristics can be applied, resulting in an interesting quality-runtime tradeoff. Gene Stacker is competitive with previous methods and often finds better and/or additional solutions within reasonable time, because of the powerful heuristics. Conclusions: The proposed approach was confirmed to be feasible in combination with heuristics to cope with realistic, complex stacking problems. The inherent flexibility of this approach allows to easily address important breeding constraints so that the obtained schedules can be widely used in practice without major modifications. In addition, the ideas applied for Gene Stacker can be incorporated in and extended for a plant breeding context that e.g. also addresses complex quantitative traits or conservation of genetic background. Gene Stacker is freely available as open source software at http://genestacker.ugent.be. The website also provides documentation and examples of how to use Gene Stacker.
Keywords
Multi-objective optimization, Heuristics, Plant breeding, Marker-assisted gene pyramiding, OPTIMIZATION, PLANT

Downloads

  • GeneStacker.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 10.92 MB

Citation

Please use this url to cite or link to this publication:

Chicago
De Beukelaer, Herman, Geert De Meyer, and Veerle Fack. 2015. “Heuristic Exploitation of Genetic Structure in Marker-assisted Gene Pyramiding Problems.” Bmc Genetics 16.
APA
De Beukelaer, H., De Meyer, G., & Fack, V. (2015). Heuristic exploitation of genetic structure in marker-assisted gene pyramiding problems. BMC GENETICS, 16.
Vancouver
1.
De Beukelaer H, De Meyer G, Fack V. Heuristic exploitation of genetic structure in marker-assisted gene pyramiding problems. BMC GENETICS. 2015;16.
MLA
De Beukelaer, Herman, Geert De Meyer, and Veerle Fack. “Heuristic Exploitation of Genetic Structure in Marker-assisted Gene Pyramiding Problems.” BMC GENETICS 16 (2015): n. pag. Print.
@article{5862059,
  abstract     = {Background: Over the last decade genetic marker-based plant breeding strategies have gained increasing attention because genotyping technologies are no longer limiting. Now the challenge is to optimally use genetic markers in practical breeding schemes. For simple traits such as some disease resistances it is possible to target a fixed multi-locus allele configuration at a small number of causal or linked loci. Efficiently obtaining this genetic ideotype from a given set of parental genotypes is known as the marker-assisted gene pyramiding problem. Previous methods either imposed strong restrictions or used black box integer programming solutions, while this paper explores the power of an explicit heuristic approach that exploits the underlying genetic structure to prune the search space. 
Results: Gene Stacker is introduced as a novel approach to marker-assisted gene pyramiding, combining an explicit directed acyclic graph model with a pruned generation algorithm inspired by a simple exhaustive search. Both exact and heuristic pruning criteria are applied to reduce the number of generated schedules. It is shown that this approach can effectively be used to obtain good solutions for stacking problems of varying complexity. For more complex problems, the heuristics allow to obtain valuable approximations. For smaller problems, fewer heuristics can be applied, resulting in an interesting quality-runtime tradeoff. Gene Stacker is competitive with previous methods and often finds better and/or additional solutions within reasonable time, because of the powerful heuristics. 
Conclusions: The proposed approach was confirmed to be feasible in combination with heuristics to cope with realistic, complex stacking problems. The inherent flexibility of this approach allows to easily address important breeding constraints so that the obtained schedules can be widely used in practice without major modifications. In addition, the ideas applied for Gene Stacker can be incorporated in and extended for a plant breeding context that e.g. also addresses complex quantitative traits or conservation of genetic background. Gene Stacker is freely available as open source software at http://genestacker.ugent.be. The website also provides documentation and examples of how to use Gene Stacker.},
  articleno    = {2},
  author       = {De Beukelaer, Herman and De Meyer, Geert and Fack, Veerle},
  issn         = {1471-2156},
  journal      = {BMC GENETICS},
  language     = {eng},
  pages        = {16},
  title        = {Heuristic exploitation of genetic structure in marker-assisted gene pyramiding problems},
  url          = {http://dx.doi.org/10.1186/s12863-014-0154-z},
  volume       = {16},
  year         = {2015},
}

Altmetric
View in Altmetric
Web of Science
Times cited: