Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Cutting an alignment with Ockham's razor

Abstract : In this article, we investigate different parsimony-based approaches towards finding re-combination 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.
Complete list of metadata

Cited literature [70 references]  Display  Hide  Download
Contributor : Fabio Pardi Connect in order to contact the contributor
Submitted on : Monday, December 16, 2019 - 9:29:46 AM
Last modification on : Thursday, November 25, 2021 - 6:04:45 AM
Long-term archiving on: : Tuesday, March 17, 2020 - 3:36:52 PM


Files produced by the author(s)


  • HAL Id : lirmm-02413025, version 1


Mark Jones, Philippe Gambette, Leo van Iersel, Remie Janssen, Steven Kelk, et al.. Cutting an alignment with Ockham's razor. 2019. ⟨lirmm-02413025⟩



Les métriques sont temporairement indisponibles