Chunk #8 — ONLINE METHODS — Computational complexity and optimal allocation

Source

Next-generation genotype imputation service and methods.

Embedded

yes

Text

We implement a recursive dynamic programming algorithm to find the optimal allocation of the genomic segments, as a brute force approach is not feasible (~2M–1 alternatives). We assume that the optimal complexity of imputation until marker i < M is denoted by C(i) and calculate C(M) recursively as (5)C(M)=mini=1,2,…,M−1{C(i)+U(i,M)×(M−i+1)+2H}