Endelman BMC Genomics 2011, 12:407 http://www.biomedcentral.com/1471-2164/12/407 M E T H O D O L O G Y A R T I C L E Open Access New algorithm improves fine structure of the barley consensus SNP map Jeffrey B Endelman Abstract Background: The need to integrate information from multiple linkage maps is a long-standing problem in genetics. One way to visualize the complex ordinal relationships is with a directed graph, where each vertex in the graph is a bin of markers. When there are no ordering conflicts between the linkage maps, the result is a directed acyclic graph, or DAG, which can then be linearized to produce a consensus map. Results: New algorithms for the simplification and linearization of consensus graphs have been implemented as a package for the R computing environment called DAGGER. The simplified consensus graphs produced by DAGGER exactly capture the ordinal relationships present in a series of linkage maps. Using either linear or quadratic programming, DAGGER generates a consensus map with minimum error relative to the linkage maps while remaining ordinally consistent with them. Both linearization methods produce consensus maps that are compressed relative to the mean of the linkage maps. After rescaling, however, the consensus maps had higher accuracy (and higher marker density) than the individual linkage maps in genetic simulations. When applied to four barley linkage maps genotyped at nearly 3000 SNP markers, DAGGER produced a consensus map with improved fine structure compared to the existing barley consensus SNP map. The root-mean-squared error between the linkage maps and the DAGGER map was 0.82 cM per marker interval compared to 2.28 cM for the existing consensus map. Examination of the barley hardness locus at the 5HS telomere, for which there is a physical map, confirmed that the DAGGER output was more accurate for fine structure analysis. Conclusions: The R package DAGGER is an effective, freely available resource for integrating the information from a set of consistent linkage maps. Background The need to integrate information from multiple linkage maps into a consensus map is a long-standing problem in genetics [1,2]. Consensus maps have been developed for many crops, including wheat [3], sorghum [4], and potato [5]. Within the barley research community alone, at least seven consensus maps have been published in the past six years [6-12]. Wenzl et al. [7] differentiated between two broad stra- tegies for constructing consensus maps. In the traditional approach, the consensus map is determined directly from the genotypic data, using extensions of the maximum- likelihood methods developed for single populations [13]. While this approach was effective for many years, it has not always produced consistent and timely results as Correspondence: j.endelman@gmail.com Department of Crop and Soil Sciences, Washington State University, 16650 State Route 536, Mount Vernon, WA 98273, USA marker densities have continued to increase [7,14]. These limitations have spurred innovation in a second (“synthetic” [7]) strategy, in which the consensus map is generated from the linkage maps without recourse to the original genotypic data. It was Yap et al. [15] who first recognized that the complex ordinal relationships present in a series of link- age maps can be exactly represented as a directed graph (Figure 1). Each graph represents a single chromosome and each vertex in the graph represents a bin of mar- kers. Provided there are no ordering conflicts between the linkage maps, the ordinal relationships in the direc- ted graph are equivalent to those in the linkage maps. In other words, there is a path from vertex v to vertex w in the graph if and only if bin v comes before bin w in one of the linkage maps. Wu et al. [14] have capitalized on this graph-theoretic formulation in their software MergeMap [16], a free © 2011 Endelman; licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.