Genotyping of pooled microsatellite markers by combinatorial optimization techniques

An important everyday task for geneticists and molecular biologists is that of isolating and analyzing some particular DNA regions (markers), each drawn from a limited and known set of possible values (alleles). This procedure is called genotyping and is based on DNA amplification and size separation. In order to increase the throughput of genotyping, recently a new experiment has been proposed which tries to analyze many different markers of similar size at once. We study the mathematical problem corresponding to this model and give a branch-and-bound algorithm for its solution. We show that by using the techniques described in this paper, genotyping of pooled markers can be computed effectively, thus potentially achieving a considerable reduction in time and expense. 1998 Published by Elsevier Science B.V. All rights reserved.