首页> 外文会议>International Conference on Algorithmic Applications in Management >A 2.57-Approximation Algorithm for Contig-Based Genomic Scaffold Filling
【24h】

A 2.57-Approximation Algorithm for Contig-Based Genomic Scaffold Filling

机译:基于重叠群的基因组支架填充的2.57近似算法

获取原文

摘要

Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problem, called One-sided-GSF-max-BC problem. The previous approximation ratio for the problem is 2. However, as we pointed out in the introduction part, the ratio 2 algorithm in the literature can only deal with special instances of the problem, not really solve the One-sided-GSF-max-BC problem. In this paper, we give an approximation algorithm of ratio 2.57 for the One-sided-GSF-max-BC problem. Our method is based on auxiliary graphs constructed and two applications of finding maximum matching in auxiliary graphs.
机译:基因组支架填充问题是一类重要的问题,在文献中已引起广泛关注。在本文中,我们研究了一种基因组支架填充问题,称为单面-GSF-max-BC问题。该问题以前的近似比率为2。但是,正如我们在引言部分所指出的那样,文献中的比率2算法只能处理问题的特殊情况,而不能真正解决单边-GSF-max- BC问题。在本文中,我们给出了单边-GSF-max-BC问题的比率2.57的近似算法。我们的方法基于构造的辅助图以及在辅助图中找到最大匹配的两个应用。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号