title: Multi-marker tagging single nucleotide polymorphism selection using estimation of distribution algorithms.
abstract: OBJECTIVE
  This paper presents an optimization algorithm for the automatic selection of a minimal subset of tagging single nucleotide polymorphisms (SNPs).
  
  
  METHODS
  The determination of the set of minimal tagging SNPs is approached as an optimization problem in which each tagged SNP can be covered by a single tagging SNP or by a pair of tagging SNPs. The problem is solved using an estimation of distribution algorithm (EDA) which takes advantage of the underlying topological structure defined by the SNP correlations to model the problem interactions. The EDA stochastically searches the constrained space of feasible solutions. It is evaluated across HapMap reference panel data sets.
  
  
  RESULTS
  The EDA was compared with a SAT solver, able to find the single-marker minimal tagging sets, and with the Tagger program. The percentage of reduction ranged from 10% to 43% in the number of tagging SNPs of the minimal multi-marker tagging set found by the EDA with respect to the other algorithms.
  
  
  CONCLUSIONS
  The introduced algorithm is effective for the identification of minimal multi-marker SNP sets, which considerably reduce the dimension of the tagging SNP set in comparison with single-marker sets. Other variants of the SNP problem can be treated following the same approach.
authors.affiliation: Faculty of Informatics, Universidad Politécnica de Madrid, R. 3306, Campus de Montegancedo, 28660 Boadilla del Monte, Madrid, Spain. roberto.santana@upm.es
authors.forename: Roberto
authors.initials: R
authors.lastname: Santana
authors.forename: Alexander
authors.initials: A
authors.lastname: Mendiburu
authors.forename: Noah
authors.initials: N
authors.lastname: Zaitlen
authors.forename: Eleazar
authors.initials: E
authors.lastname: Eskin
authors.forename: Jose A
authors.initials: JA
authors.lastname: Lozano
mesh_terms: D000465:Algorithms; D020641:Polymorphism, Single Nucleotide; D013269:Stochastic Processes