TR-IIS-03-010    PDF format

A Test for Interval Graph on Noisy Data

Abstract

An interval graph is the intersection graph of a collection of intervals. One important application of interval graph is physical mapping in genome research, that is, to reassemble the clones to determine the relative position of fragments of DNA along the genome. The linear time algorithm by Booth and Lueker (1976) for this problem has a serious drawback: the data must be error-free. However, laboratory work is never flawless. We devised a new iterative clustering algorithm based on local structure matching, which can accommodate noisy data and produce a likely interval model realizing the original graph.

Keywords: interval graph recognition, physical mapping, DNA sequence assembly, probe hybridization, clustering algorithm.