Genomic Scaffold Filling Revisited.

• DOI: 10.4230/lipics.cpm.2016.15
• Publication Date: 2016-01-01
• Authors: Haitao Jiang; Chenglin Fan; Boting Yang; Farong Zhong; Daming Zhu; Binhai Zhu
• Keywords: Sequence (biology)

The genomic scaffold filling problem has attracted a lot of attention recently. is on an incomplete sequence (scaffold) I into I', with respect to complete reference genome G, such that the number adjacencies between G and I' maximized. NP-complete APX-hard, admits 1.2-approximation. However, input not quite practical does fit most real datasets (where more often given as list contigs). In this paper, we revisit by considering important case when, (1) S given, missing genes X = c(G) - c(S) can only be inserted in contigs, objective maximize filled S' (2) subset X' still S''. For (1), present simple NP-completeness proof, then factor-2 greedy approximation algorithm, finally show FPT when each gene appears at d times G. (2), prove W[1]-hard FPT-approximation for