首页> 外文期刊>Algorithmica >Fingerprint Clustering with Bounded Number of Missing Values
【24h】

Fingerprint Clustering with Bounded Number of Missing Values

机译:缺失值有界数的指纹聚类

获取原文
获取原文并翻译 | 示例
       

摘要

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.
机译:带有丢失值的指纹矢量聚类的问题是计算生物学中一个有趣的问题,已在Figueroa等人的论文中提出。 (J. Comput。Biol。11(5):887-901,2004)。在本文中,我们展示了在缩小已知问题下限和上限之间的距离方面的一些改进,这些问题在生物学问题的变体之间具有近似性。此外,我们研究了Figueroa等人提出的原始问题的两个其他变体。 (Proc。11th Computing:澳大利亚理论研讨会(CATS),CRPIT,第41卷,第57-60页,2005年)。我们证明了即使在每个指纹仅包含两个未知位置的情况下,所有此类问题都是APX难题,并且我们提出了一种贪婪算法,该算法对于这些变体具有恒定的近似因子。尽管问题的这些受限形式很棘手,但我们表明,无穷多个缺失值的一般聚类问题使得输入向量在每个指纹中的每个固定位置最多出现一个指纹是可以解决的多项式时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号