Fingerprint Clustering with Bounded Number of Missing Values |
| |
Authors: | Paola Bonizzoni Gianluca Della Vedova Riccardo Dondi Giancarlo Mauri |
| |
Affiliation: | 1. DISCo, Università degli Studi di Milano-Bicocca, Milano, Italy 2. Dip. Statistica, Università degli Studi di Milano-Bicocca, via Bicocca degli Arcimboldi 8, Milano, Italy 3. Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali, Università degli Studi di Bergamo, Bergamo, Italy
|
| |
Abstract: | The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology that
has been proposed in Figueroa et al. (J. Comput. Biol. 11(5):887–901, 2004). 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 proposed
in Figueroa et al. (Proc. 11th Computing: The Australasian Theory Symposium (CATS), CRPIT, vol. 41, pp. 57–60, 2005). 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|