We have located links that may give you full text access.
A 2-approximation algorithm for the contig-based genomic scaffold filling problem.
Journal of Bioinformatics and Computational Biology 2018 December
The genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I ' , with respect to a complete reference genome G , such that the number of common/shared adjacencies between G and I ' is maximized. The problem is NP-complete, and admits a constant-factor approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when a scaffold S is given, the missing genes can only be inserted in between the contigs, and the objective is to maximize the number of common adjacencies between G and the filled genome S ' . For this problem, we present a simple NP-completeness proof, we then present a factor-2 approximation algorithm.
Full text links
Related Resources
Get seemless 1-tap access through your institution/university
For the best experience, use the Read mobile app
All material on this website is protected by copyright, Copyright © 1994-2024 by WebMD LLC.
This website also contains material copyrighted by 3rd parties.
By using this service, you agree to our terms of use and privacy policy.
Your Privacy Choices
You can now claim free CME credits for this literature searchClaim now
Get seemless 1-tap access through your institution/university
For the best experience, use the Read mobile app