Multi-objective optimization approach with decomposition-based algorithm for selecting tagSNPs

• Multi-objective algorithm based on decomposition for the tagSNP selection problem • Implementation of five new problem-aware operators to explore the search space • Comparative study of the proposed method with six different alternative approaches • Experimentation with five highly relevant datasets from 1000 Genomes Project (1KGP) • Competitive approach in terms of runtime and results quality after the comparisons Nowadays multiple bioinformatics issues can be solved by using evolutionary computation due to its potential to address complex optimization problems. TagSNP selection lies within this class of challenging problems, since genotyping all the Single Nucleotide Polymorphisms (SNPs) for haplotype identification is economically costly and time-consuming. If a reduced number of tagSNPs is chosen instead, the classification of haplotypes will accordingly show a worsening. As a result, tagSNP selection can be considered as a multi-objective optimization problem, in which the aim is to optimize haplotype dissimilarity while minimizing the number of selected tagSNPs. We propose and detail an approach based on the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) for accurately selecting tagSNPs attending to these two objectives. The proposed method includes novel problem-aware operators for the initialization, crossover, and mutation to boost optimization capabilities. The proposal is experimentally compared with six approaches from the literature on five real datasets, using in the evaluation three quality metrics and their corresponding statistical analyses. The attained results denote that our algorithm provides statistically-significant improvements over previous methods with competitive runtimes, thus highlighting the relevance of the proposed multi-objective approach.