A comparison of two algorithms, MultiMap and gene mapping system, for automated construction of genetic linkage maps

Using the GAW11 Problem 2 data set, we compared the performance of two auto mated map construction algorithms, MultiMap and GMS (Gene Mapping System). The MultiMap algorithm iteratively adds markers in a stepwise manner to the map, while the GMS algorithm seeks to find the best order of the whole set of markers by selective permutations of logically formed subgroups of the markers. While it is difficult to compare these two rather different algori thms, we found that, on these data, GMS performed better than MultiMap, pla cing more markers in their true order on average, with little order ambigui ty. In addition, as the number of markers increased, GMS was less computati onally demanding than MultiMap. However, if MultiMap placed a marker, it wa s almost always in the correct order. In contrast, GMS often placed a group of markers on the wrong end of the map; such incorrect placements occur wh en the evidence for placement on one end or the other is not strong. Thus, there is room for further algorithmic developments that combine the strengt hs of both the MultiMap and GMS approaches. ((C)) 1999 Wiley-Liss, Inc.