The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology. In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of variants of the biological problem. Moreover, we have studied two additional variants of the original problem. We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur for every fixed position of an input vector in at most one fingerprint is polynomial-time solvable

Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Mauri, G. (2006). Fingerprint Clustering with Bounded Number of Missing Values. In Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings (pp.106-116). Berlin : Springer [10.1007/11780441_11].

Fingerprint Clustering with Bounded Number of Missing Values

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;MAURI, GIANCARLO
2006

Abstract

The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology. In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of variants of the biological problem. Moreover, we have studied two additional variants of the original problem. We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur for every fixed position of an input vector in at most one fingerprint is polynomial-time solvable
slide + paper
Clustering; fingerprint; Computational biology
English
Symposium on Combinatorial Pattern Matching
2006
Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings
783540354550
2006
4009
106
116
none
Bonizzoni, P., DELLA VEDOVA, G., Dondi, R., Mauri, G. (2006). Fingerprint Clustering with Bounded Number of Missing Values. In Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings (pp.106-116). Berlin : Springer [10.1007/11780441_11].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/16659
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact