کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875465 | 1441955 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the scaffolding problem and its generalizations
ترجمه فارسی عنوان
الگوریتم تقریبی برای مشکل داربست و تعاریف آن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های تقریبی، الگوریتم های تصادفی، داربست، تطبیق
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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 12. 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 131-141
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 131-141
نویسندگان
Zhi-Zhong Chen, Youta Harada, Fei Guo, Lusheng Wang,