Fingerprint clustering with bounded number of missing values

DOI10.1007/S00453-008-9265-0MaRDI QIDQ5961971zbMATH OpenOpenAlexWikidataFDO

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

Publication date 16 September 2010

Published in Algorithmica (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Complexity of approximating bounded variants of optimization problems
• Some APX-completeness results for cubic graphs

Cited in

(4)

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

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)