Constructing Linkage Disequilibrium Map with Iterative Approach

摘要

With recent advance of the genotyping single nucleotide polymorphisms (SNPs) in mass scale of high density in a candidate region of the human genome, the linkage disequilibrium analysis can offer a much higher resolution of the biological samples than the traditional linkage maps. We have formulated this LD mapping problem as a constrained unidimensional scaling problem. Our method, which is directly based on the measurement of LD among SNPs, is non-parametric. Therefore it is different from LD maps derived from the given Malecot model. We have formulated with the quadratic programming approach for solving this constrained unidimensional scaling problem. Different from the classical metric unidimensional scaling problem, the constrained problem is not an NP-hard combinatorial problem. The optimal solution is determined by using the quadratic programming solver. Nevertheless, because of the large requirement for memory during the running time that may cause the out of memory problems, and the high computational time of the quadratic programming algorithm, the iterative algorithm has been developed for solving this LD constrained unidimensional scaling problem.