Approximation algorithms for the scaffolding problem and its generalizations

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)131-141
Journal / PublicationTheoretical Computer Science
Volume734
Online published13 Apr 2017
Publication statusPublished - 22 Jul 2018

Abstract

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ε/9-8ε for any constant 0 < ε < 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.

Research Area(s)

  • Approximation algorithms, Matchings, Randomized algorithms, Scaffolding

Citation Format(s)

Approximation algorithms for the scaffolding problem and its generalizations. / Chen, Zhi-Zhong; Harada, Youta; Guo, Fei et al.
In: Theoretical Computer Science, Vol. 734, 22.07.2018, p. 131-141.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review