title: Heuristic exploitation of genetic structure in marker-assisted gene pyramiding problems.
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.
authors: Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 - S9, Gent, 9000, Belgium. Herman.DeBeukelaer@UGent.be.
authors: Herman
authors: H
authors: De Beukelaer
authors: Bayer CropScience NV, Innovation Center, Technologiepark 38, Zwijnaarde, 9052, Belgium. geert.demeyer@bayer.com.
authors: Geert
authors: G
authors: De Meyer
authors: Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281 - S9, Gent, 9000, Belgium. Veerle.Fack@UGent.be.
authors: Veerle
authors: V
authors: Fack
mesh_terms: D000465:Algorithms; D001947:Breeding; D018556:Crops, Agricultural / Q000145:classification / Q000235:genetics; D005819:Genetic Markers; D010944:Plants / Q000145:classification / Q000235:genetics*; D012984:Software
chemical_list: D005819:Genetic Markers
references: Genetics. 2004 Sep;168(1):513-23
references: 15454561
references: Plant Physiol. 2008 Jul;147(3):969-77
references: 18612074
references: Genetics. 2013 Feb;193(2):327-45
references: 22745228
references: Nat Rev Genet. 2011 Oct;12(10):703-14
references: 21921926
references: Science. 2010 Feb 12;327(5967):818-22
references: 20150489