Browsing by Author "Lu, WF"

Now showing 1 - 2 of 2

A clustering algorithm for interval graph test on noisy data
(2003)
Lu, WF
;
Hsu, WL
;
資訊工程學系
;
Department of Computer Science
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 for this problem, which can accommodate noisy data and produce a likely interval model realizing the original graph.
A test for the consecutive ones property on noisy data - Application to physical mapping and sequence assembly
(2003)
Lu, WF
;
Hsu, WL
;
資訊工程學系
;
Department of Computer Science
A (0,1)-matrix satisfies the consecutive ones property (COP) for the rows if there exists a column permutation such that the ones in each row of the resultant matrix are consecutive. The consecutive ones test is useful for physical mapping and DNA sequence assembly, for example, in the STS content mapping of YAC library, and in the Bactig assembly based on STS as well as EST markers. 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 for this problem, which has the following advantages: 1. If the original matrix satisfies the COP, then the algorithm will produce a column ordering realizing it without any fill-in. 2. Under moderate assumptions, the algorithm can accommodate the following four types of errors: false negatives, false positives, normnique probes, and chimeric clones. Note that in some cases (low quality EST marker identification), NPs occur because of repeat sequences. 3. In case some local data is too noisy, our algorithm could likely discover that and suggest additional lab work to reduce the degree of ambiguity in that part. 4. A unique feature of our algorithm is that, rather than forcing all probes to be included and ordered in the final arrangement, our algorithm would delete some noisy probes. Thus, it could produce more than one contig. The gaps are created mostly by noisy probes.