1. |
- Figueroa, Andres, et al.
(författare)
-
Approximate clustering of fingerprint vectors with missing values
- 2005
-
Ingår i: Proceedings of the 2005 Australasian symposium on Theory of computing. - 1445-1336. - 1920682236 ; , s. 57-60
-
Konferensbidrag (refereegranskat)abstract
- We study the problem of clustering fingerprints with at most p missing values (CMV (p) for short) naturally arising in oligonucleotide fingerprinting, which is an efficient method for characterizing DNA clone libraries.We show that already CMV(2) is NP-hard. We also show that a greedy algorithm yields a min(1 + ln n, 2+pln l) approximation for CMV(p), and can be implemented to run in O(nl2p) time. Furthermore, we introduce other variants of the problem of clustering fingerprints with at most p missing values based on slightly different optimization criteria and show that they can be approximated in polynomial time with ratios 22p-1 and 2(1 - [EQUATION]), respectively.
|
|