Better approximation algorithms for scaffolding problems

DOI10.1007/978-3-319-39817-4_3MaRDI QIDQ4632165zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Youta Harada, Eita MacHida, Fei Guo, Lusheng Wang

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-39817-4_3

zbMATH Keywords

approximation algorithmsmatchingsrandomized algorithmsscaffolding

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Algorithms on strings (68W32) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10)

Recommendations

• Approximation algorithms for the scaffolding problem and its generalizations
• New polynomial-time algorithm around the scaffolding problem
• A complexity and approximation framework for the maximization scaffolding problem
• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• On the complexity of scaffolding problems: from cliques to sparse graphs

Cites work

• A complexity and approximation framework for the maximization scaffolding problem
• An approximation algorithm for the maximum traveling salesman problem
• On the complexity of scaffolding problems: from cliques to sparse graphs
• The Traveling Salesman Problem with Distances One and Two

Cited in

(8)

• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• Global optimization for scaffolding and completing genome assemblies
• New polynomial-time algorithm around the scaffolding problem
• A complexity and approximation framework for the maximization scaffolding problem
• Approximation algorithms for the scaffolding problem and its generalizations
• Instance guaranteed ratio on greedy heuristic for genome scaffolding
• The greedy path-merging algorithm for contig scaffolding
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies

Describes a project that uses

Uses Software

• ScaffMatch

This page was built for publication: Better approximation algorithms for scaffolding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632165)