In the problem of HLA typing, knowing the correct allele is essential for donor-recipient compatibility. I’ll present a graph model on the set of potential probes, formulate the HLA typing problem mathematically as an optimization problem, namely, a maximal weighted independent set problem, on this graph model, and describe an algorithm for solving the optimization problem. The processes of translating the typing problem to the graph model and the optimizing probe set back to the experiment design will be described in detail.
One important parameter in the optimization problem, the minimum desired size M of the independent set, can be chosen to give arbitrarily high probabilities $1 - \epsilon$ of being able to distinguish among all known alleles. I’ll discuss the corresponding error bounds for the cases of both similar and dissimilar probe response vectors, and for larger minimum Hamming distances, allowing for error correction.