CHOISS for selection of single nucleotide polymorphism markers on interval regularity

Abstract

Summary: We developed algorithms that find a set of single nucleotide polymorphism (SNP) markers based on interval regularity, given either the number of SNPs to choose (m) or the desired interval (I), subject to minimum variance or minimum sum of squared deviations from I. In both cases, the number of all possible sets increases exponentially with respect to the number of input SNPs (n), but our algorithms find the minima only with O(n(2)) calculations and comparisons by elimination of redundancy.