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

• Published in: BMC bioinformatics 2012-11, Vol.13 (1), p.312-312, Article 312
• Main Authors: De Beukelaer, Herman, Smýkal, Petr, Davenport, Guy F, Fack, Veerle
• Format: Article
• Language: English
• Subjects: Algorithms; Alleles; Allelic diversity; Analysis; Bioinformatics; Biological diversity; Computer programs; Core collections; Core subset selection; Genetic distance; Genetic diversity; Genetic resources; Genetic Variation; Germplasm; Heuristic; Local heuristics; Monte Carlo Method; Multi-objective optimization; Problem solving; Sampling; Sequence Analysis, DNA - methods; Sequence Analysis, DNA - statistics & numerical data; Software; Studies
• ISSN: 1471-2105; 1471-2105
• DOI: 10.1186/1471-2105-13-312

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. 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. 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.