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 dra wn from a limited and known set of possible values (alleles). This procedur e is called genotyping and is based on DNA amplification and size separatio n. In order to increase the throughput of genotyping, recently a new experi ment has been proposed which tries to analyze many different markers of sim ilar 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 marke rs can be computed effectively, thus potentially achieving a considerable r eduction in time and expense. 1998 Published by Elsevier Science B.V. All r ights reserved.