Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions (”contigs”) are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and $$\mathcal {NP}$$ -hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score.

International audience

International audience

This paper presents new structural and algorithmic results around the scaffolding problem, which occurs prominently in next generation sequencing. The problem can be formalized as an optimization problem on a special graph, the "scaffold graph". We prove that the problem is polynomial if this graph is a tree by providing a dynamic programming algorithm for this case. This algorithm serves as a basis to deduce an exact algorithm for general graphs using a tree decomposition of the input. We explore other structural parameters, proving a linear-size problem kernel with respect to the size of a feedback-edge set on a restricted version of Scaffolding. Finally, we examine some parameters of scaffold graphs, which are based on real-world genomes, revealing that the feedback edge set is significantly smaller than the input size.

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.

Until recently, the standard communication model for scheduling the task of a parallel program has been the homogeneous communication model (also known as the delay model) introduced by Rayward-Smith for unit-execution-times, unit-communication times (UET-UTC) precedence graphs. In this model, we have a set of identical processors that are able to communicate in a uniform way. We want to use these processors in order to process a set of tasks that are subject to precedence contraints. Each task has a processing time, and if two adjacent task of the precedence graph are processed by two different processors (resp. the same processors) then a communication delay has to be taken into account explicitly (resp. the communication time is neglected). The problem is to find a trade-off between the two extreme solutions, namely, execute all the tasks sequentially without communications, or try to use all the potential parallelism but in the cost of an increased communication overhead. This model has been extensively studied these last years both from the compexity and the (non)-approximability point of views.