Revealing hidden interval graph structure in STS-content data

Motivation: STS-content data for genomic mapping contain numerous errors an d anomalies resulting in cross-links among distant regions of the genome. I dentification of contigs within the data is an important and difficult prob lem. Results: This paper introduces a graph algorithm which creates a simpl ified view of STS content data. The shape of the resulting structure graph provides a quality check - coherent data produce a straight line, while ano malous data produce branches and loops. In the latter case, it is sometimes possible to disentangle the various paths into subsets of the data coverin g contiguous regions of the genome, i.e. contigs. These straight subgraphs can then be analyzed in standard ways to construct a physical map. A theore tical basis for the method is presented along with examples of its applicat ion to current STS data from human genome centers.