Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Approximate clustering of fingerprint vectors with missing values

In English

Författare

  • 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.

Avdelning/ar

  • Computer Science

Publiceringsår

2005

Språk

Engelska

Sidor

57-60

Publikation/Tidskrift/Serie

Proceedings of the 2005 Australasian symposium on Theory of computing

Dokumenttyp

Konferensbidrag

Förlag

Australian Computer Society

Ämne

  • Computer Science

Conference name

Computing: The Australasian Theory Symposium

Conference date

0001-01-02

Conference place

Newcastle, Australia

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

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