aiSee: Consensus Genetic Maps

Consensus Genetic Maps

“A genetic map is an ordering of genetic markers constructed from genetic linkage data for use in linkage studies and experimental design. While traditional methods have focused on constructing maps from a single population study, increasingly maps are generated for multiple lines and populations of the same organism. For example, in crop plants, where the genetic variability is high, researchers have created maps for many populations.

In the face of these new data, we address the increasingly important problem of generating a consensus map — an ordering of all markers in the various population studies.

In our method, each input map is treated as a partial order on a set of markers. To find the most consistent order shared between maps, we model the partial orders as directed graphs.

We create an aggregate by merging the transitive closure of the input graphs and taking the transitive reduction of the result. In this process, cycles may need to be broken to resolve inconsistencies between the inputs. The cycle breaking problem is NP-hard, but the problem size depends upon the scope of the inconsistency between the input graphs, which will be local if the input graphs are from closely related organisms.

We implemented our method as a Java program (available upon request). The output of the program is a GDL file which is input to aiSee.

The resulting consensus map embodies the entire set of gene order information, as it combines the data from various inputs. The consensus map graph is transitively reduced, and in addition to the order, provides three pieces of information. First, it shows in dashed line the edges removed during cycle breaking to reach the consensus. Second, it shows the error ratio as edge line thickness. Finally, it tags each marker with the set of input maps that marker occurred in, shown as a string of pluses and minuses in additional node information windows.

The generated graphs could be used in identifying those areas of the chromosome with a large amount of ambiguity ”and in prioritizing the design of laboratory experiments to fill in the missing information.

Benjamin N. Jackson, Srinivas Aluru, and Patrick S. Schnable, Iowa State University