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+lnn,2+plnl) approximation for CMV(p), and can be implemented to run in O(nl2^p) time. We also introduce other variants of the problem of clustering incomplete fingerprints based on slightly different optimization criteria and show that they can be approximated in polynomial time with ratios 2^2^p^-^1 and 2(1-12^2^p), respectively. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jda.2007.01.004 | J. Discrete Algorithms |
Keywords | Field | DocType |
p missing value,oligonucleotide fingerprinting,greedy algorithm yield,different optimization criterion,approximation algorithms,approximate clustering,clustering fingerprint,efficient method,polynomial time,clustering,dna clone library,incomplete fingerprint,np-hardness,missing values,greedy algorithm | Approximation algorithm,Discrete mathematics,Combinatorics,Greedy algorithm,Missing data,Time complexity,Cluster analysis,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
1 | 0.39 | 2 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Figueroa | 1 | 1 | 0.39 |
| A. Goldstein | 2 | 1 | 0.39 |
| Tao Jiang | 3 | 1809 | 155.32 |
| M. Kurowski | 4 | 1 | 0.39 |
| A. Lingas | 5 | 250 | 45.63 |
| M. Persson | 6 | 1 | 0.39 |