Endelman BMC Genomics 2011, 12:407 http://www.biomedcentral.com/1471-2164/12/407 Because this double summation exactly corresponds to the edges (both directed and zero-length) in the consen- sus graph, Equation 1 can be rewritten as a sum over edges with an appropriate weighting factor: edge(v,w) qv,w |x (w) − x (v) − d (v, w)|α Analogous to Equation 1, x(v) and x(w) are the posi- tions of marker bins v and w in the consensus map (every vertex in the consensus graph becomes a bin in the consensus map), and d(v, w) ≥ 0 is an edge length. For Equation 1 to equal Equation 2, the weighting factor qv,w = (# markers in v) × (# markers in w). In addition to having minimum error, it is desirable that the consensus map be entirely consistent with the consensus graph (and by extension the linkage maps) in terms of marker order. This means that for every direc- ted edge t ® u in the consensus graph, the inequality x (t) ≤ x(u) is required for the consensus map. When this set of linear inequalities is combined with minimizing Equation 2, the constrained optimization problem solved by DAGGER can be written as min x qv,w |x (w) − x (v) − d (v, w)|α (2) (3) edge(v,w) x (t) ≤ x (u) It is straightforward to show that Equation 3 can be solved by linear (a = 1) or quadratic (a = 2) program- ming methods. Let A be the p × n adjacency matrix for the directed edges in the consensus graph (p edges, n vertices). This means that in correspondence with the kth edge t ® u, the kth row of A contains -1 at the posi- tion for bin t and 1 at the position for bin u. The r × n adjacency matrix B for the zero-length edges is defined similarly, and the combined (p+r)× n adjacency matrix C is formed by stacking A on B. If the vector d contains Table 1 DAGGER performance on simulated data the edge lengths d(v, w) corresponding to the rows of A (d > 0) and B (d = 0), then the error vector is Cx - d and the consistency constraints are Ax ≥ 0. For a = 2, Equation 3 is equivalent to the following quadratic pro- gram (QP): where the matrix Q = diag(q), and q is the vector of weights qv, w in Equation 3. By introducing p+r addi- tional variables, denoted by z, Equation 3 with a = 1 is equivalent to the following linear program (LP) [26]: min (Cx − d) Q(Cx − d) x Ax ≥ 0 min q’z x, z −z ≤ Cx − d ≤ z Ax ≥ 0 Page 4 of 9 (4) (5) Validation with simulated data To test the performance of DAGGER, it was applied to simulated linkage maps generated from 1000 evenly spaced markers with a total map length of 100 cM. The results in Table 1 are for random parents with an aver- age sequence identity of 70%, for which the expected number of markers per linkage map is 0.3 × 1000 = 300. Using more divergent parents led to maps with more markers, but the trends were the same. The simulated data illustrate the primary benefit of integrating multiple linkage maps, which is that higher marker densities are possible. Table 1 shows that the average number of markers in each linkage map was indistinguishable from the expected value of 300. Con- sensus maps based on two linkage maps contained an average of 514 markers, and with eight linkage maps an average marker density of 944 out of 1000 was achieved. # Markers Map length, cM Mean absolute error, cM RMS error, cM Time, s 1 300 (1) 99 (1) 4.0 (0.2) 4.7 (0.2) – 2 514 (2) 82.9 (0.6) 87.7 (0.6) 3.4 (0.2) 3.1 (0.2) 4.0 (0.2) 3.6 (0.2) 2.0 (0.0) 2.0 (0.0) # Linkage maps 4 761 (1) 70.9 (0.5) 73.9 (0.4) 2.6 (0.1) 2.4 (0.1) 3.1 (0.1) 2.8 (0.1) 11.0 (0.1) 11.7 (0.1) 6 884 (1) 61.6 (0.4) 66.2 (0.3) 2.4 (0.1) 2.2 (0.1) 2.9 (0.1) 2.6 (0.1) 29.6 (0.2) 29.4 (0.2) 8 944 (1) 56.4 (0.3) 61.6 (0.3) 2.3 (0.1) 2.0 (0.1) 2.7 (0.1) 2.4 (0.1) 57.4 (0.4) 50.7 (0.4) Method LP/QP LP QP LP QP LP QP LP QP The mean (and SE) are reported for 100 simulations of a 100 cM interval containing 1000 markers. Linkage maps were generated from doubled haploid populations of 200 offspring, using parents with 70% sequence identity. Results are shown for both the LP and QP methods of linearizing the consensus graph (error was calculated after rescaling).