Core Hunter II: fast core subset selection based on multiple genetic diversity measures using Mixed Replica search

BMC Bioinformatics

Herman De Beukelaer²  Petr Smýkal³  Guy F Davenport¹  Veerle Fack² 

[1] , Bayer CropScience NV, Seeds, Technologiepark 38, 9052 Zwijnaarde, Belgium

[2] Department of Applied Mathematics and Computer Science, Faculty of Sciences, Ghent University, Krijgslaan 281, S9, 9000 Gent, Belgium

[3] Department of Botany, Faculty of Sciences, Palacký University, Slechtitelu 11783 71 Olomouc, Czech Republic

关键词: Multi-objective optimization;    Local heuristics;    Germplasm;    Allelic diversity;    Genetic distance;    Core subset selection;    Core collections;   

Others  :  1088058
DOI  :  10.1186/1471-2105-13-312

 received in 2012-03-22, accepted in 2012-11-01,  发布年份 2012

【 摘 要 】

Background

Sampling core subsets from genetic resources while maintaining as much as possible the genetic diversity of the original collection is an important but computationally complex task for gene bank managers. The Core Hunter computer program was developed as a tool to generate such subsets based on multiple genetic measures, including both distance measures and allelic diversity indices. At first we investigate the effect of minimum (instead of the default mean) distance measures on the performance of Core Hunter. Secondly, we try to gain more insight into the performance of the original Core Hunter search algorithm through comparison with several other heuristics working with several realistic datasets of varying size and allelic composition. Finally, we propose a new algorithm (Mixed Replica search) for Core Hunter II with the aim of improving the diversity of the constructed core sets and their corresponding generation times.

Results

Our results show that the introduction of minimum distance measures leads to core sets in which all accessions are sufficiently distant from each other, which was not always obtained when optimizing mean distance alone. Comparison of the original Core Hunter algorithm, Replica Exchange Monte Carlo (REMC), with simpler heuristics shows that the simpler algorithms often give very good results but with lower runtimes than REMC. However, the performance of the simpler algorithms is slightly worse than REMC under lower sampling intensities and some heuristics clearly struggle with minimum distance measures. In comparison the new advanced Mixed Replica search algorithm (MixRep), which uses heterogeneous replicas, was able to sample core sets with equal or higher diversity scores than REMC and the simpler heuristics, often using less computation time than REMC.

Conclusion

The REMC search algorithm used in the original Core Hunter computer program performs well, sometimes leading to slightly better results than some of the simpler methods, although it doesn’t always give the best results. By switching to the new Mixed Replica algorithm overall results and runtimes can be significantly improved. Finally we recommend including minimum distance measures in the objective function when looking for core sets in which all accessions are sufficiently distant from each other. Core Hunter II is freely available as an open source project at http://www.corehunter.org webcite.

【 授权许可】

   
2012 De Beukelaer et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

【 参考文献 】

• [1]Frankel OH: Genetic perspectives of germplasm conservation. In Genetic manipulation: impact on man and society. Edited by Arber W, Illmensee K, Peacock WJ, Starlinger P. Cambridge: Cambridge University Press; 1984:161-170.
• [2]Wright S: Evolution and the Genetics of Populations: A treatise in four volumes, Volume IV. 1427 East 60th Street Chicago, IL 60637 USA: University of Chicago Press; 1978.
• [3]Cavalli-Sforza L, Edwards A: Phylogenetic analysis. Models and estimation procedures. Am J Human Genet 1967, 19:233-257.
• [4]Shannon CE: A mathematical theory of communication. Bell Syst Tech J 1948, 27:379-423.
• [5]Berg EE, Hamrick JL: Quantification of genetic diversity at allozyme loci. Can J Forest Res 1997, 27:415-424.
• [6]Franco J, Crossa J, Warburton ML, Taba S: Sampling strategies for conserving Maize diversity when forming core subsets using genetic markers. Crop Sci 2006, 46:854-864.
• [7]Kim KW, Chung HK, Cho GT, Ma KH, Chandrabalan D, Gwag JG, Kim TS, Cho EG, Park YJ: PowerCore: a program applying the advanced M strategy with a heuristic search for establishing core sets. Bioinformatics 2007, 23:2155-2162.
• [8]Wang JC, Hu J, Liu NN, Xu HM, Zhang S: Investigation of combining plant genotypic values and molecular marker information for constructing core subsets. J Integr Plant Biol 2006, 48(11):1371-1378.
• [9]Franco J, Crossa J, Desphande S: Hierarchical multiple-factor analysis for classifying genotypes based on phenotypic and genetic data. Crop Science 2010, 50:105-117.
• [10]Sokal R, Michener C, of Kansas U: A statistical method for evaluating systematic relationships. 2502 Westbrooke Circle Lawrence KS 66045–4444: University of Kansas science bulletin, University of Kansas; 1958.
• [11]Franco J, Crossa J, Taba S, Shands H: A multivariate method for classifying cultivars and studying group x environment x trait interaction. Crop Sci 2003, 43:1249-1258.
• [12]Franco J, Crossa J: The modified location model for classifying genetic resources. I. Association between categorial and continuous variables. Crop Sci 2002, 42:1719-1726.
• [13]Franco J, Crossa J, Taba S, Eberhart SA: The modified location model for classifying genetic resources. II Unrestrictive variance-covariance matrices. Crop Sci 2002, 42:1727-1736.
• [14]Franco J, Crossa J, Villaseñor J, Taba S, Eberhart SA: A two-stage, three-way method for classifying genetic resources in multiple environments. Crop Sci 1999, 39:259-267.
• [15]Franco J, Crossa J, Villaseñor J, Taba S, Eberhart SA: Classifying genetic resources by categorical and continuous variables. Crop Sci 1998, 38(6):1688-1696.
• [16]Brown AHD: Core collections: a practical approach to genetic resources management. Genome 1989, 31:818-824.
• [17]Franco J, Crossa J, Taba S, Shands H: A sampling strategy for conserving genetic diversity when forming core subsets. Crop Sci 2005, 45:1035-1044.
• [18]Schoen DJ, Brown AH: Conservation of allelic richness in wild crop relatives is aided by assessment of genetic markers. Proc Nat Acad Sci 1993, 90:10623-10627.
• [19]Gouesnard B, Bataillon TM, Decoux G, Rozale C, Schoen DJ, David JL: MSTRAT: An algorithm for building germ plasm core collections by maximizing allelic or phenotypic richness. J Heredity 2001, 92:93-94.
• [20]Jansen J, van Hintum T: Genetic distance sampling: a novel sampling method for obtaining core collections using genetic distances with an application to cultivated lettuce. TAG Theor Appl Genet 2007, 114:421-428.
• [21]Wang J, Hu J, Xu H, Zhang S: A strategy on constructing core collections by least distance stepwise sampling. TAG Theor Appl Genet 2007, 115:1-8.
• [22]Thachuk C, Crossa J, Franco J, Dreisigacker S, Warburton M, Davenport G: Core Hunter: an algorithm for sampling genetic resources based on multiple genetic measures. BMC Bioinf 2009, 10:243. BioMed Central Full Text
• [23]Kirkpatrick S, Gelatt CD, Vecchi MP: Optimization by simulated annealing. Science 1983, 220:671-680.
• [24]Reif JC, Melchinger AE, Frisch M: Genetical and mathematical properties of similarity and dissimilarity coefficients applied in plant breeding and seed bank management. Crop Sci 2005, 45:1-7.
• [25]Ferri FJ, Pudil P, Hatef M, Kittler J: Comparative study of techniques for large-scale feature selection. In Pattern Recognition in Practice, IV: Multiple Paradigms, Comparative Studies and Hybrid Systems. Edited by Gelsema ES, Kanal LN. Amsterdam; 1994:403-413.
• [26]Mitchell M: An Introduction to Genetic Algorithms (Complex Adaptive Systems). A Bradford Book, third printing edition. 55 Hayward Street Cambridge, MA 02142-1493 USA: The MIT Press; 1998.
• [27]Dubreuil P, Warburton M, Chastanet M, Hoisington D, Charcosset A: More on the introduction of temperate maize into Europe: large-scale bulk SSR genotyping and new historical elements. Maydica 2006, 51:281-291.
• [28]Warburton M, Crossa J, Diaz L, Gomez A, Taba S: Diversidad genética en criollos de mais medida por microsatélites. In Congreso Nacional de Biotecnología Agropecuaria y Forestal. Chapingo, México; 2004.
• [29]Smýkal P, Bačová-Kerteszová N, Kalendar R, Corander J, Schulman AH, Pavelek M: Genetic diversity of cultivated flax (Linum usitatissimum L.) germplasm assessed by retrotransposon-based markers. Theor Appl Genet 2011, 122:1385-1397.
• [30]Smýkal P, Hýbl M, Corander J, Jarkovský J, Flavell A, Griga M: Genetic diversity and population structure of pea (Pisum sativum L.) varieties derived from combined retrotransposon, microsatellite and morphological marker analysis. Theor Appl Genet 2008, 117:413-424.
• [31]Jing R, Vershinin A, Grzebyta J, Shaw P, Smýkal P, Marshall D, Ambrose MJ, Ellis THN, Flavell AJ: The genetic diversity and evolution of field pea (Pisum) studied by high throughput retrotransposon based insertion polymorphism (RBIP) marker analysis. BMC Evolutionary Biol 2010, 10:44. BioMed Central Full Text
• [32]Smýkal P, Kenicer G, Flavell AJ, Corander J, Kosterin O, Redden RJ, Ford R, Coyne CJ, Maxted N, Ambrose MJ, Ellis THN: Phylogeny, phylogeography and genetic diversity of the Pisum genus. Plant Genet Res 2011, 9:4-18.