Better Approximation Algorithms for Scaffolding Problems

被引:1
作者
Chen, Zhi-Zhong [1 ]
Harada, Youta [1 ]
Machida, Eita [1 ]
Guo, Fei [2 ]
Wang, Lusheng [3 ]
机构
[1] Tokyo Denki Univ, Div Informat Syst Design, Saitama, Hatoyama 3500394, Japan
[2] Tianjin Univ, Sch Comp Sci & Technol, Tianjin, Peoples R China
[3] City Univ Hong Kong, Dept Comp Sci, Tat Chee Ave, Kowloon, Hong Kong, Peoples R China
来源
Frontiers in Algorithmics, FAW 2016 | 2016年 / 9711卷
关键词
Approximation algorithms; Randomized algorithms; Scaffolding; Matchings; TRAVELING SALESMAN PROBLEM; COMPLEXITY;
D O I
10.1007/978-3-319-39817-4_3
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theoretical problem has been proposed: Given an edge-weighted complete graph G and a perfect matching D of G, we wish to find a Hamiltonian path P in G such that all edges of D appear in P and the total weight of edges in P but not in D is maximized. This problem is NP-hard and the previously best polynomial-time approximation algorithm for it achieves a ratio of 1/2. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of 5-5 epsilon/9-8 epsilon for any constant 0 < epsilon < 1. Several generalizations of the problem have also been introduced in the literature and we present polynomial-time approximation algorithms for them that achieve better approximation ratios than the previous bests. In particular, one of the algorithms answers an open question.
引用
收藏
页码:17 / 28
页数:12
相关论文
共 8 条
  • [1] A complexity and approximation framework for the maximization scaffolding problem
    Chateau, A.
    Giroudeau, R.
    [J]. THEORETICAL COMPUTER SCIENCE, 2015, 595 : 92 - 106
  • [2] Chateau A, 2014, LECT N BIOINFORMAT, V8542, P47, DOI 10.1007/978-3-319-07953-0_4
  • [3] An approximation algorithm for the maximum traveling salesman problem
    Hassin, R
    Rubinstein, S
    [J]. INFORMATION PROCESSING LETTERS, 1998, 67 (03) : 125 - 130
  • [4] A comprehensive evaluation of assembly scaffolding tools
    Hunt, Martin
    Newbold, Chris
    Berriman, Matthew
    Otto, Thomas D.
    [J]. GENOME BIOLOGY, 2014, 15 (03):
  • [5] ScaffMatch: scaffolding algorithm based on maximum weight matching
    Mandric, Igor
    Zelikovsky, Alex
    [J]. BIOINFORMATICS, 2015, 31 (16) : 2632 - 2638
  • [6] The Genomes OnLine Database (GOLD) v.4: status of genomic and metagenomic projects and their associated metadata
    Pagani, Ioanna
    Liolios, Konstantinos
    Jansson, Jakob
    Chen, I-Min A.
    Smirnova, Tatyana
    Nosrat, Bahador
    Markowitz, Victor M.
    Kyrpides, Nikos C.
    [J]. NUCLEIC ACIDS RESEARCH, 2012, 40 (D1) : D571 - D579
  • [7] THE TRAVELING SALESMAN PROBLEM WITH DISTANCES ONE AND 2
    PAPADIMITRIOU, CH
    YANNAKAKIS, M
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (01) : 1 - 11
  • [8] On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
    Weller, Mathias
    Chateau, Annie
    Giroudeau, Rodolphe
    [J]. COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015), 2015, 9486 : 409 - 423