Name
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. |
Year | Venue | Keywords |
|---|---|---|
2005 | symposium on the theory of computing | pln l,different optimization criterion,greedy algorithm yield,oligonu- cleotide ngerprin ting,clustering fingerprint,efficient method,dna clone library,ln n,fingerprint vector,np-hardness,p missing value,oligonucleotide fingerprinting,approximate clustering,polynomial time,approximation algorithms,clustering,greedy algorithm,missing values |
Field | DocType | Volume |
Approximation algorithm,Discrete mathematics,Combinatorics,Greedy algorithm,Fingerprint,Missing data,Time complexity,Cluster analysis,Mathematics | Journal | abs/cs/0511082 |
ISBN | Citations | PageRank |
1-920682-23-6 | 4 | 0.58 |
References | Authors | |
1 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andres Figueroa | 1 | 42 | 4.27 |
| Avraham Goldstein | 2 | 5 | 2.29 |
| Jiang, Tao | 3 | 339 | 14.58 |
| Maciej Kurowski | 4 | 78 | 6.25 |
| A. Lingas | 5 | 250 | 45.63 |
| Mia Persson | 6 | 30 | 7.17 |