Endelman BMC Genomics 2011, 12:407 http://www.biomedcentral.com/1471-2164/12/407 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: w1 contains the common mar- kers between v and w, and w2 contains the remaining markers in w. All of the edges directed in and out of w are replicated for w1 and w2. Vertex w1 also receives new edges directed in and out of it according to the immedi- ately 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 (Figure 1). During construction of the consensus graph, DAGGER also keeps track of which markers were binned in the link- age 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 (see below). Although depicted in the consensus graph (Figure 1), the zero-length edges are not part of its topology (i.e., they do not imply ordinal relationships). DAGGER checks for ordering conflicts between the linkage maps by identifying the strongly connected com- ponents 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 [24]. DAGGER performs two depth-first searches, one on the reverse graph GR (formed by reversing the edges in G), and then on G itself. The traversal of GR generates a topo- logically sorted list of the vertices. By conducting the depth-first search of G in this order, the algorithm identi- fies 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 [25]. When the inconsis- tency is due to a small misplacement, this visual will indi- cate where to look in the genotypic data to resolve the ordering conflict. For more complex and long-distance inconsistencies, the conflict-resolution algorithm in Mer- geMap [14] is a valuable resource. Simplifying the consensus graph In the absence of ordering conflicts, DAGGER will out- put the consensus graph for visualization in one of two forms. The first option is to display the graph with all of Page 3 of 9 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 dis- tances, which potentially allows many edges to be removed (Figure 1). 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 ver- tices 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 con- struction of the consensus graph, due to different dis- tance 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 (provided the component linkage maps are correct), this is not true of the marker order in the consensus map. Because recombination distances are population-depen- dent, 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 |x (m2) − x (m1) − dk (m1, m2)| α (1) k (m1,m2) where x(m1) and x(m2) are the positions of markers m1 and m2 in the consensus map x, and dk(m1,m2) ≥ 0 is a distance interval from the kth linkage map. When the exponent a = 1, DAGGER minimizes the L1 norm; when a = 2, the L2 norm is minimized. The outer sum in Equation 1 is over the linkage maps, and the inner sum is over all pairs of markers (m1,m2) in either the same or adjacent bins in the kth linkage map.