The human genome has many polymorphic sites, which make up the difference between individuals. A haplotype is a vector describing the specific variant in each polymorphic position. Unfortunately, haplotypes are not measured directly, but rather need to be inferred from indirect measurements. We tackle the task of computationally resolving these vectors from frequency measurements of their different coordinates.
Biologically, this task is driven by a current global effort to map all human genetic variants, while our strategy potentially offers a 10-20-fold saving in biological reactions performed toward this task. measured directly, but rather need to be inferred from indirect measurements. We tackle the task of computationally resolving these vectors from frequency measurements of their different coordinates.
Biologically, this task is driven by a current global effort to map all human genetic variants, while our strategy potentially offers a 10-20-fold saving in biological reactions performed toward this task.
We study in depth two typical scenarios of haplotype mapping: (i) Reconstructing the most common haplotypes for a set of several ethnically distinct populations; (ii) Reconstructing all haplotypes from small pools drawn from a single population. Computationally, our method for the former case is an adaptation of the k-means clustering algorithm, while the solution for the latter case builds on the technique of lattice reduction in algebraic number theory.
All the required biological background will be provided.
