Advanced

Approximate clustering of incomplete fingerprints

Figueroa, Andres; Goldstein, Avraham; Jiang, Tao; Kurowski, Maciej; Lingas, Andrzej LU and Persson, Mia LU (2008) In Journal of Discrete Algorithms 6(1). p.103-108
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(nl2p) 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 22p−1 and Click to view the MathML source, respectively.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Journal of Discrete Algorithms
volume
6
issue
1
pages
103 - 108
publisher
Elsevier
external identifiers
  • scopus:39149127023
ISSN
1570-8667
DOI
10.1016/j.jda.2007.01.004
project
VR 2005-4085
language
English
LU publication?
yes
id
efd1d85f-ad82-4a9f-a601-6db6414d2a1a (old id 629480)
date added to LUP
2007-11-27 15:10:40
date last changed
2017-01-01 05:31:22
@article{efd1d85f-ad82-4a9f-a601-6db6414d2a1a,
  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(nl2p) 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 22p−1 and Click to view the MathML source, respectively.},
  author       = {Figueroa, Andres and Goldstein, Avraham and Jiang, Tao and Kurowski, Maciej and Lingas, Andrzej and Persson, Mia},
  issn         = {1570-8667},
  language     = {eng},
  number       = {1},
  pages        = {103--108},
  publisher    = {Elsevier},
  series       = {Journal of Discrete Algorithms},
  title        = {Approximate clustering of incomplete fingerprints},
  url          = {http://dx.doi.org/10.1016/j.jda.2007.01.004},
  volume       = {6},
  year         = {2008},
}