Endelman BMC Genomics 2011, 12:407 http://www.biomedcentral.com/1471-2164/12/407 Page 2 of 9 Figure 1 Diagram of the DAGGER package. Linkage maps are first converted into unbranched directed graphs, where each vertex is a marker bin and each edge length is the distance of the corresponding map interval. After merging the linkage maps, the consensus graph is checked for cycles, which represent ordering conflicts. Provided there are none, the consensus graph can be simplified to generate an ordinal consensus graph, which contains only those edges needed for ordinal equivalency with the linkage maps. The consensus graph can also be linearized to produce a consensus map, using either linear or quadratic programming (latter is shown). resource for constructing consensus maps. MergeMap contains an efficient algorithm for resolving ordering conflicts between linkage maps, which appear as cycles in the consensus graph. The removal of these cycles produces a directed acyclic graph, or DAG, which MergeMap then simplifies and linearizes to produce a consensus map. Close et al. [11] used MergeMap to integrate four bar- ley linkage maps genotyped at nearly 3000 SNP markers. The resulting consensus SNP map has been used for association mapping [17-19] by members of the Barley Coordinated Agriculture Project (Barley CAP) [20]. In addition to the consensus map, Close et al. [11] pub- lished consensus graphs for each of the seven barley chromosomes. While examining the fine structure of the hardness locus on the 5HS telomere, which has been sequenced [21], several unphysical orderings were detected in the consensus graph that are not present in any of the linkage maps. The discovery that the simplified consensus graphs produced by MergeMap are not ordinally equivalent to the linkage maps prompted the development of new algorithms for the simplification and linearization of con- sensus graphs. These algorithms have been implemented as a package for the R computing environment [22] called DAGGER [23]. To validate DAGGER, a new barley consensus SNP map was constructed and compared with the results of Close et al. [11]. The performance of DAG- GER was also evaluated with simulated data. Results and Discussion Constructing the consensus graph Given a list of linkage maps, DAGGER builds up the con- sensus graph sequentially. The first two linkage maps are merged to create a consensus graph, which is then merged with the next linkage map, and so on. The mer- ging algorithm proceeds from the first to the last bin in the linkage map M that is to be integrated with graph