BACKGROUND
the need to integrate information from multiple linkage maps into a consensus map is a long-standing problem in genetics  <cit> .
consensus maps have been developed for many crops, including wheat  <cit> , sorghum  <cit> , and potato  <cit> .
within the barley research community alone, at least seven consensus maps have been published in the past six years  <cit> .
wenzl et al.
<cit>  differentiated between two broad strategies 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  <cit> .
while this approach was effective for many years, it has not always produced consistent and timely results as marker densities have continued to increase  <cit> .
these limitations have spurred innovation in a second  strategy, in which the consensus map is generated from the linkage maps without recourse to the original genotypic data.
it was yap et al.
<cit>  who first recognized that the complex ordinal relationships present in a series of linkage maps can be exactly represented as a directed graph .
each graph represents a single chromosome and each vertex in the graph represents a bin of markers.
provided there are no ordering conflicts between the linkage maps, the ordinal relationships in the directed 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.
<cit>  have capitalized on this graph-theoretic formulation in their software mergemap  <cit> , a free 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.
<cit>  used mergemap to integrate four barley linkage maps genotyped at nearly  <dig> snp markers.
the resulting consensus snp map has been used for association mapping  <cit>  by members of the barley coordinated agriculture project   <cit> .
in addition to the consensus map, close et al.
<cit>  published 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  <cit> , 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 consensus graphs.
these algorithms have been implemented as a package for the r computing environment  <cit>  called dagger  <cit> .
to validate dagger, a new barley consensus snp map was constructed and compared with the results of close et al.
<cit> .
the performance of dagger was also evaluated with simulated data.
RESULTS
constructing the consensus graph
given a list of linkage maps, dagger builds up the consensus 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 merging algorithm proceeds from the first to the last bin in the linkage map m that is to be integrated with graph g. let sv be the set of vertices in g that contain one or more markers in bin v of m. for each vertex w in sv, if all of the markers in w are contained in v, then w remains intact.
if only some of the markers in w are in v, then w is split into two vertices: w <dig> contains the common markers between v and w, and w <dig> contains the remaining markers in w. all of the edges directed in and out of w are replicated for w <dig> and w <dig>  vertex w <dig> also receives new edges directed in and out of it according to the immediately proximal and distal bins in m. any markers in v that were not present in g are added as a new vertex with appropriate edges.
when completed, the consensus graph contains a directed edge for every map interval between adjacent bins in the linkage maps .
during construction of the consensus graph, dagger also keeps track of which markers were binned in the linkage maps.
the map distance between binned markers is zero, and this information is needed to minimize the error between the consensus map and linkage maps .
although depicted in the consensus graph , the zero-length edges are not part of its topology .
dagger checks for ordering conflicts between the linkage maps by identifying the strongly connected components of the consensus graph.
two vertices v and w are strongly connected if there is a path from v to w and from w to v. in the context of markers, that would mean the markers in v mapped before those in w, which in turn mapped before those in v; this represents an inconsistency between the linkage maps.
identifying the strongly connected components of a directed graph is a standard exercise in computer science  <cit> .
dagger performs two depth-first searches, one on the reverse graph gr , and then on g itself.
the traversal of gr generates a topologically sorted list of the vertices.
by conducting the depth-first search of g in this order, the algorithm identifies the strongly connected components of g.
dagger will only proceed with graph simplification and linearization if the marker order between linkage maps is consistent.
to facilitate manual curation of errors in the linkage maps, dagger will output the strongly connected components of g for visualization with the graphviz dot software  <cit> .
when the inconsistency is due to a small misplacement, this visual will indicate where to look in the genotypic data to resolve the ordering conflict.
for more complex and long-distance inconsistencies, the conflict-resolution algorithm in mergemap  <cit>  is a valuable resource.
simplifying the consensus graph
in the absence of ordering conflicts, dagger will output the consensus graph for visualization in one of two forms.
the first option is to display the graph with all of the distance information used to generate the consensus map.
the second option is to simplify the graph so that it conveys the ordering of the markers but not their distances, which potentially allows many edges to be removed .
the ordinal consensus graph produced by dagger contains only those edges that are needed to satisfy the equivalency property stated in the introduction, namely, that there exists a path from vertex v to vertex w if and only if bin v mapped before bin w in one of the linkage maps.
the edge reduction proceeds by first using the topologically sorted vertex list from the depth-first search of gr to determine, for each vertex v, the list of all vertices reachable from v. next, the edges for each vertex are considered for elimination according to the topological sort order of the vertices to which they are directed.
let q be a topologically sorted list of the vertices to which there are directed edges from vertex v. if vertex qk is reachable from vertex qj with j < k, then the edge to qk is removed.
following the edge reduction, dagger performs one other simplification without loss of ordinal information.
some of the marker bins that were split during the construction of the consensus graph, due to different distance estimates, may have the same pattern of inward and outward edges after the edge reduction.
these vertices are combined and their markers put back in one bin.
linearizing the consensus graph
whereas the ordinal consensus graph produced by dagger will not be invalidated by further research , this is not true of the marker order in the consensus map.
because recombination distances are population-dependent, the relative order of markers that have not been mapped together in a single population cannot always be determined unambiguously.
dagger generates a consensus map by minimizing the "error" between the consensus map and the linkage maps.
in mathematical terms, this error may be written as
where x and x are the positions of markers m <dig> and m <dig> in the consensus map x, and dk ≥  <dig> is a distance interval from the kth linkage map.
when the exponent α =  <dig>  dagger minimizes the l <dig> norm; when α =  <dig>  the l <dig> norm is minimized.
the outer sum in equation  <dig> is over the linkage maps, and the inner sum is over all pairs of markers  in either the same or adjacent bins in the kth linkage map.
because this double summation exactly corresponds to the edges  in the consensus graph, equation  <dig> can be rewritten as a sum over edges with an appropriate weighting factor:
analogous to equation  <dig>  x and x are the positions of marker bins v and w in the consensus map , and d ≥  <dig> is an edge length.
for equation  <dig> to equal equation  <dig>  the weighting factor qv,w =  × .
in addition to having minimum error, it is desirable that the consensus map be entirely consistent with the consensus graph  in terms of marker order.
this means that for every directed edge t → u in the consensus graph, the inequality x ≤ x is required for the consensus map.
when this set of linear inequalities is combined with minimizing equation  <dig>  the constrained optimization problem solved by dagger can be written as
it is straightforward to show that equation  <dig> can be solved by linear  or quadratic  programming methods.
let a be the p × n adjacency matrix for the directed edges in the consensus graph .
this means that in correspondence with the kth edge t → u, the kth row of a contains - <dig> at the position for bin t and  <dig> at the position for bin u. the r × n adjacency matrix b for the zero-length edges is defined similarly, and the combined × n adjacency matrix c is formed by stacking a on b. if the vector d contains the edge lengths d corresponding to the rows of a  and b , then the error vector is cx - d and the consistency constraints are ax ≥  <dig>  for α =  <dig>  equation  <dig> is equivalent to the following quadratic program :
where the matrix q = diag, and q is the vector of weights qv, w in equation  <dig>  by introducing p+r additional variables, denoted by z, equation  <dig> with α =  <dig> is equivalent to the following linear program   <cit> :
validation with simulated data
to test the performance of dagger, it was applied to simulated linkage maps generated from  <dig> evenly spaced markers with a total map length of  <dig> cm.
the results in table  <dig> are for random parents with an average sequence identity of 70%, for which the expected number of markers per linkage map is  <dig>  ×  <dig> =  <dig>  using more divergent parents led to maps with more markers, but the trends were the same.
the mean  are reported for  <dig> simulations of a  <dig> cm interval containing  <dig> markers.
linkage maps were generated from doubled haploid populations of  <dig> offspring, using parents with 70% sequence identity.
results are shown for both the lp and qp methods of linearizing the consensus graph .
the simulated data illustrate the primary benefit of integrating multiple linkage maps, which is that higher marker densities are possible.
table  <dig> shows that the average number of markers in each linkage map was indistinguishable from the expected value of  <dig>  consensus maps based on two linkage maps contained an average of  <dig> markers, and with eight linkage maps an average marker density of  <dig> out of  <dig> was achieved.
an unusual feature of both the lp and qp linearization methods is their tendency to compress map intervals, whereas most consensus maps are inflated relative to the original linkage maps .
as shown in table  <dig>  the amount of compression increased as more linkage maps were integrated.
for two linkage maps, the lp and qp consensus maps were compressed by 17% and 12% respectively, while for eight linkage maps the compression was 44%  and 38% .
the qp consensus maps had consistently less compression than the lp maps.
for the simple example shown in figure  <dig>  where both linkage maps have a total length of  <dig>  cm, one can verify analytically that the qp consensus map is compressed to  <dig>  cm .
by default dagger rescales the consensus map so that its total length equals the mean length of the component linkage maps, but the user can also request the compressed map.
validation with barley data
the original impetus for developing dagger came from analyzing the results of close et al.
<cit> , who used mergemap  <cit>  to integrate the information from four barley linkage maps genotyped at nearly  <dig> snp markers.
these same linkage maps were used as input for dagger, and no ordering conflicts were detected.
the ordinal consensus graphs for the seven barley chromosomes  and the qp consensus map  produced by dagger are available online.
abbreviations are sm = steptoe × morex, owb = oregon wolfe barley, mb = morex × barke, ho = haruno nijo × ouh <dig>  blank entries indicate the marker was not mapped in that population.
none of the ordinal information in the dagger graph violates this physical order.
the only relationships among the hinb/hina/gsp markers in the dagger graph are that marker 3_ <dig> is distal to markers 3_ <dig>  3_ <dig>  and 3_ <dig>  table  <dig> shows that this information comes from the oregon wolfe barley  linkage map, and that no other ordinal information for the hardness locus markers is present in the linkage maps.
mergemap also captures this ordering, but in addition there are numerous relationships that are not present in the linkage maps.
this is apparent from the unphysical ordering of the hinb/hina/gsp markers.
mergemap shows the markers 3_ <dig>  3_ <dig>  3_ <dig>  and 2_ <dig> as mapping distal to both hinb markers, and the marker 3_ <dig> is shown distal to 3_ <dig>  the order of these markers is indeterminate from the linkage maps, which is how they are portrayed by dagger.
the unphysical relationships in the simplified graph from mergemap arise because of the way markers are binned.
mergemap will potentially bin markers if they are binned in at least one of the linkage maps and if their order is indeterminate  <cit> .
to appreciate the consequences of this rule, consider the vertex with six markers at the top of the mergemap graph.
four of these markers are from the hardness locus and were only present in the steptoe-morex  map: 3_ <dig>  3_ <dig>  3_ <dig>  and 2_ <dig>  the other two markers in the vertex--1_ <dig> and 2_0894--are binned with the hardness locus markers in the sm linkage map .
the markers 1_ <dig> and 2_ <dig> were also co-segregating in the morex-barke  population, where they mapped distal to the hinb marker 3_ <dig>  because the aforementioned hina and gsp markers were binned with 1_ <dig> and 2_ <dig> in the sm linkage map, and because their relationship to 3_ <dig> is indeterminate from the linkage maps, mergemap binned all six markers together.
this creates the implication that the hina and gsp markers are distal to 3_ <dig>  which is consistent with the linkage maps but not implied by them .
as this example illustrates, the simplified graphs from mergemap are not ordinally equivalent to the linkage maps and will potentially contain unphysical relationships even if the linkage maps do not.
the simplified graphs from dagger are ordinally equivalent to the linkage maps and will not contain unphysical relationships provided the linkage maps are physically correct.
the dagger map was generated with the qp method.
nonetheless, there were several indications of improved fine structure with dagger.
figure  <dig> compares the two  consensus maps at the 5hs telomere.
on the physical map the hardness locus  is  <dig> kb, within which there was only  <dig> recombinant out of the  <dig> total individuals in the sm, owb, and mb populations  <cit> .
this is reflected in the linkage maps in table  <dig>  where all the hardness locus markers appear in one bin in both the sm and mb linkage maps and in two bins separated by  <dig>  cm in the owb linkage map.
from these data the hardness locus should occupy less than  <dig> cm in the consensus map, which was true with dagger  but not with mergemap .
figure  <dig> shows the rms error between the consensus map and the linkage maps for each of the seven barley chromosomes.
the dagger map had consistently less error, with an average of  <dig>  cm per marker interval compared to  <dig>  cm with mergemap.
CONCLUSIONS
new algorithms for the simplification and linearization of consensus graphs have been implemented as a package for the r computing environment called dagger.
the package offers both linear and quadratic programming options for linearizing the consensus graph.
when these two methods were compared using simulated data, the consensus maps generated by quadratic programming had less compression and higher accuracy.
when applied to four barley linkage maps genotyped at nearly  <dig> snp markers, in less than one minute dagger produced a consensus map with improved fine structure compared to the existing barley consensus snp map.
the rms error between the linkage maps and the dagger map was  <dig>  cm per marker interval compared to  <dig>  cm for the existing consensus map.
examination of the barley hardness locus at the 5hs telomere confirmed that the dagger output was more accurate for fine structure analysis.
dagger is an effective, freely available resource for integrating the information from a set of consistent linkage maps.

 the need to integrate information from multiple linkage maps into a consensus map is a long-standing problem in genetics. consensus maps have been developed for many crops, including wheat, sorghum, and potato. within the barley research community alone, at least seven consensus maps have been published in the past six years. wenzl et al. differentiated between two broad strategies 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. while this approach was effective for many years, it has not always produced consistent and timely results as marker densities have continued to increase. these limitations have spurred innovation in a second strategy, in which the consensus map is generated from the linkage maps without recourse to the original genotypic data. it was yap et al. who first recognized that the complex ordinal relationships present in a series of linkage maps can be exactly represented as a directed graph. each graph represents a single chromosome and each vertex in the graph represents a bin of markers. provided there are no ordering conflicts between the linkage maps, the ordinal relationships in the directed 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. have capitalized on this graph-theoretic formulation in their software mergemap, a free 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. used mergemap to integrate four barley linkage maps genotyped at nearly snp markers. the resulting consensus snp map has been used for association mapping by members of the barley coordinated agriculture project. in addition to the consensus map, close et al. published 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, 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 consensus graphs. these algorithms have been implemented as a package for the r computing environment called dagger. to validate dagger, a new barley consensus snp map was constructed and compared with the results of close et al.. the performance of dagger was also evaluated with simulated data.  constructing the consensus graph given a list of linkage maps, dagger builds up the consensus 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 merging algorithm proceeds from the first to the last bin in the linkage map m that is to be integrated with graph g. let sv be the set of vertices in g that contain one or more markers in bin v of m. for each vertex w in sv, if all of the markers in w are contained in v, then w remains intact. if only some of the markers in w are in v, then w is split into two vertices: w contains the common markers between v and w, and w contains the remaining markers in w. all of the edges directed in and out of w are replicated for w and w vertex w also receives new edges directed in and out of it according to the immediately proximal and distal bins in m. any markers in v that were not present in g are added as a new vertex with appropriate edges. when completed, the consensus graph contains a directed edge for every map interval between adjacent bins in the linkage maps. during construction of the consensus graph, dagger also keeps track of which markers were binned in the linkage maps. the map distance between binned markers is zero, and this information is needed to minimize the error between the consensus map and linkage maps. although depicted in the consensus graph, the zero-length edges are not part of its topology. dagger checks for ordering conflicts between the linkage maps by identifying the strongly connected components of the consensus graph. two vertices v and w are strongly connected if there is a path from v to w and from w to v. in the context of markers, that would mean the markers in v mapped before those in w, which in turn mapped before those in v; this represents an inconsistency between the linkage maps. identifying the strongly connected components of a directed graph is a standard exercise in computer science. dagger performs two depth-first searches, one on the reverse graph gr, and then on g itself. the traversal of gr generates a topologically sorted list of the vertices. by conducting the depth-first search of g in this order, the algorithm identifies the strongly connected components of g. dagger will only proceed with graph simplification and linearization if the marker order between linkage maps is consistent. to facilitate manual curation of errors in the linkage maps, dagger will output the strongly connected components of g for visualization with the graphviz dot software. when the inconsistency is due to a small misplacement, this visual will indicate where to look in the genotypic data to resolve the ordering conflict. for more complex and long-distance inconsistencies, the conflict-resolution algorithm in mergemap is a valuable resource. simplifying the consensus graph in the absence of ordering conflicts, dagger will output the consensus graph for visualization in one of two forms. the first option is to display the graph with all of the distance information used to generate the consensus map. the second option is to simplify the graph so that it conveys the ordering of the markers but not their distances, which potentially allows many edges to be removed. the ordinal consensus graph produced by dagger contains only those edges that are needed to satisfy the equivalency property stated in the introduction, namely, that there exists a path from vertex v to vertex w if and only if bin v mapped before bin w in one of the linkage maps. the edge reduction proceeds by first using the topologically sorted vertex list from the depth-first search of gr to determine, for each vertex v, the list of all vertices reachable from v. next, the edges for each vertex are considered for elimination according to the topological sort order of the vertices to which they are directed. let q be a topologically sorted list of the vertices to which there are directed edges from vertex v. if vertex qk is reachable from vertex qj with j < k, then the edge to qk is removed. following the edge reduction, dagger performs one other simplification without loss of ordinal information. some of the marker bins that were split during the construction of the consensus graph, due to different distance estimates, may have the same pattern of inward and outward edges after the edge reduction. these vertices are combined and their markers put back in one bin. linearizing the consensus graph whereas the ordinal consensus graph produced by dagger will not be invalidated by further research, this is not true of the marker order in the consensus map. because recombination distances are population-dependent, the relative order of markers that have not been mapped together in a single population cannot always be determined unambiguously. dagger generates a consensus map by minimizing the "error" between the consensus map and the linkage maps. in mathematical terms, this error may be written as where x and x are the positions of markers m and m in the consensus map x, and dk ≥ is a distance interval from the kth linkage map. when the exponent α = dagger minimizes the l norm; when α = the l norm is minimized. the outer sum in equation is over the linkage maps, and the inner sum is over all pairs of markers in either the same or adjacent bins in the kth linkage map. because this double summation exactly corresponds to the edges in the consensus graph, equation can be rewritten as a sum over edges with an appropriate weighting factor: analogous to equation x and x are the positions of marker bins v and w in the consensus map, and d ≥ is an edge length. for equation to equal equation the weighting factor qv,w = ×. in addition to having minimum error, it is desirable that the consensus map be entirely consistent with the consensus graph in terms of marker order. this means that for every directed edge t → u in the consensus graph, the inequality x ≤ x is required for the consensus map. when this set of linear inequalities is combined with minimizing equation the constrained optimization problem solved by dagger can be written as it is straightforward to show that equation can be solved by linear or quadratic programming methods. let a be the p × n adjacency matrix for the directed edges in the consensus graph. this means that in correspondence with the kth edge t → u, the kth row of a contains - at the position for bin t and at the position for bin u. the r × n adjacency matrix b for the zero-length edges is defined similarly, and the combined × n adjacency matrix c is formed by stacking a on b. if the vector d contains the edge lengths d corresponding to the rows of a and b, then the error vector is cx - d and the consistency constraints are ax ≥ for α = equation is equivalent to the following quadratic program: where the matrix q = diag, and q is the vector of weights qv, w in equation by introducing p+r additional variables, denoted by z, equation with α = is equivalent to the following linear program: validation with simulated data to test the performance of dagger, it was applied to simulated linkage maps generated from evenly spaced markers with a total map length of cm. the results in table are for random parents with an average sequence identity of 70%, for which the expected number of markers per linkage map is × = using more divergent parents led to maps with more markers, but the trends were the same. the mean are reported for simulations of a cm interval containing markers. linkage maps were generated from doubled haploid populations of offspring, using parents with 70% sequence identity. results are shown for both the lp and qp methods of linearizing the consensus graph. the simulated data illustrate the primary benefit of integrating multiple linkage maps, which is that higher marker densities are possible. table shows that the average number of markers in each linkage map was indistinguishable from the expected value of consensus maps based on two linkage maps contained an average of markers, and with eight linkage maps an average marker density of out of was achieved. an unusual feature of both the lp and qp linearization methods is their tendency to compress map intervals, whereas most consensus maps are inflated relative to the original linkage maps. as shown in table the amount of compression increased as more linkage maps were integrated. for two linkage maps, the lp and qp consensus maps were compressed by 17% and 12% respectively, while for eight linkage maps the compression was 44% and 38%. the qp consensus maps had consistently less compression than the lp maps. for the simple example shown in figure where both linkage maps have a total length of cm, one can verify analytically that the qp consensus map is compressed to cm. by default dagger rescales the consensus map so that its total length equals the mean length of the component linkage maps, but the user can also request the compressed map. validation with barley data the original impetus for developing dagger came from analyzing the results of close et al., who used mergemap to integrate the information from four barley linkage maps genotyped at nearly snp markers. these same linkage maps were used as input for dagger, and no ordering conflicts were detected. the ordinal consensus graphs for the seven barley chromosomes and the qp consensus map produced by dagger are available online. abbreviations are sm = steptoe × morex, owb = oregon wolfe barley, mb = morex × barke, ho = haruno nijo × ouh blank entries indicate the marker was not mapped in that population. none of the ordinal information in the dagger graph violates this physical order. the only relationships among the hinb/hina/gsp markers in the dagger graph are that marker 3_ is distal to markers 3_ 3_ and 3_ table shows that this information comes from the oregon wolfe barley linkage map, and that no other ordinal information for the hardness locus markers is present in the linkage maps. mergemap also captures this ordering, but in addition there are numerous relationships that are not present in the linkage maps. this is apparent from the unphysical ordering of the hinb/hina/gsp markers. mergemap shows the markers 3_ 3_ 3_ and 2_ as mapping distal to both hinb markers, and the marker 3_ is shown distal to 3_ the order of these markers is indeterminate from the linkage maps, which is how they are portrayed by dagger. the unphysical relationships in the simplified graph from mergemap arise because of the way markers are binned. mergemap will potentially bin markers if they are binned in at least one of the linkage maps and if their order is indeterminate. to appreciate the consequences of this rule, consider the vertex with six markers at the top of the mergemap graph. four of these markers are from the hardness locus and were only present in the steptoe-morex map: 3_ 3_ 3_ and 2_ the other two markers in the vertex--1_ and 2_0894--are binned with the hardness locus markers in the sm linkage map. the markers 1_ and 2_ were also co-segregating in the morex-barke population, where they mapped distal to the hinb marker 3_ because the aforementioned hina and gsp markers were binned with 1_ and 2_ in the sm linkage map, and because their relationship to 3_ is indeterminate from the linkage maps, mergemap binned all six markers together. this creates the implication that the hina and gsp markers are distal to 3_ which is consistent with the linkage maps but not implied by them. as this example illustrates, the simplified graphs from mergemap are not ordinally equivalent to the linkage maps and will potentially contain unphysical relationships even if the linkage maps do not. the simplified graphs from dagger are ordinally equivalent to the linkage maps and will not contain unphysical relationships provided the linkage maps are physically correct. the dagger map was generated with the qp method. nonetheless, there were several indications of improved fine structure with dagger. figure compares the two consensus maps at the 5hs telomere. on the physical map the hardness locus is kb, within which there was only recombinant out of the total individuals in the sm, owb, and mb populations. this is reflected in the linkage maps in table where all the hardness locus markers appear in one bin in both the sm and mb linkage maps and in two bins separated by cm in the owb linkage map. from these data the hardness locus should occupy less than cm in the consensus map, which was true with dagger but not with mergemap. figure shows the rms error between the consensus map and the linkage maps for each of the seven barley chromosomes. the dagger map had consistently less error, with an average of cm per marker interval compared to cm with mergemap.  new algorithms for the simplification and linearization of consensus graphs have been implemented as a package for the r computing environment called dagger. the package offers both linear and quadratic programming options for linearizing the consensus graph. when these two methods were compared using simulated data, the consensus maps generated by quadratic programming had less compression and higher accuracy. when applied to four barley linkage maps genotyped at nearly snp markers, in less than one minute dagger produced a consensus map with improved fine structure compared to the existing barley consensus snp map. the rms error between the linkage maps and the dagger map was cm per marker interval compared to cm for the existing consensus map. examination of the barley hardness locus at the 5hs telomere confirmed that the dagger output was more accurate for fine structure analysis. dagger is an effective, freely available resource for integrating the information from a set of consistent linkage maps. 
when applied to four barley linkage maps genotyped at nearly snp markers, dagger produced a consensus map with improved fine structure compared to the existing barley consensus snp 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. the root-mean-squared error between the linkage maps and the dagger map was cm per marker interval compared to cm for the existing consensus map. the need to integrate information from multiple linkage maps is a long-standing problem in genetics. the r package dagger is an effective, freely available resource for integrating the information from a set of consistent linkage maps. 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. 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 than the individual linkage maps in genetic simulations. new algorithms for the simplification and linearization of consensus graphs have been implemented as a package for the r computing environment called dagger. one way to visualize the complex ordinal relationships is with a directed graph, where each vertex in the graph is a bin of markers.
 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.  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 than the individual linkage maps in genetic simulations. when applied to four barley linkage maps genotyped at nearly 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 cm per marker interval compared to 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.  the r package dagger is an effective, freely available resource for integrating the information from a set of consistent linkage maps. 