Orienting Ordered Scaffolds: Complexity and Algorithms

We address the problem of orientating ordered scaffolds as an optimization problem based on given weighted orientations of scaffolds and their pairs. We formalize this problem using notion of a scaffold graph. We prove that this problem is 𝖭𝖯NP-hard, and present a polynomial-time algorithm for solving its special case, where orientation of each scaffold is imposed relatively to at most two other scaffolds.