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 automated 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 algorithms, we found that, on these data, GMS performed better than MultiMap, placing more markers in their true order on average, with little order ambiguity. In addition, as the number of markers increased, GMS was less computationally demanding than MultiMap. However, it MultiMap placed a marker, it was 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 when the evidence for placement on one end or the other is not strong. Thus, there is room for further algorithmic developments that combine the strengths of both the MultiMap and GMS approaches.