# Better Approximation Algorithms for Scaffolding Problems

Ontology type: schema:Chapter

### Chapter Info

DATE

2016-05-27

AUTHORS 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{1}{2}}$$\end{document}. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{5-5{\epsilon }}{9-8{\epsilon }}}$$\end{document} for any constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0< {\epsilon } < 1$$\end{document}. 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. More... »

PAGES

17-28

### Book

TITLE

Frontiers in Algorithmics

ISBN

978-3-319-39816-7
978-3-319-39817-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-39817-4_3

DOI

http://dx.doi.org/10.1007/978-3-319-39817-4_3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1022958113

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan"
],
"type": "Organization"
},
"givenName": "Youta",
"id": "sg:person.011526465541.54",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan"
],
"type": "Organization"
},
"familyName": "Machida",
"givenName": "Eita",
"id": "sg:person.014542220455.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014542220455.48"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computer Science and Technology, Tianjin University, Tianjin, China",
"id": "http://www.grid.ac/institutes/grid.33763.32",
"name": [
"School of Computer Science and Technology, Tianjin University, Tianjin, China"
],
"type": "Organization"
},
"familyName": "Guo",
"givenName": "Fei",
"id": "sg:person.0776100512.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776100512.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Lusheng",
"id": "sg:person.01105113721.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
],
"type": "Person"
}
],
"datePublished": "2016-05-27",
"datePublishedReg": "2016-05-27",
"description": "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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\frac{1}{2}}$$\\end{document}. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${\\frac{5-5{\\epsilon }}{9-8{\\epsilon }}}$$\\end{document} for any constant \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0< {\\epsilon } < 1$$\\end{document}. 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.",
"editor": [
{
"familyName": "Zhu",
"givenName": "Daming",
"type": "Person"
},
{
"familyName": "Bereg",
"givenName": "Sergey",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-39817-4_3",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-39816-7",
"978-3-319-39817-4"
],
"name": "Frontiers in Algorithmics",
"type": "Book"
},
"keywords": [
"polynomial-time approximation algorithm",
"approximation algorithm",
"best polynomial-time approximation algorithm",
"graph theoretical problem",
"new polynomial-time approximation algorithm",
"best approximation algorithm",
"best approximation ratio",
"Hamiltonian path P",
"Scaffolding Problem",
"previous bests",
"approximation ratio",
"graph G",
"big chains",
"path P",
"algorithm",
"problem",
"complete graph G",
"open question",
"generalization",
"edge",
"NPs",
"total weight",
"main stages",
"BEST",
"ratio",
"chain",
"literature",
"questions",
"purpose",
"genome assembly",
"stage",
"weight",
"scaffolding",
"assembly",
"contigs",
"scaffolds",
"paper"
],
"name": "Better Approximation Algorithms for Scaffolding Problems",
"pagination": "17-28",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1022958113"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-39817-4_3"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-39817-4_3",
"https://app.dimensions.ai/details/publication/pub.1022958113"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:48",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_332.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-39817-4_3"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-39817-4_3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-39817-4_3'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-39817-4_3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-39817-4_3'

This table displays all metadata directly associated to this object as RDF triples.

138 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N3437067f3385469e9db0beb063323d7c
4 schema:datePublished 2016-05-27
5 schema:datePublishedReg 2016-05-27
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{1}{2}}$$\end{document}. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{5-5{\epsilon }}{9-8{\epsilon }}}$$\end{document} for any constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0< {\epsilon } < 1$$\end{document}. 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.
7 schema:editor N25a633ea8bf343ecafdfdc49060b14a5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N48e253d494634b18b89be5592cff065e
12 schema:keywords BEST
13 Hamiltonian path P
14 NPs
15 Scaffolding Problem
16 algorithm
17 approximation algorithm
18 approximation ratio
19 assembly
20 best approximation algorithm
21 best approximation ratio
22 best polynomial-time approximation algorithm
23 big chains
24 chain
25 complete graph G
26 contigs
27 edge
28 generalization
29 genome assembly
30 graph G
31 graph theoretical problem
32 literature
33 main stages
34 new polynomial-time approximation algorithm
35 open question
37 paper
38 path P
39 polynomial-time approximation algorithm
40 previous bests
41 problem
42 purpose
43 questions
44 ratio
46 scaffolding
47 scaffolds
48 stage
49 total weight
50 weight
51 schema:name Better Approximation Algorithms for Scaffolding Problems
52 schema:pagination 17-28
53 schema:productId N3cd20288e3ca41e692278d263f98a573
54 N4f80a6c1b1d5478fa73b2bdbf7b96f85
55 schema:publisher Nba4a99d1405948e8a4e28c7717075241
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022958113
57 https://doi.org/10.1007/978-3-319-39817-4_3
58 schema:sdDatePublished 2022-05-10T10:48
60 schema:sdPublisher N6ba737b9f2254ef8bcd661ec22205bc0
61 schema:url https://doi.org/10.1007/978-3-319-39817-4_3
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N206a0686e5a04157a11f1cc4a426fc8f rdf:first sg:person.01105113721.52
66 rdf:rest rdf:nil
68 rdf:rest Ndf34ec349d9147f8a94b8dc9cb05c5bc
69 N3437067f3385469e9db0beb063323d7c rdf:first sg:person.015654265661.98
71 N3cd20288e3ca41e692278d263f98a573 schema:name doi
72 schema:value 10.1007/978-3-319-39817-4_3
73 rdf:type schema:PropertyValue
74 N48e253d494634b18b89be5592cff065e schema:isbn 978-3-319-39816-7
75 978-3-319-39817-4
76 schema:name Frontiers in Algorithmics
77 rdf:type schema:Book
78 N4f80a6c1b1d5478fa73b2bdbf7b96f85 schema:name dimensions_id
79 schema:value pub.1022958113
80 rdf:type schema:PropertyValue
82 schema:givenName Daming
83 rdf:type schema:Person
84 N6ba737b9f2254ef8bcd661ec22205bc0 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N7e69832da0bf44f396ca309b28fa7eef schema:familyName Bereg
87 schema:givenName Sergey
88 rdf:type schema:Person
89 Na30d2f8767584660827d642529780590 rdf:first sg:person.014542220455.48
90 rdf:rest Nc5426054fd93436aafa60cb947935afc
91 Nba4a99d1405948e8a4e28c7717075241 schema:name Springer Nature
92 rdf:type schema:Organisation
93 Nc5426054fd93436aafa60cb947935afc rdf:first sg:person.0776100512.16
94 rdf:rest N206a0686e5a04157a11f1cc4a426fc8f
95 Ndf34ec349d9147f8a94b8dc9cb05c5bc rdf:first N7e69832da0bf44f396ca309b28fa7eef
96 rdf:rest rdf:nil
98 rdf:rest Na30d2f8767584660827d642529780590
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.01105113721.52 schema:affiliation grid-institutes:None
106 schema:familyName Wang
107 schema:givenName Lusheng
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
109 rdf:type schema:Person
110 sg:person.011526465541.54 schema:affiliation grid-institutes:grid.412773.4
112 schema:givenName Youta
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011526465541.54
114 rdf:type schema:Person
115 sg:person.014542220455.48 schema:affiliation grid-institutes:grid.412773.4
116 schema:familyName Machida
117 schema:givenName Eita
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014542220455.48
119 rdf:type schema:Person
120 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
121 schema:familyName Chen
122 schema:givenName Zhi-Zhong
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
124 rdf:type schema:Person
125 sg:person.0776100512.16 schema:affiliation grid-institutes:grid.33763.32
126 schema:familyName Guo
127 schema:givenName Fei
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0776100512.16
129 rdf:type schema:Person
130 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
131 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
132 rdf:type schema:Organization
133 grid-institutes:grid.33763.32 schema:alternateName School of Computer Science and Technology, Tianjin University, Tianjin, China
134 schema:name School of Computer Science and Technology, Tianjin University, Tianjin, China
135 rdf:type schema:Organization
136 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan
137 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Saitama, Hatoyama, Japan
138 rdf:type schema:Organization