Genetics, Vol. 165, 2235-2247, December 2003, Copyright © 2003

A Graph-Theoretic Approach to Comparing and Integrating Genetic, Physical and Sequence-Based Maps

Immanuel V. Yapa, David Schneiderb, Jon Kleinbergc, David Matthewsd, Samuel Cartinhourb, and Susan R. McCoucha
a Department of Plant Breeding, Cornell University, Ithaca, New York 14853,
b United States Department of Agriculture-Agricultural Research Service, Center for Agricultural Bioinformatics, Cornell Theory Center, Ithaca, New York 14853,
c Department of Computer Science, Cornell University, Ithaca, New York 14853
d United States Department of Agriculture-Agricultural Research Service, Cornell University, Ithaca, New York 14853

Corresponding author: Susan R. McCouch, 162 Emerson Hall, Cornell University, Ithaca, NY 14853-1901., SRM4{at}cornell.edu (E-mail)

Communicating editor: G. A. CHURCHILL

For many species, multiple maps are available, often constructed independently by different research groups using different sets of markers and different source material. Integration of these maps provides a higher density of markers and greater genome coverage than is possible using a single study. In this article, we describe a novel approach to comparing and integrating maps by using abstract graphs. A map is modeled as a directed graph in which nodes represent mapped markers and edges define the order of adjacent markers. Independently constructed graphs representing corresponding maps from different studies are merged on the basis of their common loci. Absence of a path between two nodes indicates that their order is undetermined. A cycle indicates inconsistency among the mapping studies with regard to the order of the loci involved. The integrated graph thus produced represents a complete picture of all of the mapping studies that comprise it, including all of the ambiguities and inconsistencies among them. The objective of this representation is to guide additional research aimed at interpreting these ambiguities and inconsistencies in locus order rather than presenting a "consensus order" that ignores these problems.