Résumé
In this article, we investigate different parsimony-based approaches towards
finding recombination breakpoints in a multiple sequence alignment. This
recombination detection task is crucial in order to avoid errors in
evolutionary analyses caused by mixing together portions of sequences which had
a different evolution history. Following an overview of the field of
recombination detection, we formulate four computational problems for this task
with different objective functions. The four problems aim to minimize (1) the
total homoplasy of all blocks (2) the maximum homoplasy per block (3) the total
homoplasy ratio of all blocks and (4) the maximum homoplasy ratio per block. We
describe algorithms for each of these problems, which are fixed-parameter
tractable (FPT) when the characters are binary. We have implemented and tested
the algorithms on simulated data, showing that minimizing the total homoplasy
gives, in most cases, the most accurate results. Our implementation and
experimental data have been made publicly available. Finally, we also consider
the problem of combining blocks into non-contiguous blocks consisting of at
most p contiguous parts. Fixing the homoplasy h of each block to 0, we show
that this problem is NP-hard when p >= 3, but polynomial-time solvable for p =
2. Furthermore, the problem is FPT with parameter h for binary characters when
p = 2. A number of interesting problems remain open.