The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximate clustering of fingerprint vectors with missing values

På svenska

Author

  • Andres Figueroa
  • Avraham Goldstein
  • Tao Jiang
  • Maciej Kurowski
  • Andrzej Lingas
  • Mia Persson

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

57-60

Publication/Series

Proceedings of the 2005 Australasian symposium on Theory of computing

Document type

Conference paper

Publisher

Australian Computer Society

Topic

  • Computer Science

Conference name

Computing: The Australasian Theory Symposium

Conference date

0001-01-02

Conference place

Newcastle, Australia

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 1445-1336
  • ISBN: 1-920682-23-6