Résumé
The recombination problem is inspired by genome rearrangement events that occur in bacteriophage populations. Its goal is to explain the transformation of one bacteriophage population into another using the minimum number of recombinations. Here we show that the combinatorial problem is NP-Complete, both when the target population contains only one genome of unbounded length, and when the size of the genomes is bounded by a constant. In the first case, the existence of a minimum solution is shown to be equivalent to a 3D-matching problem, and in the second case, to a satisfiability problem. These results imply that the comparison of bacteriophage populations using recombinations may have to rely on heuristics that exploit biological constraints.