Cutting an alignment with Ockham's razor - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2019

Cutting an alignment with Ockham's razor

Mark Jones
  • Function : Author
  • PersonId : 1046445
Remie Janssen
  • Function : Author
  • PersonId : 1061069
Fabio Pardi


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.
Fichier principal
Vignette du fichier
1910.11041.pdf (405.79 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-02413025 , version 1 (16-12-2019)


  • 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⟩
158 View
104 Download


Gmail Mastodon Facebook X LinkedIn More