Fingerprint clustering with bounded number of missing values

DOI10.1007/S00453-008-9265-0zbMATH Open1205.68334arXivcs/0511082OpenAlexW1973297314WikidataQ57518523 ScholiaQ57518523MaRDI QIDQ5961971FDOQ5961971

Authors: Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Giancarlo Mauri 

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The problem of clustering fingerprint vectors is an interesting problem in Computational Biology that has been proposed in (Figureroa et al. 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of some variants of the biological problem. Namely we are able to prove that the problem is APX-hard even when each fingerprint contains only two unknown position. Moreover we have studied some variants of the orginal problem, and we give two 2-approximation algorithm for the IECMV and OECMV problems when the number of unknown entries for each vector is at most a constant.

Full work available at URL: https://arxiv.org/abs/cs/0511082

Recommendations

• Fingerprint Clustering with Bounded Number of Missing Values
• Approximate clustering of incomplete fingerprints
• A fingerprint identification algorithm by clustering similarity
• Efficient fingerprint search based on database clustering
• Complexity and improved heuristic algorithms for binary fingerprints clustering

zbMATH Keywords

clusteringapproximation algorithmfingerprint vectors

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Biochemistry, molecular biology (92C40) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Some APX-completeness results for cubic graphs
• Complexity of approximating bounded variants of optimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Approximate clustering of incomplete fingerprints
• Clustering binary oligonucleotide fingerprint vectors for DNA clone classification analysis
• Fingerprint Clustering with Bounded Number of Missing Values
• Complexity and improved heuristic algorithms for binary fingerprints clustering

This page was built for publication: Fingerprint clustering with bounded number of missing values

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961971)