标题:A 2-approximation algorithm for the contig-based genomic scaffold filling problem
作者:Haitao Jiang; Letu Qingge; Daming Zhu; Binhai Zhu
作者机构:[Haitao Jiang; Daming Zhu] Shandong Univ, Sch Comp Sci & Technol, Jinan, Shandong, Peoples R China.; [Letu Qingge; Binhai Zhu] Montana State Univ, G 更多
通讯作者:Binhai, Z
通讯作者地址:[Binhai, Z]Montana State Univ, Gianforte Sch Comp, Bozeman, MT 59717 USA.
来源:JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY
出版年:2018
卷:16
期:6
DOI:10.1142/S0219720018500221
关键词:Comparative genomics; scaffold filling; contigs; adjacencies;; NP-completeness; approximation algorithms
摘要: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.
收录类别:SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85059749343&doi=10.1142%2fS0219720018500221&partnerID=40&md5=f87ff5460c7b03b4b7b01b4e61e1c5e4
TOP