Fixed-Parameter Algorithms for Scaffold Filling

In this paper we consider two combinatorial problems related to genome comparison. The two problems, starting from possibly incomplete genomes produced from sequencing data, aim to reconstruct the complete genomes by inserting a collection of missing genes. More precisely, in the first problem, called One-sided scaffold filling, we are given an incomplete genome B and a complete genome A, and we look for the insertion of missing genes into B with the goal of maximizing the common adjacencies between the resulting genome and B′. In the second problem, called Two-sided scaffold filling, we are given two incomplete genomes A, B, and we look for the insertion of missing genes into both genomes so that the resulting genomes A′ and B′ have the same multi-set of genes, with the goal of maximizing the common adjacencies between A′ and B′. While both problems are known to be NP-hard, their parameterized complexity when parameterized by the number of common adjacencies of the resulting genomes is still open. In this paper, we settle this open problem and we present fixed-parameter algorithms for the One-sided scaffold filling problem and the Two-sided scaffold filling problem.