TR-IIS-06-004    Fulltext

A Test for Interval Graphs on Noisy Data – DNA Fragment Assembly

Wei-Fu Lu and Wen-Lian Hsu


An interval graph is the intersection graph of a collection of intervals. One important application of interval graph is the construction of physical maps 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 is robust enough to accommodate a certain percentage of noisy data and to produce a likely interval model realizing the original graph.


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