Skip to Main content Skip to Navigation
Journal articles

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 metadatas

Cited literature [70 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02413025
Contributor : Fabio Pardi <>
Submitted on : Monday, December 16, 2019 - 9:29:46 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Document(s) archivé(s) le : Tuesday, March 17, 2020 - 3:36:52 PM

File

1910.11041.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02413025, version 1

Citation

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

Share

Metrics

Record views

53

Files downloads

18